Тьюрингово программирование

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

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

Пример 1.

1. Построить машину Тьюринга, переводящую слово в слово , если внешний алфавит .

2. Проверить работу машины Тьюринга над некоторым словом.

Решение.

1. Опишем работу алгоритма, решающего задачу.

Будем обозначать состояния машины Тьюринга числами 0,1,2,…, причем 1 ‑ начальное, а 0 ‑ заключительное состояния.

Так как нам надо переписать слово в обратном порядке, то понадобится вспомогательный символ внешнего алфавита, который обозначим «*», т.е. .

Вначале с помощью команд ; заменяем на «*» и движемся влево. Признаком окончания слова будет считывание λ в состояниях 2 или 3. С помощью команд

и

печатаем символ , движемся вправо и переходим в состояние 4.

Запишем промежуточные конфигурации:

Если в состоянии 4 считываем символы а или b, то, не изменяя символы и состояние, движемся вправо. Это позволит пройти новое слово, которое строим, без изменений.

,

Если в состоянии 4 считываем символ «*», то это значит, что новое слово пройдено и надо переходить в следующее состояние 5, чтобы дойти до остатков старого слова.

Если в состоянии 5 считываем символ «*», то движемся вправо, не меняя символ и состояние. Если в состоянии 5 считываем символы а или b, значит, дошли до остатков старого слова. Заменяем символы на «*», переходим в состояния 2 или 3 и движемся влево.

, ,

В состояниях 2 или 3, двигаясь влево, нужно пройти все символы «*», а также новое слово. Это позволят сделать команды:

, , ,

, , .

Признаком того, что все символы «*», а также новое слово пройдены, будет считывание λ в состояниях 2 или 3.

Запишем промежуточные конфигурации:

Дальше по циклу все символы перепишутся. Признаком того, что старое слово закончилось, является считывание символа λ в состоянии 5. Остается стереть все символы «*» и остановится в начале нового слова. Для этого понадобятся команды:

; ; ; ; .

Запишем все конфигурации:

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

A\Q
λ	‑			‑
a
b
*	‑

2. Проверим работу машины Тьюринга над словом .

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

Пример2.

1. Построить машину Тьюринга, вычисляющую числовую функцию .

2. Проверить работу построенной машины над некоторым набором значений.

Решение.

1. Будем обозначать состояния машины Тьюринга причем ‑ начальное, а ‑ заключительное состояния.

Набор значений аргументов изображается словом .

Аргумент должен остаться без изменения, этого можно добиться с помощью команды . Когда в состоянии встретиться символ λ, значит, мы попали на символ, разделяющий изображения аргументов, переходим в состояние , а сам символ λ пока оставим без изменений с помощью команды .

Далее набор единиц, изображающих аргумент , проходим до конца. Для этого добавим команды: ; .

Теперь с помощью «челночного» алгоритма удвоим количество единиц в блоке, изображающем вторую переменную.

Расширим алфавит, введя символ «*», т.е. . Будем заменять единицы блока метками «*» следующим образом.

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

A\Q
λ						‑	‑	‑
*	‑	‑	‑	‑		‑	‑	‑

2. Проверим работу алгоритма над изображением набора переменных . Применим эту машину к слову 11λ11. Вот последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация — стандартная начальная):

Нетрудно заметить, что данная машина Тьюринга перерабатывает исходное слово в слово , т.е. .