Повторение (цикл)
Используя конструкцию для ветвления легко реализовать в терминах машин Тьюринга и оператор цикла.
Лемма 9.6. Пусть ? - распознающая м.Т., а м.Т.



Доказательство. Действительно, пусть м.Т.


м.Т.







Реализованные выше операции над машинами Тьюринга и вычислимыми функциями позволяют получать программы новых м.Т., используя обычные конструкции языка программирования "высокого" уровня: последовательную и параллельную композицию, ветвление и цикл. Пусть M, M1, M2,… , Mm, ? - машины Тьюринга. Последовательную композицию M1 и M2 будем обозначать M1;M2, параллельную композицию M1, M2,… , Mm обозначаем как


цикл -

Пример 9.4. Рассмотрим в качестве примера задачу перевода чисел из унарной системы счисления в двоичную. Пусть fub(|n) = n(2) для всех n

Пусть M1 - м.Т., которая начальную конфигурацию q0 ,|n переводит в конфигурацию q1 ,0*|n; M2 - м.Т., которая прибавляет 1 к двоичному числу-аргументу (см. пример ref{ex8-suc}); M3 - м.Т., которая вычитает 1 из унарного числа; ? - м.Т., которая на аргументе вида x*|y выдает 0, если число y > 0, и выдает 1 при y=0 (т.е. на аргументе x*


Действительно, после работы M1 получаем конфигурацию q10*|n. Предположим теперь по индукции, что после i (i <n) итераций цикла while получается конфигурация q1 i(2)*|n-i. Тогда на (i+1)-ой итерации цикла после параллельного применения M2 к i(2) и M3 к |n-i
получаем конфигурацию q1(i+1)(2)*|n-i-1. Поэтому после n итераций получится конфигурация q1 n(2)*


Отметим, что из приведенного примера и из задачи \oldref{prb3-6}(a) следует, что класс вычислимых на м.Т. арифметических функций не зависит от выбора унарного или двоичного кодирования аргументов и результатов. Это же справедливо и для троичной, десятичной и других позиционных систем счисления ( почему ?).