Управляющие и вычислительные состояния

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

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

1. Двигаться вправо, пока не встретиться пустой символ.

2. Сдвинуться на одну ячейку влево.

3. Пока в текущей ячейке находится '1', заменять его на '0' и двигаться влево.

4. Если в текущей ячейке находится '0' или 'blank', записать в ячейку '1' и завершить работу.

На рис. 1.6 представлен граф переходов управляющего автомата машины Тьюринга, реализующей функцию инкремент. Здесь символ ‘b’ – сокращение от blank, символ ‘*’ на месте записываемого символа означает «записать тот же самый символ, который был считан». Команды головке обозначаются стрелками (стрелка вниз означает «остаться на месте»).

Увеличение числа на единицу с помощью машины Тьюринга

Отметим, что в графе переходов обозначены имена состояний управляющего автомата. Эти имена отражают смысл состояния и являются кратким описанием поведения машины в этом состоянии.

Итак, управляющий автомат машины Тьюринга, реализующей функцию инкремент, имеет три состояния. Сколько же состояний у этой машины в целом? Ее действия в каждый момент времени полностью определяются совокупностью состояния управляющего автомата, строки на ленте и положения головки. Отметим, что символы на ленте для устройства управления представляют собой входные воздействия, однако, относительно машины в целом они не являются входными (внешними), а формируют часть внутреннего состояния вычислителя. Всевозможных строк на ленте, как и положений головки, бесконечно много, поэтому и у машины Тьюринга бесконечное число состояний.

Машина Тьюринга

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

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

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

Понятия управляющих и вычислительных состояний применимы не только к машине Тьюринга, но и к любой сущности со сложным поведением. Однако, если в машине Тьюринга отличить управляющие состояния от вычислительных не составляет труда (поскольку она по определению состоит из устройства управления и ленты), то для произвольной сущности явное выделение управляющих состояний – сложная задача. Причина сложности состоит в том, что различия между управляющими и вычислительными состояниями в общем случае трудно формализовать. Неформально основные различия сформулированы в таблице.

Управляющие и вычислительные состояния

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