От машины Тьюринга к машине Мили

Итак, мы рассмотрим, почему «потенциал параллелизма» у МТ выше, чем у машины Поста (МП).

Вячеслав Любченко

В предыдущей статье («Мир ПК», № 2/02, с. 150) мы подробно рассмотрели машину Тьюринга (МТ). Там же, коснувшись работы с несколькими головками, имеющими внутренние состояния, был намечен перспективный путь развития МТ — параллельный. Именно ему и посвящена настоящая статья.

Мама, дядя, который ходил

на одной ноге, — уже на двух.

Он себе вырастил или ему приделали?

К. Чуковский. От двух до пяти

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

«Черный ящик»

Взглянем на любую абстрактную машину, а точнее, на ее управляющее устройство (УУ), с позиций «черного ящика». Первый его вариант — абстрактный «черный ящик» (АЧЯ), имеющий по одному входу и выходу. Символы внешнего алфавита поступают в АЧЯ через вход, обычно называемый входным алфавитом. А символы, изменяющие информацию на ленте, через выход, именуемый АЧЯ, выдает выходной алфавит. Причем допускается, что оба эти алфавита могут совпадать. Второй вариант, «структурный черный ящик» (СЧЯ) имеет множество таких каналов, и возможна ситуация, когда число входных-выходных каналов СЧЯ соответствует числу символов входного-выходного алфавитов АЧЯ. Тогда «ящик» на структурном уровне уже составляет основу модели параллельных процессов.

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

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

А необходимо ли вообще манипулировать информацией о таком внутреннем состоянии? Безусловно, ведь, например, от того, с каким «внутренним настроем» пожал вам сегодня руку ваш начальник, может зависеть многое! Казалось бы, обычное, «стандартное» действие, столь похожее на вчерашнее, но конечный результат может быть разным. Аналогично и с программами. В них внутреннее состояние — это дополнительный канал, не только следящий за ее работой, но и дающий информацию для управления ей. Именно поэтому и имеет смысл подавать информацию о внутреннем состоянии машины и на выход, и на вход «ящика». Кроме того, должно быть ясно, что данными о состоянии можно оперировать параллельно с данными на других каналах.

Было бы удобно, если бы символы внутренних состояний абстрактной машины формировали отдельное множество. Тогда можно было бы считать, что выходной алфавит СЧЯ — объединение множеств символов внутренних состояний и внутреннего алфавита машины (см. «Мир ПК», № 2-3/02).

Таким образом, можно сделать вывод: СЧЯ более удобен и гибок, чем АЧЯ, а из двух формальных моделей внутреннего устройства такого «ящика» наиболее естественна модель типа МТ, т. е. та, которая отражает понятие внутреннего состояния «черного ящика».

Операционный и управляющий блоки

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

Аналогично можно поступить и на программном уровне. Используем обычный прием формального определения программы в виде так называемой схемы программы S, где S = тройка, M — множество ячеек памяти, или просто память, A — множество операторов программы, G — управление программой [2]. В этом случае память и операторы составляют ОБ, управление — УБ. Если такой подход распространить и на абстрактные машины, то М — лента, а все остальное — управляющее устройство этих машин.

Далее разберем подробнее, что будет входить в относящуюся к ОБ и УБ машину Тьюринга и соответственно МТ-программу. Рассмотрим реализацию этих блоков, взяв за основу известные языки программирования, например Си++. Те же операции распространим по возможности и на программы для МП.

Предикаты и действия МТ

Возьмем сначала операционный блок. На этом уровне множество операторов или блоков, составляющих ОБ, можно представить двойкой , где X — множество узлов (блоков, функций и/или подпрограмм и т. п.), анализирующих символы (если говорить об АМ), Y — множество узлов, преобразующих символы. Те функции, которые входят во множество X, назовем предикатами, а те, что содержатся во множестве Y, — действиями.

В случае реализации элементов ОБ для МТ на языке Си++ ее предикат может выглядеть так:

bool xN() {sn == sj;},

где s_n — текущий символ на ленте; s_i — значение того символа, которому должен соответствовать символ на ленте.

Если символы равны, то предикат xN, где N — номер предиката и номер входного канала СЧЯ, возвратит значение «истина», а если нет — «ложь». Следует заметить, это очень важно, что предикаты по замыслу не изменяют значение памяти, т. е. информации на ленте для распараллеливания.

Функции-действия (далее — просто действия) не возвращают значений, и этот факт можно подчеркнуть на Си++ типом возвращаемого значения — void. В случае с МТ действие, изменяющее текущий символ s_n на s_k, на Си++ будет иметь следующий вид:

void yN() {sn = sk;},

а действие, перемещающее головку вправо, можно представить так:

void yN() {R;}.

Предикаты и действия для машины, адресующей ячейки ленты, примут вид:

bool xN() {s[i] == sj;},
void yN() {s[i] = sk;},

где i — индекс (адрес) ячейки на ленте, представленной массивом s.

Условимся, что для действий, как и для предикатов, N — не только обозначает их номер в ОБ, но и номер выходного канала СЧЯ.

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

qi,xj,yk,ql,

где x_j — предикат, принадлежащий множеству X;

y_k — действие из множества Y;

q_i, q_l — текущее и следующее состояния машины из множества ее внутренних состояний Q соответственно.

В результате получится код программы на Си++, реализующий предикаты и действия МТ, для функции И—НЕ (листинг 1):

Это вариант программы для МТ, имеющей адресацию. Лента реализована массивом целых чисел, где нулевой и первый элементы массива s содержат входные значения функции, а второй элемент — выходное.

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

Таблица переходов МТ

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

Сначала рассмотрим программу УБ для МТ. Для задачи моделирования функции И—НЕ запись алгоритма работы УБ машины Тьюринга будет следующей:

q1, x1x2, y2, q2
q2, x3, y1, q1
q2, x4, y1, q1

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

Теперь понятно почти полное соответствие приведенной программы для УБ таблице переходов (ТП) структурного конечного автомата (КА) Мили, моделирующего такую же функцию И-НЕ. При этом в ТП одна инструкция УБ модифицированной МТ полностью соответствует одной строке таблицы переходов КА. Понятно также, почему модель КА абсолютно подходит в качестве модели УБ машины Тьюринга: переход от программы Тьюринга к таблице переходов КА почти очевиден и элементарен (он был рассмотрен ранее).

Мы вполне можем уменьшить количество предикатов, используя их отрицание. В этом случае программа, применившая для индикации состояния своего выхода внутренние состояния, может быть представлена так:

q1, x1x2, -, q2
q2, ^ x1, -, q1
q2, ^x2, -, q1

Здесь в качестве знака отрицания использован символ (^).

Возникает вопрос: нельзя ли для дальнейшего сокращения общего количества функций ввести параметры для предикатов и действий? Безусловно, можно, но, как показала практика, лучше смириться с тем, что легко устранить, нежели ухудшить эффективность реализации и получить проблемы с формальным определением и теорией самой абстрактной машины.

09.08.2002г