Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
перемещать ленту влево или вправо на одну ячейку.
Машина Тьюринга работает следующим образом: в каждой ситуации, определенной внутренним состоянием управляющего устройства и символом, прочитанным на ленте, машина срабатывает,70
Часть /. Предварительные сведения из логики и алгебры
переходя в другое состояние и передвигая ленту определенным образом. Это делается в соответствии с правилами перехода, которые указывают, как должна действовать машина в каждой заданной ситуации.
Уточним теперь (следуя Мартину Дэвису) представление о функционировании машин Тьюринга.
4.2.2. Формальное описание
Символы, которые машина читает и пишет на ленте, мы будем
обозначать через S0, Sj.....Sn; они образуют алфавит машины.
S0 интерпретируется как «пустой символ»; он играет особую роль: считается, что этот символ записан в каждой пустой ячейке, и, обратно, если в ячейке записан символ S0, то она пуста. Мы будем писать вместо S0 также В или ф. Заменить Si на So означает стереть Si.
Вместо Si мы часто будем писать «1» (единицу) или «|» (палочку).
Внутренние состояния (т. е. состояния управляющего устройства) будут обозначаться через
<7ь <72. <7з. • • •;
любая конкретная машина Тьюринга обладает конечным числом таких состояний.
Символы Я и JI будут означать смещение ленты на одну ячейку вправо или влево соответственно 1J.
Дадим теперь несколько определений.
(1) Выражением называется конечная последовательность символов в алфавите (S0, Si, ...; qi, qz, ...; П, JI).
(2) Командой называется выражение одного из трех следующих типов:
qi S/ Sk qu Qi Si П qu Яі S1 Л qt.
(3) Машиной Тьюринга называется конечное множество команд, имеющих попарно различные начальные пары символов.
Л П
[ в S01 Sp Sf — Sx Sft В В
— Голобка
Управляющее j/cmpoucmSo
') N3 : В литературе символы П и Jl часто употребляются в значениях, противоположных принятым здесь. Это связано с тем, что вместо перемещения ленты можно говорить о перемещении головки. — Прим. ред.Гл. IV. Алгоритмы. Машины Тьюринга
71
Работа машины Тьюринга. С помощью только что приведенных определений работа машины Тьюринга может быть теперь описана точно.
.Начальная пара некоторой команды задает исходную ситуацию• машина находится в состоянии q% и читает символ Sj-. .. Поведение машины в данной ситуации qtSj полностью определяется заключительной парой символов той единственной команды, которая соответствует этой ситуации (т. е. начинается парой символов qiSj). При этом элементарные действия машины бывают одного из следующих трех типов:
Тип SftQi' машина заменяет Sj на Sh и переходит из состояния qi в состояние qi.
Тип TJqi. машина сдвигает ленту на одну ячейку вправо и переходит из состояния qi в состояние qi.
Тип Jlqi-. машина сдвигает ленту на одну ячейку влево и переходит из состояния <7і в состояние qi.
Напомним, что на множество команд, задающих машину Тьюринга, наложено требование, чтобы начальные пары символов всех команд были различны. В силу этого требования в любой данной ситуации возможно не более чем одно очередное элементарное действие. Машину, для которой это требование выполнено, мы назовем детерминированной. Машину, для которой указанное требование не соблюдается, т. е. в некоторой ситуации она имеет право «выбирать» между несколькими разными элементарными действиями, мы будем называть недетерминированной.
Сформулируем еще одно определение.
(4) Конфигурацией называется выражение, удовлетворяющее следующим условиям: . оно не содержит вхождений символов П И Л) .. оно содержит ровно одно вхождение символа типа qr, ... это вхождение символа qt не занимает в выражении крайней правой позиции.
Так, выражения
Iq3SiBS2BBSl
и
q*B 1
являются конфигурациями, а выражения
Лqu IS2, qiB StfiSh S1Stfl
таковыми не являются.
Пусть а — некоторая конфигурация. Будем говорить, что а есть конфигурация некоторой машины Тьюринга Z, если состояние qt, фигурирующее в а, является одним из внутренних состояний машины Z, а все остальные символы, входящие в а, принадлежат алфавиту Z.72
Часть /. Предварительные сведения из логики и алгебры
Конфигурация машины однозначно задает ее поведение1). В самом деле, характеристика ситуации не учитывает всю совокупность символов, записанных на ленте; конфигурация же позволяет сделать это.
Конфигурация, из которой выброшено qu характеризует содержимое ленты; в то же время, если S3-— символ, стоящий в конфигурации справа от qi, то qiSj есть ситуация машины Z. Дадим теперь последнее определение.
(5) Пусть а и ? — конфигурации некоторой машины Z. Мы будем писать
а —> ?
в одном из трех следующих случаев (Р и Q обозначают произвольные последовательности символов алфавита машины):
ЭР, Q]:a = PqiSjQ, ? = PqiSkQ, машина имеет команду qtSjSkqi, ЭР, Q:a = PqiSiQ, ? = PSiqiQ, машина имеет команду qtSjJIqi, ЭР, Q:a = PSkqtSiQ,$ = PqiSkSjQ, машина имеет команду q^flqt.
. Первый случай соответствует такому элементарному действию машины, при котором она заменяет символ Sj символом Sh и переходит из состояния qi в состояние qu