Ветвление (условный оператор)

Машину Тьюринга будем называть распознающей, если для некоторого алфавита и каждого входа , на котором останавливается, ее результат , т.е. вычисляет некоторую двузначную функцию (возможно частичную) на словах из

Лемма 9.5. Пусть - распознающая м.Т., м.Т. вычисляет функцию f(x), а м.Т. - функцию g(x). Тогда существует м.Т. вычисляющая функцию

Доказательство. Требуемая м.Т. вначале копирует вход x и получает на ленте слово x*x, затем вычисляет параллельную композицию функций и тождественной функции e(x)=x и переходит в конфигурацию . Выбор между f и g происходит по следующим командам:

Кроме того, обеспечим переход в новое заключительное состояние:

Таким образом, мы реализовали в терминах машин Тьюринга обычный в языках программирования оператор ветвления:

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

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

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

Доказательство. Действительно, пусть м.Т. - вычисляет тождественную функцию g(x)=x. Построим по м.Т. м.Т. реализующую ветвление как в лемме 9.5. Тогда искомая м.Т. получается из заменой команд на соответствующие команды , обеспечивающие зацикливание.

Реализованные выше операции над машинами Тьюринга и вычислимыми функциями позволяют получать программы новых м.Т., используя обычные конструкции языка программирования "высокого" уровня: последовательную и параллельную композицию, ветвление и цикл. Пусть - машины Тьюринга. Последовательную композицию M₁ и M₂ будем обозначать M₁;M₂, параллельную композицию M₁, M₂,... , M_m обозначаем как (здесь b - это символ, разделяющий аргументы и результаты этих машин), ветвление -

цикл -

Пример 9.4. Рассмотрим в качестве примера задачу перевода чисел из унарной системы счисления в двоичную. Пусть f^ub(|ⁿ) = n₍₂₎ для всех , где n₍₂₎ - двоичная запись числа n.

Пусть M₁ - м.Т., которая начальную конфигурацию q₀ ,|ⁿ переводит в конфигурацию q₁ ,0*|ⁿ; M₂ - м.Т., которая прибавляет 1 к двоичному числу-аргументу (см. пример ref{ex8-suc}); M₃ - м.Т., которая вычитает 1 из унарного числа; - м.Т., которая на аргументе вида x*|^y выдает 0, если число y > 0, и выдает 1 при y=0 (т.е. на аргументе ); M₄ - м.Т., которая стирает * в аргументе вида x* и останавливается. Реализация каждой из указанных м.Т. очевидна. Теперь требуемая м.Т. M_ub, вычисляющая f^ub, получается как

Действительно, после работы M₁ получаем конфигурацию q₁0*|ⁿ. Предположим теперь по индукции, что после i (i <n) итераций цикла while получается конфигурация q₁ i₍₂₎*|^n-i. Тогда на (i+1) -ой итерации цикла после параллельного применения M₂ к i₍₂₎ и M₃ к |^n-i получаем конфигурацию q₁(i+1)₍₂₎*|^n-i-1. Поэтому после n итераций получится конфигурация . На ней выдаст 1, и цикл завершится с записью на ленте, из которой M₄ сотрет * и оставит требуемый результат n₍₂₎.

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

Может быть рассмотрено еще одно обобщение машин Тьюринга: их композиции. Операции композиции, выполняемые над алгоритмами, позволяют образовывать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга - алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них: произведение, возведение в степень, итерацию.

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

На­по­мним, что впер­вые идея ну­ме­ра­ции кон­стру­к­тив­ных объ­е­к­тов (не­чис­ло­вой при­ро­ды) на­ту­ра­ль­ны­ми чис­ла­ми бы­ла вы­ска­за­на и ре­али­зо­ва­на К.Гёделем (вспом­ни­те до­ка­за­те­ль­ст­во те­оре­мы Гё­де­ля о пол­но­те).

 

Опре­де­ле­ние (по [Мат­ро­сов,1989,с.104]).

(1) (Гё­де­ле­вой) ну­ме­ра­ци­ей объ­е­к­тов мно­же­ст­ва E на­зо­вём отоб­ра­же­ние g:N_g®E не­ко­то­ро­го мно­же­ст­ва на­ту­ра­ль­ных чи­сел N_gÍN на мно­же­ст­во кон­стру­к­тив­ных объ­е­к­тов E.

(2) Одно­знач­ной гё­де­ле­вой ну­ме­ра­ци­ей объ­е­к­тов мно­же­ст­ва E на­зо­вём ну­ме­ра­цию объ­е­к­тов мно­же­ст­ва E, яв­ля­ющу­юся би­ек­ци­ей.

(3) Про­стой гё­де­ле­вой ну­ме­ра­ци­ей объ­е­к­тов мно­же­ст­ва E на­зо­вём ну­ме­ра­цию объ­е­к­тов мно­же­ст­ва E в слу­чае, ког­да N_g=N.

Ну­ме­ра­ция (ко­ди­ро­ва­ние) про­грамм игра­ет фун­да­мен­та­ль­ную роль в те­ории вы­чис­ле­ний.

Пер­вый спо­соб по­стро­ения гё­де­ле­вой ну­ме­ра­ции ма­ши­ны Тью­рин­га.

Рас­смо­трим про­из­во­ль­ную ма­ши­ну Тью­рин­га M. Пред­ста­вим про­грам­му ма­ши­ны Тью­рин­га M в ви­де сле­ду­ющей фун­кци­она­ль­ной схе­мы, в ко­то­рой a'Î{a₀,...,a_m}_, q'Î{q₀,...,q_n}, rÎ{L,L,R}: