ГЛАВА XIII. МАШИНЫ ТЬЮРИНГА

§ 13.1. Описание и примеры машин Тьюринга

В гл. XII были разъяснены основные интуитивно очевидные требования, которые предъявляются к алгоритмам. Это требования детерминированности, массовости и применимости («целенаправленности») алгоритмов. Важно, что результат применения алгоритма совершенно не зависит от того, кто его использует. Человек, выполняющий алгоритм, должен действовать, «как машина», заботясь лишь о том, чтобы правильно выполнить предписания. Поэтому, естественно, возникает мысль: нельзя ли действительно поручить выполнение алгоритма машине?

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

Можно предложить различные «конструкции» машин, способных выполнять алгоритмы. Наиболее наглядна схема, предложенная в 1936 г. английским математиком Тьюрингом. Ниже приводится описание одного из возможных вариантов функционирования таких машин

Рассмотрим бесконечную одномерную ленту, которая разделена на ячейки. Мы будем считать, что лента бесконечна лишь в одном направлении — направо, так что существует самая левая ячейка.

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

Представим себе также специальное устройство — считывающую и записывающую головку, которая может располагаться напротив каждой из ячеек ленты и по команде извне «стереть» записанный в этой ячейке символ и записать новый. Считывающая и записывающая головка может также по команде перемещаться на одну ячейку вправо или влево (если она не находится в самой левой ячейке). Команды на считывающую и записывающую головку подаются от управляющего устройства, которое в свою очередь получает от головки сигнал о наличии того или иного символа в ячейке ленты, расположенной против головки.

Управляющее устройство имеет конечное число внутренних состояний и работает в дискретном времени . Входом управляющего устройства являются символы , выдаваемые считывающей и записывающей головкой, выходом — команды на действия головки: какой символ головка должна записать в соответствующей ячейке и куда передвинуться. Пусть в момент времени t считывающая и записывающая головка находилась напротив (считая слева) ячейки, в которой был записан символ , а управляющее устройство находилось в состоянии . Управляющее устройство в зависимости от состояния и входа выдает символ (в соответствии с которым головка стирает старый символ и печатает новый ), а затем один из символов П, Л или С («право»? «лево», "стоп"), в соответствии с которым головка передвигается на одну клетку вправо или влево, или остается на месте. После этого управляющее устройство переходит в новое состояние (также определяемое однозначно символами ).

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

Таблица 13.1

Таблица 13.2

Таблица 13.3

Таблица 13.3

Например, если таблица автомата есть табл. 13.1, таблица первого преобразователя — табл. 13.2, второго — табл. 13.3, то совмещенная таблица, целиком описывающая работу машины Тьюринга, имеет вид табл. 13.4.

В клетках этой таблицы первым записан символ из , вторым — из , третьим из . Если основная таблица машины Тьюринга задана, то при каждом заполнении ленты работа машины однозначно определена.

Далее будем считать, что символ состояния управляющего устройства означает состояние покоя машины Тьюринга, т. е. строка основной таблицы имеет следующие свойства: 1) первым символом в каждой клетке этой строки всегда является (и никогда при

2) вторым символом в клетке столбца этой строки является тот же символ (и никогда при );

3) третьим символом в каждой клетке этой строки является символ С (и никогда П или Л) (см. пример табл. 13.5).

Таблица 13.5

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

Таблица 13.6

Таблица 13.7

Машина А

В дальнейшем для простоты будем предполагать, что алфавит символов состоит всего лишь из двух символов: «пустого» 0 и «непустого» 1.

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

1) Машина А (табл. 13.7). Если в начальный момент машина А находится в состоянии и воспринимает заполненную клетку, то она «отыскивает» на ленте первую пустую (т. е. заполненную символом 0) клетку справа от той, на которой находится головка, «печатает» там символ 1 и останавливается. Если же вначале головка находилась напротив пустой клетки, то машина ее «заполняет» и останавливается, не передвигая головку.

В табл. 13.8 и 13.9 приведены два варианта работы машины.

Таблица 13.8

Черта над соответствующей ячейкой ленты означает, что считывающая и записывающая головка находится в данный момент как раз напротив этой ячейки. Символ над чертой — состояние управляющего устройства в этот момент.

Таблица 13.9

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

2) Машина В (табл. 13.10). Эта машина имеет также лишь одно состояние (не считая состояния покоя). Она «стирает» единицу в той ячейке, где находится головка (если эта ячейка непуста), или в первой слева непустой ячейке, передвигает головку еще левее на ячейку и останавливается. Один вариант работы машины В приведен в табл. 13.11.

Таблица 13.10

Машина В

Таблица 13.11

3) Машина С (табл. 13.12). Эта машина отыскивает первую после группы нулей группу единиц справа от начальной ячейки и останавливается около последней из этих единиц. Вариант работы машины С приведен в табл. 13.13.

Таблица 13.12,

Машина С

Таблица 13.13

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

Таблица 13.14

Машина D

4) Машина D (табл. 13.14). Эта машина заполняет первый промежуток справа между двумя группами единиц, оставляя всего одну незаполненную ячейку. Если головку машины в нулевой такт не помещать напротив пустой ячейки в состоянии , то сочетания и никогда не встретятся и в дальнейшем: состояние вообще никогда не повторится, а в машина может прийти лишь тогда, когда единица уже напечатана. Вариант работы машины приведен в табл. 13.15.

Иногда нам придется рассматривать машины, имеющие не одно, а два или несколько состояний покоя и т. д.). Рассмотрим соответствующий пример.

5) Машина Е (табл. 13.16). Эта машина, находясь в начальном состоянии всегда напротив заполненной ячейки, обнаруживает, что записано в соседней ячейке слева — 0 или 1. В зависимости от этого она переходит в состояние или и останавливается в исходной ячейке.

Два варианта работы машины Е приведены в табл. 13.17 и 13.18.

Таблица 13.15

В заключение параграфа без особых пояснений приведем еще несколько примеров машин Тьюринга. Эти машины понадобятся нам в дальнейшем.

Таблица 13.16

Машина Е

Таблица 13.17

Таблица 13.18

6) Машина F (табл. 13.19). Эта машина отыскивает ближайшую слева группу единиц после группы нулей.

Таблица 13.19

Машина F

Таблица 13.20

Машина G

Таблица 13.21

Машина H

7) Машина G (табл. 13.20). Машина G стирает все единицы слева (если они есть) до ближайшего слева нуля.

8) Машина Н (табл. 13.21). Печатает единицу справа после группы единиц через одну пустую ячейку. Отличается от машины А (пример 1) только тем, что печатает единицу не на первой справа пустой ячейке, а на второй.

9) Машина I (табл. 13.22). Отправляясь от заполненной ячейки, стирает в ней единицу и «переносит» ее в ближайшую пустую ячейку слева (другими словами, «сдвигает» группу единиц левее исходной ячейки на одну ячейку влево).

10) Машина К (табл. 13.23). «Стирает» одну единицу в ячейке, расположенной правее исходной (если там есть единица).

Таблица 13.22

Машина

Таблица 13.23

Машина К

11) Машина L (табл. 13.24). Отправляясь от заполненной ячейки, идет налево и останавливается левее группы единиц на две ячейки.

Таблица 13.24

Машина

Таблица 13.25

Машина М

12) Машина М (табл. 13.25). Имея два состояния покоя, «распознает», напротив какой ячейки находится — пустой или заполненной. В зависимости от этого переходит в первое или второе состояние покоя.