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

0) прибавляющую 1 к натуральному числу n, представленному в троичной системе счисления. Начальная конфигурация: q1b1b2…bn, где bi – троичные цифры 0, 1 или 2;

1) складывающую натуральные числа m и n в троичной системе счисления. Начальная конфигурация:
q1b11b12…b1s+b21b22…b2p, заключительная конфигурация: q0b31b32…b3q, где b1i, b2j, b3k – троичные цифры 0, 1 или 2;

2) прибавляющую 1 к натуральному числу n, представленному в шестеричной системе счисления. Начальная конфигурация: q1d1d2…ds, где di – шестеричные цифры 0, 1, …, 5. (Для сокращения записи программы используйте метасимволы);

3) вычитающую 1 из натурального числа n > 1, представленного в десятичной системе счисления. Начальная конфигурация: q1d1d2…ds, где di – десятичные цифры 0, 1, …, 9. (Для сокращения записи программы используйте метасимволы);

4) складывающую натуральные числа m и n в десятичной системе счисления. Начальная конфигурация: q1d11d12…d1s+d21d22…d2p, заключительная конфигурация: q0d31d32…d3q, где d1i, d2j, d3k – десятичные цифры 0, 1, …, 9. (Для сокращения записи программы используйте метасимволы);

5) вычитающую 1 из натурального числа n > 1, представленного в троичной системе счисления. Начальная конфигурация: q1b1b2…bn, где bi – троичные цифры 0, 1 или 2;

6) прибавляющую 1 к натуральному числу n, представленному в десятичной системе счисления. Начальная конфигурация: q1d1d2…ds, где di – десятичные цифры 0, 1, …, 9. (Для сокращения записи программы используйте метасимволы);

7) складывающую натуральные числа m и n в четвертичной системе счисления. Начальная конфигурация: q1b11b12…b1s+b21b22…b2p, заключительная конфигурация: q0b31b32…b3q, где b1i, b2j, b3k – четвертичные цифры 0, 1, 2 или 3;

8) вычитающую 1 из натурального числа n > 1, представленного в пятеричной системе счисления. Начальная конфигурация: q1b1b2…bn, где bi – пятеричные цифры 0, 1, 2, 3 или 4;

9) прибавляющую 1 к натуральному числу n, представленному в восьмеричной системе счисления. Начальная конфигурация: q1d1d2…ds, где di – восьмеричные цифры 0, 1, …, 7. (Для сокращения записи программы используйте метасимволы) .
2. Постройте машину Тьюринга, подсчитывающую

0) число единиц в двоичном коде a1a2…an и записывающую результат подсчета слева от заданного кода в троичной системе счисления. Начальная конфигурация: q1a1a2…an, заключительная конфигурация: q₀b₁b₂…b_m* q₁a₁a₂…a_n, где ai – двоичные цифры 0, 1; bi – троичные цифры 0, 1 или 2;

1) число вхождений символа a в слово P в алфавите {a, b, c, d} и записывающую результат в троичной системе счисления слева от слова Р. Начальная конфигурация: q₁y₁y₂…y_n. Заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yiÎ{a, b, c, d}; bi – троичная цифра 0, 1 или 2;

2) число единиц в слове P в двоичном алфавите {0, 1} и записывающую это число в десятичной системе счисления слева от слова P. Начальная конфигурация: q₁y₁y₂…y_n, заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yiÎ{0,1}; biÎ{0,1,2,3,4,5,6,7,8,9};

3) число единиц в слове P в двоичном алфавите {0,1} и записывающую это число в восьмеричной системе счисления слева от слова P. Начальная конфигурация: q1y1y2…yn, заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yiÎ{0,1}; biÎ{0,1,2,3,4,5,6,7};

4) число вхождений строки 101 в двоичное слово Р и записывающую результат слева от слова Р в троичной системе счисления. Начальная конфигурация: q1y1y2…yn, заключительная конфигурация: q₀y₁y₂…y_n * b₁b₂…b_m, где yiÎ{0,1}; biÎ{0,1,2,3};

5) число вхождений строки aba в слово Р в алфавите {a,b} и записывающую результат слева от слова Р в двоичной системе счисления. Начальная конфигурация: q1y1y2…yn, заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yiÎ{a, b}; biÎ{0,1};

6) сумму цифр троичного числа и записывающую результат слева от заданного троичного числа в двоичной системе счисления. Начальная конфигурация: q₁y₁y₂…y_n, заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yiÎ{0, 1, 2}; biÎ{0,1};

7) сумму цифр десятичного числа и записывающую результат слева от заданного десятичного числа в десятичной системе счисления. Начальная конфигурация: q1y1y2…yn, заключительная конфигурация: q₀b₁b₂…b_m*y₁y₂…y_n, где yi, bi Î{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. (Для сокращения записи программы используйте метасимволы.);

8) число нулей в двоичном коде q₁a₁a₂…a_n и записывающую результат подсчета слева от заданного кода в троичной системе счисления. Начальная конфигурация: q₁a₁a₂…a_n, заключительная конфигурация: q₀b₁b₂…b_m* q₁a₁a₂…a_n, где ai – двоичные цифры 0, 1; bi – троичные цифры 0, 1 или 2;

9) число вхождений строки 100 в двоичное слово Р и записывающую результат слева от слова Р в троичной системе счисления. Начальная конфигурация: q₀y₁y₂…y_n, заключительная конфигурация: q₀y₁y₂…y_n * b₁b₂…b_m, где yiÎ{0,1}; biÎ{0,1,2,3}.

Дата добавления: 2014-11-20