Программирование машины Тьюринга, страница 7

¦     ¦    q0    ¦   q1   ¦ 

¦-----+----------+--------¦ 

¦  0  ¦1 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  1  ¦2 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  2  ¦3 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  3  ¦4 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  4  ¦5 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  5  ¦6 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  6  ¦7 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  7  ¦8 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  8  ¦9 Стоп q0 ¦        ¦ 

+-----+----------+--------¦ 

¦  9  ¦0 Влево q0¦        ¦ 

+-----+----------+--------¦ 

¦  ^  ¦1 Стоп q0 ¦        ¦ 

+-------------------------+ 

_1.5 

Выполним данный алгоритм на следующем примере:  увеличим число 

389 на единицу. 

. 

- 13 - 

Внутреннее и внешнее состояние машины Тьюринга перед  выполне-  нием  алгоритма:  обозреваем крайнюю правую цифру - цифру разряда  единиц в состоянии q0. Каретка указывает на ячейку с номером 3. 

Покажем расположение данного числа в машине Тьюринга и ее сос-  тояние к началу выполнения алгоритма. 

_1.0 

_40   1   2   3   4  _45   _4... 

----------------------------- 

¦ ^ ¦ 3 ¦ 8 ¦ 9 ¦ ^ ¦ ^ ¦   ¦ 

----------------------------- 

q0 

_1.5 

Если обозреваемая ячейка содержит цифру отличную от 9,  то Ма-  шина остановится уже после первого такта работы, в котором проис-  ходит замена этой цифры другой цифрой в соответствии  со  схемой. 

Если  же последняя цифра 9,  то машина заменяет ее 0 и производит  сдвиг влево (к соседнему,  более высокому разряду)  и  продолжает  пребывать  в  рабочем  состоянии q0 (таким образом обеспечивается  перенос единицы в более высокие разряды). Если число оканчивается 

k девятками,  то машина закончит работу в точности после k+1 так-  та. 

_23.2. Алгоритм перевода чисел из унарной записи _2в _2десятичную 

Под унарной  записью числа понимаем набор палочек,  количество  которых равно данному числу. 

Дана конечная совокупность палочек,  вписанных в ячейках, взя-  тых подряд без пропусков (такие совокупности будем называть _1набо- 

_1рами палочек); требуется записать в десятичной системе количество  этих палочек. 

_3Функциональная схема: 

_1.0 

+--------------------------+    +--------------------------+ 

¦     ¦  q1  ¦  q2  ¦  q3  ¦    ¦     ¦  q1  ¦  q2  ¦  q3  ¦ 

¦-----+------+------+------¦    ¦-----+------+------+------¦ 

¦  0  ¦ 1Нq3 ¦ 0Сq2 ¦ 0Пq3 ¦    ¦  6  ¦ 7Нq3 ¦ 6Сq2 ¦ 6Пq3 ¦ 

+-----+------+------+------¦    +-----+------+------+------¦ 

¦  1  ¦ 2Нq3 ¦ 1Сq2 ¦ 1Пq3 ¦    ¦  7  ¦ 8Нq3 ¦ 7Сq2 ¦ 7Пq3 ¦ 

+-----+------+------+------¦    +-----+------+------+------¦ 

¦  2  ¦ 3Нq3 ¦ 2Сq2 ¦ 2Пq3 ¦    ¦  8  ¦ 9Нq3 ¦ 8Сq2 ¦ 8Пq3 ¦ 

+-----+------+------+------¦    +-----+------+------+------¦ 

¦  3  ¦ 4Нq3 ¦ 3Сq2 ¦ 3Пq3 ¦    ¦  9  ¦ 0Лq1 ¦ 9Сq2 ¦ 9Пq3 ¦ 

+-----+------+------+------¦    +-----+------+------+------¦ 

¦  4  ¦ 5Нq3 ¦ 4Сq2 ¦ 4Пq3 ¦    ¦  ¦  ¦ 1Нq3 ¦ ¦Сq2 ¦ ¦Лq1 ¦ 

+-----+------+------+------¦    +-----+------+------+------¦ 

¦  5  ¦ 6Нq3 ¦ 5Сq2 ¦ 5Пq3 ¦    ¦  *  ¦ *Лq1 ¦ ¦Лq1 ¦ ¦Пq3 ¦ 

+--------------------------+    +--------------------------+ 

_1.5 

. 

- 14 - 

Если к началу работы машины на ленте будут записаны цифра 0  и  набор из k палочек,  то машина "сотрет" все эти палочки, а вместо  нуля появится десятичная запись числа 0+k, т.е. k. 

Рассмотрим еще некоторые примеры тьюринговых машин для решения  арифметических задач. В этих задачах как исходные данные (условия  задачи), так и результат являются натуральными числами. Условимся  считать, что в машине каждое натуральное число задано в виде  на-  бора из такого же числа палочек; если же в задаче фигурируют нес-  колько натуральных чисел, то изображающие их наборы палочек будем  отделять каким-нибудь специальным знаком.  Этот знак также входит  во внешний алфавит машины.