Машина Тьюринга.

 

В 1936 г. английский математик Алан Тьюринг опубликовал статью «О вычислимых числах», в которой для уточнения понятия алгоритма использовал абстрактную математическую конструкцию, впоследствии названную машиной Тьюринга.

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

 

 

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

1. он заставляет головку прочитать букву, которая находится на ленте под головкой;

2. в зависимости от прочитанной буквы и того состояния, в котором находится он сам, логический блок может:

a записать на ленте в той клетке, находящейся под головкой, некоторую букву;

b передвинуть ленту влево, вправо или оставить на месте;

c изменить свое собственное состояние;

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

Итак, мы имеем:

1. некий алфавит Р={р_о,…, p_i, ..., р_n}, содержащий буквы, которые могут быть записаны на ленте. Этот алфавит называется алфавитом машины Тьюринга;
2. алфавит А={a₁, a₂, …, a_m}, содержащий состояния, в которых может находиться логический блок;
3. алфавит D={d_-1, d₀, d1}, предназначенный для обозначения движения ленты влево или вправо и остановки ленты.

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

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

Если головка читает букву p_i, и блок находится в состоянии a_i, то поведение машины определяется записью p_xd_ya_z, которая соответствует командам:

~ записать на ленте вместо буквы p_i букву р_х;

~ совершить перемещение ленты d_y;

~ перейти логическому блоку в состояние a_z.

Очевидно, что от реакции на сочетание p_i, a_j для i≠j будет зависеть работа машины Тьюринга. Реакцию машины на сочетания p_i, a_j можно представить в виде таблицы, в клетках которой стоят тройки символов вида p_xd_ya_z.

	a1	a2	…	az	…	am
p0
p1
…
px				pxdyaz
…
pn

 

Если записать на ленте некоторое слово в алфавите Р и нажать кнопку запуска, то в результате работы машины возможны два исхода:

~ работа машины после конечного числа шагов прекратится. При этом слово, записанное на ленте, будем называть результатом ее работы, т.е. машина применима к исходным данным;

~ машина никогда не остановится, т.е. результат: машина никогда не выдаст и не применима к исходным данным.

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

Пусть задана функция f(x)=х+1, при х≥0. Построить машину Тьюринга, реализующую эту функцию.

Решение:

1) введем условные обозначения и определим исходное состояние ленты:

a) значения х будем записывать на ленте в виде строки, состоящей из единиц, а пустые клетки будем обозначать нулями;

b) расположим ленту так, чтобы самая левая единица находилась под головкой;

c) переведем логический блок в исходное состояние a_i;

2) проанализируем работу логического блока:

a) если в состоянии a_i головка считает символ 1, то нужно, чтобы логический блок снова записал в эту ячейку 1, ленту продвинул на одну позицию влево и сам остался в прежнем состоянии a_i;

b) если в состоянии a_i головка считает символ 0, то логиче­ский блок должен записать в эту ячейку 1, ленту оставить в этой же позиции и сам перейти в состояние а₂;

c) находясь в состоянии a₂ и при считывании головкой символа 1, логический блок должен снова записать в эту клетку 1, ленту не перемещать и оставаться в состоянии а₂. При этом машина остановится;

3) построим функциональную таблицу машины Тьюринга, вычисляющей значение функции f(х)= х+1, при х≥0:

	A1	a2
	1d0a2
	1d1a1	1d0a2

4) проиллюстрируем работу машины Тьюринга при х =2:

a) в исходном состоянии машина Тьюринга имеет вид:

 

…

…

a1

 

b) после первого шага машина Тьюринга перейдет в состояние:

…

…

 

	a1

 

c) после второго шага машина Тьюринга перейдет в состояние:

…

…

 

 

d) после третьего шага машина Тьюринга перейдет в состояние:

…

…

 

 

e) после четвертого шага произойдет остановка машины, и на ленте будет записано значение функции в виде соответствующего числа клеток, заполненных символами 1.

 

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

Основной тезис Тьюринга можно сформулировать следующим образом: «Для любой вычислимой функции можно построить машину Тьюринга, реализующую эту функцию».