§ 11. УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА

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

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

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

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

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

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

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

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

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

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

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

Указание 9. Переходи к указанию 1.

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

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

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

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

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

Поэтому мы должны в первую очередь позаботиться о выработке надлежащего способа задания

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

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

Так, например, вместо схемы рис. 12 возникает одномерная строка символов

Очевидно, по этой строке можно при желании однозначным образом восстановить первоначальную таблицу. Поступая аналогично, можно при рассмотрении конфигураций условиться о том, чтобы букву состояний писать не под обозреваемой буквой, а непосредственно правее ее. В таком случае конфигурация IV на рис. 24 перейдет в строку

Очевидно, по такому одномерному изображению конфигурации можно при желании однозначным образом восстановить ее первоначальный вид.

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

Конечно, можно было выбрать другие буквы, отличные от , и для обозначения сдвигов (влево, вправо, отсутствие сдвига), однако при этом должно быть четко оговорено, какой именно буквой какой сдвш

обозначается. Здесь сказывается тот факт, что каждая из трех букв обозначает вполне определенное действие, которое не заменимо другим.

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

1) чтобы строку можно было бы однозначным образом разбить на отдельные кодовые группы;

2) чтобы можно было распознавать, какие кодовые группы отнесены каждой из букв в отдельности, и чтобы можно было различить кодовые группы, отнесенные буквам состояний от тех, которые отнесены буквам внешнего алфавита.

Эти два условия будут наверняка соблюдены при следующем способе кодирования.

1. В качестве кодовых групп берутся различных слов вида

(между единицами — сплошь нули).

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

2. Сопоставление кодовых групп исходным буквам осуществляется согласно следующей таблице кодирования (см. стр. 99).

При такой системе кодирования в нашем случае выглядит так:

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

(см. скан)

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

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

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

Указание 2 и 3. Отыщи в шифре схемы пару соседних кодовых групп, одинаковую с парой кодовых групп в шифре конфигурации, в которой первая группа является обозреваемой.

Указание 6 Если в обозреваемой тройке кодовых групп из шифра схемы второй является группа 1001,

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

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

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

В связи с существованием универсальной тьюринговой машины всевозможные функциональные схемы (или их шифры) можно толковать двояко:

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

2) схема описывает программу, подаваемую на ленту универсальной машины для реализации соответствующего алгоритма.

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

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

реальной вычислительной машине внешняя память (магнитная лента или барабан) конечна.

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