Как она работает

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

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

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

- читающе-записывающей головки (скажем, наподобие магнитофонной);

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

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

На этих рисунках приняты следующие обозначения: S_i считываемый с ленты, S_j символ записываемый на ленту; q₀, q₁, q₂ (в обобщенном виде - q_i, q_j) символы состояний машины;! состояние останова машины; Q обозначение памяти, хранящей эти состояния; символы H, R, L обозначают направления движения головки соответственно вправо, влево, команду головке остаться неподвижной; P условное обозначение устройства, управляющего движением головки; наконец, в нашем конкретном примере 1, l, + - символы внешнего алфавита, записываемые на ленте, при этом, как это часто принято делать при описании работы машины Тьюринга, буквой l обозначается пустой символ, указывающий на то, что в соответствующей ячейке ленты ничего не записано.

Работу машины Тьюринга, используя, например таблицу (см. рис. 8) можно описать следующим образом. Если в какой-то момент времени управляющее устройство находилось в состоянии q₀ (вертикальный столбец таблицы, обозначенный q₀), а головка из ячейки, напротив которой она в этот момент находилась, считывает символ 1 (горизонтальная строка таблицы, обозначенная символом 1), то в эту ячейку записывается пустой символ l, т. е. стирается записанный там ранее символ, головка перемещается на одну ячейку вправо, и управляющее устройство переходит в состояние q₂. Описанное действие считается одним тактом работы машины.

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

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

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

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

l 1 1 1 + 1 1 l,

q₀

показан на рис. 9. Исходное слово в данном случае представляет собой запись условия: сложить в унарной системе счисления числа 3 и 2. Если проследить все конфигурации, возникающие при решении данной задачи, то заключительной будет конфигурация

L 1 1 1 1 1 l,

!

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

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

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

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