Внутренний язык

Доказано, что для решения любой задачи, имеющей решение, может быть построена так называемая универсальная машина Тьюринга, т. е. такая машина, которая имеет единственную, строго фиксированную таблицу, описывающую ее работу. Например, для универсальной машины Тьюринга, оперирующей с двоичным алфавитом, таблицы (диаграммы) работы ее управляющего устройства можно посмотреть в монографии М. Минского Вычисления и автоматы [39].

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

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

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

Смысл этого краткого изложения можно раскрыть таким образом. Универсальная машина как бы читает на ленте описание алгоритма работы специализированной машины и по этому описанию делает то, что делала бы специализированная машина, то есть работает по принципу интерпретации (подражания). Сам принцип интерпретации заключается в последовательном выполнении раз и навсегда закрепленных правил (указаний). Воспользуемся для пояснения достаточно простыми интерпретирующими указаниями, взятыми нами с небольшими изменениями из книги Б. А. Трахтенброта Алгоритмы и вычислительные автоматы [38, с.126].

Указание 1. Обозревайте на ленте ячейку (единственную), под которой подписана буква. (Здесь и далее, в данной последовательности указаний, подписанная под ячейкой буква обозначает символ состояния интерпретируемой машины.)

Указание 2. Отыщите в таблице столбец, обозначенный той же буквой, которая подписана под обозреваемой ячейкой.

Указание 3. В найденном столбце обозревайте тройку букв, которая расположена на пересечении со строкой, обозначенной такой же буквой, какая вписана в обозреваемой ячейке.

Указание 4. Замените букву из обозреваемой ячейке первой буквой из обозреваемой тройки.

Указание 5. Если в обозреваемой тройке вторым символом является признак завершения вычислений, например, знак!, то остановитесь процесс закончен.

Указание 6. Если в обозреваемой тройке вторым символом является символ останова головки - буква Н, то замените букву, подписанную под обозреваемой ячейкой, третьей буквой из обозреваемой тройки.

Указание 7. Если в обозреваемой ячейке вторым символом является признак движения головки влево буква L, то сотрите букву, подписанную под обозреваемой ячейкой, и левее ее запишите третью букву из обозреваемой тройки.

Указание 8. Если в обозреваемой тройке вторым символом является признак движения головки вправо буква R, то сотрите букву, подписанную под обозреваемой ячейкой, и правее ее запишите третью букву из обозреваемой тройки.

Указание 9. Если просмотр входного слова не закончен, переходите к указанию 1, в противном случае заканчивайте процесс.

Если данную систему указаний закодировать по принятой системе пятерок, то полученная запись может рассматриваться как собственное описание универсальной машины. Примечательно, что описание данного алгоритма (т. е. последовательности указаний) не использует символы внешнего алфавита интерпретируемой машины, и, следовательно, этот алгоритм может быть записан на внутреннем языке универсальной машины. Иными словами, чтение описания алгоритма работы специализированной машины универсальной машиной идет стандартным образом, как предписывает система указаний, и не зависит от конкретного вида этого описания (при принятой системе кодирования информации). Этому обстоятельству мы придаем исключительно важное значение.

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

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

Поиск по сайту: