15.2. Машина Тьюринга. Описание. Примеры машин

Машина Тьюринга имеет три алфавита:

1. Внешний алфавит с пустым символом -

2. Внутренний алфавит, или алфавит состояний . (Состояние называется заключительным состоянием, - начальным состоянием, состояния рабочими состояниями.)

3. Алфавит сдвигов S = {-1, 0, +1}.

В конструкции машины имеются:

а) бесконечная лента (разбитая на ячейки), предназначенная для раз­мещения бесконечных записей конечных слов над алфавитом А (по одной букве в ячейке);

б) считывающе-записывающее устройство (СЗУ). СЗУ обладает спо­собностью обозревать одну ячейку ленты, считывать букву, записан­ную в ячейке, заносить на место считываемой буквы любую другую из , передвигаться вдоль ленты влево и вправо на одну ячейку;

в) устройство управления (УУ), которое управляет с помощью программы машины ее работой;

г) программа машины, определяющая переходы машины от одной конфигурации к другой.

Под конфигурацией машины понимают пару: слово с отметкой и со­стояние машины.

Словом с отметкой называют слово, записанное на ленте с указанием обозреваемой СЗУ ячейки.

Программа машины - отображение П : , т. е. правило, сопоставляющее любой паре - «буква-состояние» - тройку - «буква-состояние-сдвиг». Так как A, Q - конечны, то программу машины можно задать таблицей (см. табл. 15.1).

Таблица 15.1.

		…		…
…	…	…	…	…	…
…	…	…	…	…	…
Λ

Правила работы машины (правила обращения УУ с программой и СЗУ)

Машина работает дискретно (пошагово). На каждом шаге происходит переход от одной конфигурации к другой. Перед началом работы машина находится в начальной конфигурации: СЗУ обозревает первую букву слова, а машина находится в начальном состоянии . СЗУ считывает букву, находящуюся в обозреваемой ячейке. УУ обращается к программе машины: находит клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка , тогда буква а заносится в обозреваемую ячейку, машина переводится в состояние q, а СЗУ совершает сдвиг на одну ячейку влево, если , на одну ячейку вправо, если s = +1, и остается на месте, если . На этом завершена работа машины на первом шаге, и она готова к выполнению следующего аналогичного шага и т. д.

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

Если и - исходное слово, Т - машина, то через Т(и) обозначается результат применения машины Т к слову и.

Определение 15.6. Говорят, что машина Т не применима к слову и, если в процессе применения ее к слову она ни на каком из шагов не приходит в заключительное состояние.

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

Напомним, что 5₁₀ = | | | | | _унарн. Рассмотрим алфавит . Необходимо построить машину Т, удовлетворяющую условию: Т((т)_унарн. + (п)_унарн.) = (т + п)_унарн. Ясно, что такая машина определяется следующей программой:

|
+
Λ

Замечание 15.1. Условимся составлять программы так, чтобы «останов» происходил на первой букве результата.

Замечание 15.2. В программе могут быть пустые клетки. Можно считать, что при выходе на такие клетки происходит «останов» (т.е. что внутри таких клеток написаны тройки, содержащие заключительное состояние).

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове | | + | | |. При записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой ячейкой.

0)		8)
1)		9)
2)		10)
3)		11)
4)		12)
5)		13)
6)		14)
7)

Пример 15.4. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.

Расширим исходный алфавит А = {|} до А' = {|, α}. Искомую машину построим в алфавите . Ясно, что программа такой машины может выглядеть так:

|
α
Λ

Применим полученную машину к слову | |.

0)		5)		10)
1)		6)		11)
2)		7)		12)
3)		8)		13)
4)		9)		14)
				15)

Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q₁ обеспечивает замену | на α, состояние q₂ обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружен, q₃ обеспечивает дописывание | в случае, когда произошла замена α на |.

Введем в рассмотрение стандартные машины:

1. Тождественная машина Е - применима к любому слову над алфавитом А и Е(и) = и.

2. Пусть А - алфавит и , . Копирующей машиной называется машина, применимая к любому слову и над А, причем

3. Пусть А - алфавит и . Машиной, заменяющей α на β, называется машина , применимая к любому слову и так:

4. Пусть А - алфавит и . Машиной-проектором называют машину, применимую к любому слову , где и, v - слова над алфавитом А, причем

; .

Теорема 15.3. Тождественная, копирующая, заменяющая машины и машины-проекторы существуют.