8. Машина Тьюринга. Другой стандартной формой представления любого алгоритма являются функциональные схемы, реализуемые в машинах Тьюринга (рис. 258). Слова, перерабатываемые в данном алфавите {ξ1, ξ2, ..., ξm}, называемом внешним алфавитом машины, изображаются в ячейках неограниченной ленты (НЛ), причем в каждой в ячейке может храниться только один символ.
Работа машины происходит в дискретном времени. На каждом такте обозревается единственная ячейка и считываемый символ ξi заменяется другим ξj (i = j означает, что символ не изменяется), который определяется состоянием машины sk в данный тактовый момент из множества ее возможных состояний {s1, s2, ..., sn}. Кроме того, вырабатывается последующее состояние машины и команда, управляющая перемещением по ленте, которая подготавливает очередную ячейку для обозрения на следующем такте. Таких команд в машине Тьюринга только три: П — обозревать соседнюю справа ячейку, Л — обозревать соседнюю слева ячейку и Н — продолжать обозревать прежнюю ячейку. Совокупность {s1, s2, ..., sn} и {П, Л, Н} образует внутренний алфавит машины.
Функциональная схема, соответствующая какому-либо алгоритму, задается подобно общей таблице переходов конечного автомата (6.4) с некоторыми несущественными отличиями. Обычно строки таблицы соответствуют символам внешнего алфавита ξ1, ξ2, ..., ξm, а столбца — состояниям машины s1, s2, ..., sn. В каждой клетке записывается тройка символов, обозначающих замещающих символ из внешнего алфавита, управляющую команду и последующее состояние. Например, функциональная схема, соответствующая алгоритму сложение (числа представляются совокупностью единиц или просто «палочек», общее количество которых равно данному числу, причем они расположены в ячейках без пропусков) имеет вид:
Знак «!» используется для обозначения стоп-состояния, при наступлении которого процесс останавливается и результирующее слово считывается по ленте, а через ∧ обозначается пустой символ.
Функциональная таблица полностью определяет функционирование машины и реализуется в ней логическим блоком (ЛБ). На
- 628 -
два его входа подаются считываемые символы, над которыми совершаются операции (замена другими символами), и состояния, играющие роль команд, определяющих эти операции. На одном из выходов логического блока образуется символ, который в данном такте замещает на ленте обозреваемый символ, а на остальных двух выходах — команды, определяющие функционирование машины на следующем такте (перемещение по ленте и новое состояние). Для запоминания этих команд вводятся задержки З1 и З2 представляющие собой внутреннюю память машины.
Перед началом работы на ленту наносится исходное слово и задаются начальные условия, т.е. указывается первая обозреваемая ячейка и начальное состояние. После пуска машины процесс преобразования информации происходит автоматически.
Рис. 258. Машина Тьюринга.
Пусть, например, требуется сложить числа 4 и 6. исходное слово на ленте запишется в виде 1111+111111. В соответствии с приведенной выше схемой сложения начальные условия определяются ячейкой с крайней левой единицей и состоянием s1. На первом такте единица стирается, выдается команда сдвига вправо и перехода в состояние s3(∧Пs3 ). Последующие такты сводятся к сдвигам направо сквозь все единицы (1Пs3 ) и знак + (+Пs3 ) до тех пор, пока не будет достигнута первая пустая ячейка. Тогда в эту пустую ячейку вписывается единица и машина переходи в состояние s2 (1Нs2) При состоянии s2 происходят сдвиги в обратном направлении через все символы 1 и + до первой пустой ячейки слева. После этого происходит сдвиг вправо, левая крайняя единица стирается, и машина переходит в состояние s1 (∧Пs1). В результате этого цикла единица левого слагаемого оказалась перенесенной в правое слагаемое, что соответствует слову 111+1111111 (сумма не изменяется). Очевидно, через четыре таких цикла исходное слово преобразуется к виду +1111111111. К началу пятого цикла обозревается символ + при состоянии s1, который стирается и происходит остановка (∧Н!). В результате получим слово 1111111111, соответствующее числу 10.
Описанные машины Тьюринга являются специализированными: каждому алгоритму соответствует своя машина. Рассматривая функциональную схему как описание программы, можно прийти к понятию универсальной машины Тьюринга, которая реализует