Задачи.

1.

Построить машину Тьюринга, которая выполняет следующие операции в унарной системе счисления: а) сложение; б) вычитание натуральных чисел;

в) умножение; г) нахождение целой части частного.

2.

На ленте записано число в унарной системе. Составить таблицу, с помощью которой можно отвечать на вопрос: делится ли данное число на пять.

3.

Построить машину Тьюринга для перевода числа, записанного в унарной системе, в двоичную систему.

4.

Построить машину Тьюринга, с помощью которой можно перевести в унарную систему запись числа в двоичной системе.

5.

Составить функциональную таблицу машины Тьюринга для перевода записи числа из троичной системы в четверичную систему.

6.

На ленте записано некоторое число массивов палочек, разделенных звездочками. Построить машину Тьюринга, которая могла бы подсчитать число массивов на ленте и записать это число в унарном коде.

7.

Построить машину Тьюринга, которая преобразует всякое натуральное число 2N в число NxN в унарной системе.

8.

Построить машину Тьюринга для нахождения наибольшего общего делителя двух натуральных чисел в унарной системе счисления.

9.

Построить машину Тьюринга для преобразования любого унарного числа вида M*N в | M - N |.

10.

Построить машину Тьюринга для перевода натуральных чисел из унарной системы счисления в десятичную.

11.

Построить машину Тьюринга для перевода натуральных чисел из десятичной системы счисления в унарную.

12.

Построить машину Тьюринга, которая преобразует всякое натуральное число в остаток Х от деления этого числа на три (число представлено в унарной системе счисления).

13.

Построить машину Тьюринга, преобразующую всякое натуральное число, представленное в унарной системе счисления, в остаток от деления этого числа на 5.

14.

Построить машину Тьюринга для перевода натуральных чисел из унарной системы счисления в восьмеричную.

15.

Построить машину Тьюринга для перевода натуральных чисел из

восьмеричной системы счисления в унарную.

16.

Построить машину Тьюринга для перевода натуральных чисел из унарной системы счисления в пятеричную.

17.

Построить машину Тьюринга для перевода натуральных чисел из пятеричной системы счисления в унарную.

18.

Построить машину Тьюринга, которая преобразует унарное число N в число 3N-2.

19.

Построить машину Тьюринга, которая преобразует унарное число M*N в число 2(M-N) при условии M>N.

20.

Построить машину Тьюринга, которая преобразует унарное число M*N в число 3(M+N).

21.

Построить машину Тьюринга, которая преобразует унарное число N в целую часть числа (N+2):2.

22.

Построить машину Тьюринга, которая переводит натуральное число из троичной системы счисления в унарную.

23.

Построить машину Тьюринга, которая заменяет число Х, записанное в унарной системе, целой частью числа (3Х+1):2.

24.

Построить машину Тьюринга, которая удваивает любое записанное на ленте слово в алфавите {a, b, c}

25.

Построить машину Тьюринга, которая переворачивает любое записанное на ленте слово в алфавите{a, b, c}.