2.2. Построение машины Тьюринга

2.2.1. Вычисления на машине Тьюринга

Машина Тьюринга [5] – это автомат A={X, Q, f, ₁, ₂, q₁}, где Х – множество символов, которые могут быть записаны в ячейках ленты; Q - множество состояний, в которых может находиться автомат; q_t=f(q_i, x_j) - функция переходов автомата в новое состояние q_t в зависимости от текущего состояния q_i и считанного из текущей ячейки ленты символа x_j ; x_k=₁(q_i, x_j) - функция выходов автомата, которая определяет, какой символ x_k  будет записан в текущую ячейку ленты в зависимости от текущего состояния автомата q_i и считанного значения x_j ячейки ленты; z_l=₂(q_i, x_j) - функция выходов, определяющая направление передвижения головки вдоль ленты u{R, L, S}, где R (L) - команда сдвига вправо (влево) на одну ячейку, S - команда стоять на месте; q₁Q - начальное состояние автомата.

14

Анализ схемы алгоритма

Отметим, что групповой операции, например GR1(0), соответствует такая строка в ФС: q_i: х х q_j; 1 R q_i (в ячейке (q_i, 0) описываются действия х х q_j, следующие за групповой операцией; последнее действие означает безусловный переход на метку q_j). Аналогично записываются строки и для других операций (они описаны в подразд. 2. 2. 2).

Итак, ФС для функции у=а.0.а имеет следующий вид (табл. 2.4); в начальном состоянии головка МТ всегда обозревает “1”.

Таблица 2.4

М2	0	1
q1	L q2	R q1
q2	-	0 R q3
q3	R q4	R q3
q4	1 L q5	R q4
q5	L q6	L q5
q6	1 L q7	L q6
q7	R !	0 R q3

В табл. 2.5 и 2.6 приведены результаты работы машины М2 для различных исходных данных (Т - такты, Q - состояния). Здесь жирным шрифтом выделены значения инвертированных символов на ленте; в табл. 2.6, кроме того, объединены такты с неизменным состоянием, а фрагменты ситуации на ленте усечены до минимума.

Пример 2.4

Постановка задачи. Построить МТ в алфавите X={0, 1, #}, где # - сигнал об аварийном завершении работы, вычисляющую разность двух натуральных чисел у=а-b (a, b ). Предусмотреть случай a<b, когда разность не определяется, но выдается сигнал # об аварийном завершении работы МТ. Сохранение исходных чисел и очистка ленты до и после результата не предусматриваются.

В этом примере приведём только схему алгоритма и ФС построенной МТ.

Схема алгоритма представлена на рис. 2.5, а её ФС - в табл. 2.7, в которой для упрощения опущен столбец, соответствующий символу “#”, так как для этой МТ символ “#” является только выходным.

23

Анализ словесного описания алгоритма

Ясно, что МТ должна выполнять простые (R, L) и групповые (по условию наличия 1 в текущей ячейке - GR1(0), GL1(0)) операции сдвига головки, а также операции инвертирования содержимого текущей ячейки - INV. Кроме того, требуется операция проверки «z=0?» для нахождения левого разделителя числа a’. Операция GR1(0) выполняется в пп. 1, 3, 5; операция GL1(0) выполняется в пп. 7, 9 словесного описания. Множество используемых символов: X={0,1}; очевидно, что дополнительные символы не требуются.

Рассмотренных операций и знания их последовательности достаточно для построения схемы алгоритма (рис. 2.4).

22

Работа машины Тьюринга (МТ) описывается функциональной схемой, предcтавляющей собой двухмерную таблицу размерностью mхn (n – мощность множества X, m - мощность множества Q), в каждой ячейке которой содержится тройка символов: (x_k, u, q_t). Функциональную схему (ФС) можно рассматривать как программу МТ, где каждая строка соответствует команде выбора по условию. В зависимости от символа, который обозревает головка, выбирается то или иное продолжение программы, включающее три действия: записать в текущую ячейку ленты значение x_k , сдвинуть головку в направлении u, перевести автомат в новое состояние q_t (безусловный переход на метку q_t - на строку, соответствующую состоянию q_t).

Автомат МТ может быть полностью или частично детерминированным. В первом случае ФС автомата заполнена полностью, во втором - ФС может содержать пустые ячейки: если текущая ячейка на пересечении строки q_t и столбца x_k, пуста, то в некотором состоянии q_t никогда не может быть прочитан символ x_k.

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

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

Выполнение задания состоит в описании ФС для созданной МТ. Областью определения и областью значений вычисляемой функции являются положительные целые числа, записанные на ленте МТ.

Удобна следующая кодировка используемых на ленте чисел: число n представляется n+1 расположенными подряд в ячейках символами “1” (число 0 - “1”, число 1 - “11”, число 2 - “111” и т. д.), числа на ленте разделяются ячейками с символом “0” (пустая ячейка).

Определение 1. МТ начинает работать при следующих условиях:

1. МТ находится в начальном состоянии q₁ Q;

2. На ленте представлена последовательность m чисел (n₁, n₂,,..., n_m):

3. Все ячейки ленты справа и слева от заданной последовательности чисел пусты (содержат символы “0”);

15

4. Программист знает, какую ячейку ленты обозревает головка автомата в начальном состоянии.

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

Определение 2. Машина Тьюринга вычисляет функцию y=f(n₁, n₂, ..., n_m ) от m переменных, если для любых n₁, n₂ ..., n_m существует такой момент времени, что:

• МТ достигнет состояния останова (! - его обозначение);

• на ленте будет получен результат вычисления функции y=f (n₁, n₂, ... , n_m) (соответствующее числу у количество единиц; справа эта последовательность ограничена пустыми ячейками);

• головка обозревает первую единицу числа у.

В качестве дополнительных условий при построении МТ могут быть указаны такие требования:

• сохранение на ленте исходной последовательности чисел, т.е. в результате работы МТ на ленте будет представлена система чисел (n₁, n₂, ... , n_m, у);

• возвращение головки в стандартное положение;

• все ячейки, расположенные левее и правее результата работы МТ, пусты (содержат символ “0”).

Например, нужно вычислить функцию y=n₁+n₂+n₃. При начальных условиях лента выглядит следующим образом: q₁ ... 011101111011000...

На ленте записаны числа 2, 3, 1; головка находится в стандартном положении. Обозначение текущего состояния автомата помещается перед последовательностью символов на ленте, а указателем положения головки является подчёркивание символа в текущей ячейке ленты. Такое пред-ставление ситуации на ленте в совокупности с указанием состояния МТ называют её конфигурацией.

16