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

Машина Тьюринга (МТ) состоит из устройства управления, считывающей головки и бесконечной ленты.

Устройство управления способно принимать некоторое конечное множество состояний.

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

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

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

Пусть x , x ,..., xn 0 1 - символы входного алфавита Х, буквы которого могут быть записаны на ленте.

Символ 0 x отождествляется с нулевым символом. Иногда этот символ обозначается как В и называется пробелом. Считается, что все незанятые ячейки ленты заняты пробелами.

Пусть Q ={q0 q1,,,,, qm}- алфавит внутренних состояний устройства управления МТ. Состояние q0 - начальное состояние. Предполагается, что в исходном состоянии МТ находится в состоянии q0 , а считывающая головка обозревает крайний левый символ входной цепочки.

Пусть I = {l, r, s}- множество инструкций управления движением ленты. Символ l -означает сдвиг ленты на одну ячейку влево ( ← ); r - сдвиг вправо, s – отсутствие движения или остановка ленты. Заметим, что l и r можно употреблять в противоположном значении, если полагать, что лента неподвижна, а движется головка считывания.

МТ условно можно изобразить следующим образом

Ситуацией называется пара q i x j ; q i ∈ Q , x j ∈ X . Очевидно, начальная ситуация

МТ (указанной на рисунке) есть q0 x α. Выражением будем называть конечную после довательность символов в алфавите { , ,..., , , ,..., , , , } 0 1 0 1 x x x q q q l r s n m .

Командой называется выражение одного из следующих типов i k l j q x x q ; i k j q x rq ; i k j q x pq ; i k j q x sq - команда остановки.

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

Кроме того, функционирование МТ можно задавать с помощью так называемых таблиц Айзермана, определяющих отображения δ :Q× X в Q , μ :Q× X в X и

λ :Q× X в I и называемых соответственно таблицами преобразования сигнала, записи ленты и таблицей преобразования перемещения ленты. Эти три таблицы можно объединить в одну обобщенную таблицу.

Конфигурацией называется выражение вида i j k l q x x ...x , в котором i q не может занимать крайней правой позиции.

Конфигурация однозначно определяет работу МТ. Пусть α ,β – конфигурации некоторой МТ z, а Р,R- произвольные последовательности символов на ленте. МТ переходит из α в β (α →β ) в одном из трех случаев

1. по команде i k l j q x x q . В этом случае символ k x в рабочей ячейке заменяется l x , состояние i q заменяется состоянием j q , а лента остается без движения Pq x R i k α = , Pq xlR j β =

2. по команде i k j q x lq . Лента передвигается на одну ячейку влево, состояние q меняется на j q , Pq x R i k α = , P q R j

3. по команде i k j q x rq . Лента передвигается на одну ячейку вправо, состояние i q заменяется на j q , Px q xlR k j α = , Pq x xlR j k β =

Конфигурация α называется заключительной, если не существует такой конфигурации β , что α →β .

Вычислением в МТ называется последовательность конфигураций α ,β ,...,γ ,l , таких что α →β ,…,γ →l , где l - заключительная конфигурация.