Правила работы машины

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

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

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

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

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

Пример. Дана машина Тьюринга, складывающая натуральные числа, записанные в унарной системе счисления (напомним, что, например 5₁₀=+||_унар). Программа этой машины задана таблицей:

Рисунок 18.1.

алфавит	q1	q2	q3
|	| q1+1	q3-1	| q3-1
+	| q1+1
	q2-1		q0+1

Выписать последовательно возникающие при работе этой машины конфигурации на исходном слове И=+|| (т.е. мы будем складывать два числа: 2 и 3).

Как видно из таблицы, у машины четыре состояния q₀; q₁, q₂, q₃ внешний алфавит состоит из трех символов | - единица; + - сложение; - пустой символ.

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

Изобразим схематично ленту для записей и слово И=+||, записанное на ней, стрелкой обозначено СЗУ, рядом со стрелкой - состояние машины.

Рисунок 18.2.

|

|

+

|

|

|

↑(q₁)

Перед началом работы машины СЗУ обозревает первую букву ячейки. УУ обращается к программе: буква |, состояние q₁ - переводит букву | в букву |, состояние q₁ переводит в состояние q₁ и делает шаг вправо (+1).

Рисунок 18.3.

|

|

+

|

|

|

↑(q₁)

СЗУ обозревает вторую ячейку. УУ обращается к программе: буква |, состояние q₁ переводит | в |, q₁ в q₁ и делает шаг вправо (+1).

Рисунок 18.4.

|

|

+

|

|

|

↑(q₁)

буква +, состояние q₁ - переводит + в |, q₁ в q₁ и +1.

Рисунок 18.5.

|

|

|

|

|

|

↑(q₁)

буква |, состояние q₁ - переводит | в |, q₁ в q₁ и +1.

Рисунок 18.6.

|

|

|

|

|

|

↑(q₁)

|

|

|

|

|

|

↑(q₁)

|

|

|

|

|

|

↑(q₁)

буква , состояние q₁ - переводит в , состояние q₁ в q₁ и -1.

Рисунок 18.7.

|

|

|

|

|

|

↑(q₂)

буква |, состояние q₂ - переводит | в , состояние q₂ в q₂ и -1.

Рисунок 18.8.

|

|

|

|

|

↑(q₃)

буква |, состояние q₃ - переводит | в |, q₃ в q₃ и -1.

Рисунок 4.1.9.

|

|

|

|

|

↑(q₃)

|

|

|

|

|

↑(q₃)

|

|

|

|

|

↑(q₃)

|

|

|

|

|

↑(q₃)

|

|

|

|

|

↑(q₃)

буква , состояние q₃, - переводит в , q₃ в q₀.

Рисунок 18.10.

|

|

|

|

|

↑(q₀)

Машина пришла в заключительное состояние q₀.

Результат работы машины:

Т(И) = Т(|| +) =

Nbsp;

Дата добавления: 2015-07-07