Введение в схемы, автоматы и алгоритмы



             

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


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

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

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

g(x) =\ '\mbox {\bf while}\ \Phi(x)= 0\ \mbox {\bf do }\ \ x := f(x)\ \mbox {\bf enddo}'

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

{\cal M}_2
- вычисляет тождественную функцию g(x)=x. Построим по м.Т.
\Phi, {\cal M}_1 \mbox { и }\ {\cal M}_2\

м.Т.

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

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

\mathbf {par}_b(M_1,M_2,\ldots , M_m)\
(здесь b - это символ, разделяющий аргументы и результаты этих машин), ветвление -

{\bf if}\ \Phi\ {\bf then}\ M_1\ {\bf else}\ M_2\ {\bf endif}

цикл -

{\bf while}\ \Phi\ {\bf do }\ M\ {\bf enddo}.

Пример 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, получается как

M_1; {\bf while}\ \Phi\ \mathbf{ do\ \ par}_*(M_2,M_3)\ {\bf enddo}; M_4.

Действительно, после работы 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) следует, что класс вычислимых на м.Т. арифметических функций не зависит от выбора унарного или двоичного кодирования аргументов и результатов. Это же справедливо и для троичной, десятичной и других позиционных систем счисления ( почему ?).




Содержание  Назад  Вперед