Повторение (цикл)

Используя конструкцию для ветвления легко реализовать в терминах машин Тьюринга и оператор цикла.

Лемма 9.6. Пусть ? - распознающая м.Т., а м.Т.

вычисляет функцию f(x). Тогда существует м.Т. которая вычисляет функцию, задаваемую выражением:

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

- вычисляет тождественную функцию g(x)=x. Построим по м.Т.

м.Т.

реализующую ветвление как в лемме 9.5. Тогда искомая м.Т. получается из заменой команд qf1 a qf a H (a ?) на соответствующие команды qf1 a q0 a H (a ?), обеспечивающие зацикливание.

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

(здесь b - это символ, разделяющий аргументы и результаты этих машин), ветвление -

цикл -

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

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*

)); M4 - м.Т., которая стирает * в аргументе вида x* и останавливается. Реализация каждой из указанных м.Т. очевидна. Теперь требуемая м.Т. Mub, вычисляющая fub, получается как

Действительно, после работы 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)*

. На ней ? выдаст 1, и цикл завершится с записью n(2)* на ленте, из которой M4 сотрет * и оставит требуемый результат n(2).

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

Содержание раздела

---