Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

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

Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как "проблему разрешимости" - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.

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

Основные определения.

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

1. Управляющее устройство, которое может находиться в одном из множества состояний, образующих конечное множество Q.

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

3. Устройство обращения к ленте, т.е. записывающую-считывающую головку, которая в каждый момент времени обозревает одну ячейку ленты, и в зависимости от символа, находящегося в этой ячейке, и состояния управляющего устройства записывает в ячейку символ, возможно, совпадающий с прежним или пустой (т.е. стирает символ при считывании), сдвигается на ячейку вправо или влево или остается на месте. При этом управляющее устройство переходит в новое состояние (или остается в старом).

В множестве состояний управляющего устройства выделяются начальное состояние q₁ и заключительное состояние q₀, попав в которое машина останавливается.

Лента разбита на ячейки. Во всякой ячейке в каждый дискретный момент времени находится один символ алфавита А={a₀,a₁,a₂,...,a_n}, n ³ 1. В множестве символов алфавита выделяют пустой символ. Любая ячейка, содержащая пустой символ, называется пустой ячейкой. В качестве пустого символа обычно используется L. В некоторых случаях различают входной и выходной алфавит. Говорят, что рабочий алфавит А_раб есть объединение А_раб=А_inÈA_outÈ{L}, где А_in - входной алфавит, A_out - выходной алфавит.

Лента предполагается потенциально неограниченной в обе стороны. Это следует понимать так, что в любой момент лента может быть продолжена в любую сторону, хотя в каждый данный момент она конечна.

Управляющее устройство в каждый момент находится в некотором состоянии q_j Î Q_, Q₌{q₀,q₁,q₂,...,q_r-1}. Множество Q называется внутренним алфавитом или множеством внутренних состояний. Иногда в Q выделяются подмножества Q₁ и Q₀ начальных и заключительных состояний соответственно. Предположим, что r>1, и в множестве состояний имеется одно начальное состояние q₁ и одно заключительное состояние q₀.

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

Работа управляющего устройства описывается тремя функциями:

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

(q_i,a_j, G(q_i,a_j ),F(q_i,a_j),D(q_i,a_j)). (2.1)

или короче (q_ia_jq_ija_ijd_ij). Эти пятерки называются командами.

В общем случае функции G, F, и D являются частичными, т.е. не для всякой пары вида (q_i,a_j) определена соответствующая пятерка вида (2.1). Список всех пятерок, определяющих работу машины Тьюринга, называется программой машины Тьюринга. Программу часто задают в виде таблицы, Табл. 13.

Если в программе для пары (q_i,a_j) пятерка вида (2.1) отсутствует, то в таблице на пересечении строки и столбца ставится прочерк.

Таблица 13Табличное задание программы машины Тьюринга

Q   A	q0	qi	qr-1
a0		. . .
aj	...	(qij,aij,dij)	...
an-1		. . .

Работу машины Тьюринга удобно описывать на языке конфигураций. Пусть в некоторый момент самая левая непустая ячейка c₁ содержит символ а_i1, а самая правая непустая ячейка c_s, s³2, содержит символ a_is (между ячейками c₁ и c_s находятся v ячеек). В этом случае говорят, что на ленте записано слово Р= (a_i1,a_i2,...,a_is), где a_ip - символ, содержащийся в этот момент в ячейке c_p, 1£ p £ s. При s=1, т.е. когда на ленте записан один непустой символ, Р=a. Пусть в этот момент управляющее устройство находится в состоянии q_i и головка обозревает пустую ячейку, расположенную слева или справа от слова Р, и между этой ячейкой и первой (соответственно последней) ячейкой слова Р расположено v пустых ячеек. Конфигурацией машины в этот момент является слово

Здесь L - пустой символ алфавита А.

Если в некоторый момент лента пуста, то конфигурацией машины будет слово q_i L.

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

Зоной работы машины Т на слове Р называется множество всех ячеек, которые за время работы машины хотя бы один раз обозреваются головкой.

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

Если Р₁ - исходное слово, то машина Т, начав работу на слове Р₁ , либо остановится через определенное число шагов, либо никогда не остановится. В первом случае говорят, что машина Т применима к слову Р₁ и результатом работы машины над словом Р₁ является слово Р, соответствующее заключительной конфигурации, что обозначается как Р=Т(Р₁). Во втором случае говорят, что машина Т не применима к слову Р₁. Если какой-либо символ а алфавита встречается в слове Р подряд к раз, то этот фрагмент слова будем записывать как а^К.

Если в некоторый момент времени конфигурация машины была К, а в следующий момент К₁, то конфигурация К₁ называется непосредственно выводимой из конфигурации К, что обозначается как К ├ К₁. Если К₁ - начальная конфигурация, то последовательность К₁ ├ К₂ ├ …├ К_m, где любые две рядом расположенные конфигурации связаны отношением непосредственной выводимости при 1£i£m-1, называется тьюринговым вычислением. При этом говорят, что конфигурация К_m выводима из конфигурации К₁ и пишут К₁ ╟ К_m. Если К_m - заключительная конфигурация, то К_m заключительно выводима из К₁. Это записывают: К₁ ╞ К_m.

Пример. Выяснить, применима ли машина Т, заданная программой П, к слову Р. Если применима, то найти результат применения и заключительную конфигурацию. Принять, что пустой символ обозначается 0, q₁ - начальное состояние, q₀ - заключительное состояние.

П:	- обрабатываемое слово.

Последовательность конфигураций, проходимых машиной Т в процессе работы над словом Р, имеет вид:

q₁1³0²1² ├ 1q₁1²0²1² ├ 1²q₁10²1² ├ 1³q₁0²1² ├ 1³0q₂01² ├ 1³0²q₃1² ├

1³0²1q₂1 ├1³0²q₁1² ├1³0²1q₁1 ├ 1³0²1²q₁0 ├ 1³0²1²0q₂0 ├

1³0²1²0²q₃0 ├ 1³0²1²0²q₀0.

Машина Т применима к данному слову Р, и результат работы машины Т над словом имеет вид: Т(1³0²1²)=1³0²1².