Математический аппарат инженера

Задается алфавит А и фиксируется в определенном порядке система ориентированных подстановок. Исходя из произвольного слова R в алфавите А, просматриваются подстановки в том порядке, в каком они заданы. Первая встретившаяся подстановка с левой частью входящей в R, используется для преобразования R, в которое вместо первого вхождения ее левой части подставляется ее правая часть, в результате чего получаем новое слово R₁. Далее процесс повторяется, исходя из слова R₁, R₂ и т.д. до тех пор, пока этот процесс не останавливается. Признаками остановки процесса служат два случая: во-первых, когда получается такое слово R_n, что ни одна из левых частей допустимых подстановок в него не входят, и во-вторых, когда при получении R_n приходится применять последнюю подстановку.

Пусть, например, задан алфавит A = {1, +} и система подстановок + → ∧, 1→ 1 (∧ - пустое слово). Слово 111+11+1111+1 этот алгоритм перерабатывает так:

111+11+1111+1

11111+1111+1

111111111+1

1111111111

1111111111

Процесс оканчивается применением заключительной подстановки, которая перерабатывает слово само в себя. Как видим, алгоритм суммирует количество единиц, т.е. осуществляет операцию сложения. Эквивалентный ему алгоритм можно задать с помощью системы подстановок: 1+ → +1; +1→1; 1→1.

- 627 -

В соответствии со смелой гипотезой, основанной на накопленном опыте, предполагается, что любой алгоритм может быть представлен в виде нормального алгоритма Маркова. Иначе говоря, нормальный алгоритм Маркова принимается в качестве стандартной формы любого алгоритма.

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

. Другой стандартной формой представления любого алгоритма являются функциональные схемы, реализуемые в машинах Тьюринга (рис. 258). Слова, перерабатываемые в данном алфавите {ξ₁, ξ₂, ..., ξ_m}, называемом внешним алфавитом машины, изображаются в ячейках неограниченной ленты (НЛ), причем в каждой в ячейке может храниться только один символ.

Работа машины происходит в дискретном времени. На каждом такте обозревается единственная ячейка и считываемый символ ξ_i заменяется другим ξ_j (i = j означает, что символ не изменяется), который определяется состоянием машины s_k в данный тактовый момент из множества ее возможных состояний {s₁, s₂, ..., s_n}. Кроме того, вырабатывается последующее состояние машины и команда, управляющая перемещением по ленте, которая подготавливает очередную ячейку для обозрения на следующем такте. Таких команд в машине Тьюринга только три: П — обозревать соседнюю справа ячейку, Л — обозревать соседнюю слева ячейку и Н — продолжать обозревать прежнюю ячейку. Совокупность {s₁

, s₂, ..., s_n} и {П, Л, Н} образует внутренний алфавит машины.

Функциональная схема, соответствующая какому-либо алгоритму, задается подобно общей таблице переходов конечного автомата (6.4) с некоторыми несущественными отличиями. Обычно строки таблицы соответствуют символам внешнего алфавита ξ₁, ξ₂, ..., ξ_m, а столбца — состояниям машины s₁, s₂, ..., s_n. В каждой клетке записывается тройка символов, обозначающих замещающих символ из внешнего алфавита, управляющую команду и последующее состояние. Например, функциональная схема, соответствующая алгоритму сложение (числа представляются совокупностью единиц или просто «палочек», общее количество которых равно данному числу, причем они расположены в ячейках без пропусков) имеет вид:

Знак «!» используется для обозначения стоп-состояния, при наступлении которого процесс останавливается и результирующее слово считывается по ленте, а через ∧ обозначается пустой символ.

Функциональная таблица полностью определяет функционирование машины и реализуется в ней логическим блоком (ЛБ). На

- 628 -

два его входа подаются считываемые символы, над которыми совершаются операции (замена другими символами), и состояния, играющие роль команд, определяющих эти операции. На одном из выходов логического блока образуется символ, который в данном такте замещает на ленте обозреваемый символ, а на остальных двух выходах — команды, определяющие функционирование машины на следующем такте (перемещение по ленте и новое состояние). Для запоминания этих команд вводятся задержки З₁ и З₂ представляющие собой внутреннюю память машины.

Перед началом работы на ленту наносится исходное слово и задаются начальные условия, т.е. указывается первая обозреваемая ячейка и начальное состояние. После пуска машины процесс преобразования информации происходит автоматически.

Рис. 258. Машина Тьюринга.