13.5.Машина Тьюринга
Вне зависимости от модели, вычисление функций подразумевает символьную запись набора исходных данных и также символьную запись императива преобразования этих данных.
В случае нормального алгоритма Маркова, в качестве набора исходных данных выступает слово P в алфавите A, а императивом преобразования P в Q служат правила подстановки, специфичные для каждого алгоритма.
В случае рекурсивных функций, набором исходных данных служат символьные записи значений функции, а императивом преобразования служит набор операций (подстановок, определения по индукции и минимизации) специфический для каждой функции.
Обратим внимание, что, как для записи алгоритма Маркова, так и для записи рекурсивной функции необходим исполнитель, реализующий императивы, содержащиеся в этих записях. Кроме того, изящные теоретические конструкции, как в первом, так и во втором случае чрезвычайно сложны в их практической реализации при массовом решении конкретных прикладных задач. Следствием этого является факт использования алгоритмов Маркова и формализма рекурсивных функций только на теоретическом уровне, но не для инженерной реализации автоматических вычислителей.
Существенный шаг по направлению создания технических средств автоматизации вычислений сделал Алан Тьюринг, предложив в 1936-м году концепцию машины преобразования данных, которая известна как "машина Тьюринга".
Машина Тьюринга - очень простое вычислительное устройство. Она имеет ленту бесконечной длины, разделенную на ячейки. Лента может двигаться влево и вправо, сдвигаясь на одну ячейку за один шаг. Каждая ячейка может быть пустой или содержать символ, выбираемый из некоторого конечного алфавита. Также машина Тьюринга имеет головку, которая в каждый момент времени может читать и изменять содержимое доступной ячейки.
Рис. 49. Машина Тьюринга
В каждый момент времени машина находится в одном из возможных состояний, которое представляется целым числом q0 qMax. Одно из состояний, как правило, состояние q1, определяется как исходное состояние, также определяется состояние останова, как правило, q0.
Поведение машины определяется устройством управления, которое функционирует на основании таблицы управления. Таблица управления определяет действия, которые будет выполнять машина в текущий дискретный момент времени.
Действие, которое совершает машина в текущий дискретный момент времени, зависит только от текущего состояния машины и символа в доступной ячейке, который считывает головка машины. На основе этой информации (состояния и считанного символа), машина Тьюринга может выполнить одно из трех действий:
записать символ в ячейку (возможно тот же самый, который в ней уже находился );
оставить ленту на месте или передвинуть ее на одну ячейку вправо - влево;
перейти в следующее состояние (возможно, то же самое, в котором машина находится в данный момент).
Для решения каждой конкретной задачи создается конкретная управляющая таблица, пример которой приведен на (Рис.50).
|
q0 |
q1 |
q2 |
0 |
0,q0,С |
0,q1,П |
1,q0,С |
1 |
1,q0,С |
0,q2,П |
1,q2,П |
+ |
- |
- |
1,q0,С |
Рис. 50. Пример управляющей таблицы
В боковике таблицы записываются символы алфавита, в шапке таблицы записываются допустимые состояния машины. В каждом поле таблицы записывается команда, формат которой приведен ниже:
<символ, заменяющий текущий символ на входной ленте>,<следующее состояние машины>,<движение ленты: Лево, Право, Стоп>
Устройство управления в каждый дискретный момент времени считывает символ из доступной ячейки входной ленты, и выполняет команду, записанную в поле [<текущий символ>, <текущее состояние>] управляющей таблицы.
Приведенная на рис.50 управляющая таблица записана для решения задачи сложения двух натуральных чисел. Числа представляются в примитивной системе счисления.
Семантика состояний машины приведена ниже:
q0 - состояние останова;
q1 - считывались только нули;
q2 - считана хотя бы одна единица.
Императив движения ленты обозначается как: П – движение на одну ячейку вправо, Л – движение на одну ячейку влево, С – оставить ленту на месте.
Команды машины интерпретируются следующим образом:
["0",q1]: <0,q1,П> – пропускает "0" перед записями чисел;
["1",q1]: <"0",q2, П> - первая единица убирается, так как где - то следом должен быть +;
["0", q2]: <"1",q0,C> - второго числа нет, останов.
["1",q2]: <"1",q2,П> - пропускаются единицы до знака сложения;
["+",q2]: <"1",q0,C> - заменяетcя плюс на единицу и машина останавливается.
Две команды столбца qo реализуют динамический останов машины. Две пустые клетки управляющей таблицы – нереализуемые ситуации.
Трассировка процесса сложения двух натуральных чисел на машине Тьюринга приведена ниже.
0 |
0 |
1 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
q1 |
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
|
q1 |
|
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
|
|
q1 |
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
|
|
|
q2 |
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
|
|
|
|
q2 |
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
+ |
1 |
1 |
0 |
0 |
|
|
|
|
|
q2 |
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
q0 |
|
|
|
В настоящее время управляющую таблицу машины Тьюринга записывают на языке графов (Рис.51) в виде графа переходов машины Тьюринга как детерминированного конечного автомата
Рис. 51. Граф переходов для машины Тьюринга
В этом случае дуги определяют направления смены состояний, каждой дуге поставлена в соответствие пара: (текущий символ, команда). Команда, поставленная в соответствие дуге, имеет формат: <записываемый на ленту символ>, <следующее состояние машины>.
Машина Тьюринга может иметь две ленты: входную и выходную. Однако это не расширяет класс решаемых на машине задач.
[Айзерман, Л.А. Гусев и др.Гос. изд-во ф.м. л-ры, М.: 1960]