 |
Универсальная машина Тьюринга
|
|
|
|
1.2.1.Композиция машин Тьюринга
|
ущность композиции машин аналогична известному в математике принципу суперпозиции. Смысл суперпозиции заключается в том, что в качестве аргумента одной функции используется другая функция. Применительно к машинам Тьюринга композиция означает, что результаты решения задачи на одной машине являются исходными данными для другой машины Тьюринга. Общая схема объединения двух машин в композицию показана на рисунке 1.6.
 |
Рисунок 1.6
На рисунке 1.6 приняты следующие обозначения:
Т1, Т2 - машины Тьюринга;
ST1, ST2 - системы команд машин Т1 и Т2 соответственно;
x - исходная информация для машины Т1;
Т1(х) - результат работы машины Т1;
Т2(Т1(х)) - результат работы машины Т2.
Рассмотрим для примера композицию двух машин, первая из которых выполняет операцию копирования, а вторая - операцию сложения чисел в унарном коде. Схема объединения машин и пример ленты с полученными результатами приведен на рисунке 1.7.
Рисунок 1.7
Показанная на рисунке 1.7 композиция позволяет выполнить операцию удвоения числа при помощи уже известных машин копирования и сложения. Таким образом, составив алгоритмы работы машин Тьюринга для решения набора определенных операций (например, арифметических операций), затем можно составлять композиции машин Тьюринга для решения более сложных задач. При этом разработка общего алгоритма сводится к его составлению из тех операций, для которых уже известны алгоритмы выполнения на машине Тьюринга. Такой подход аналогичен использованию процедур и функций в программировании.
Однако использование композиции машин предполагает, что известны алгоритмы выполнения элементарных операций, из которых составляется общий алгоритм. Поэтому при решении произвольных задач такой подход не исключает необходимости составления новых алгоритмов и, соответственно, разработки машин Тьюринга с различными блоками управления. Реализовать любой алгоритм без изменения структуры блока управления возможно при использовании универсальной машины Тьюринга.
|
|
|
1.2.2.Универсальная машина Тьюринга
Если задана некоторая машина Тьюринга (т.е. известны алфавиты входных, выходных сигналов и состояний, исходное положение головки и исходное состояние машины, а также таблица работы машины и лента с исходной информацией), то можно по шагам вручную выполнить все преобразования информации, для которых предназначена эта машина. Фактически в этом случае выполняется моделирование машины Тьюринга.
При анализе операций, которые выполняются при моделировании машины Тьюринга, можно установить, что моделирование сводится к повторению на каждом шаге следующих действий:
ÄЧтение символа из ячейки ленты, над которой находится головка.
ÄПоиск команды в таблице работы машины. Поиск выполняется по текущему состоянию машины и значению считанного символа.
ÄВыбор из команды символа, который должен быть записан на ленту, и его запись.
ÄВыбор из команды символа перемещения головки и ее перемещение.
ÄВыбор из команды нового состояния машины и смена текущего состояния на новое. Далее следует переход к следующему шагу и повторение этих действий.
|
|
 | |||||
 | |||||
 | |||||
Рисунок 1.8
Характер этих элементарных действий таков, что все они могут быть выполнены при помощи некоторой другой машины Тьюринга, которая будет моделировать работу исходной машины. Сущность моделирования поясняется на рисунке 1.8.
Если машина Т имеет систему команд ST и обрабатывает ленту с информацией Х, то её работа может быть смоделирована другой машиной U, которая имеет собственную систему команд SU. Для моделирования на вход машины U нужно подать не только ленту с информацией Х, но и систему команд (таблицу работы) ST. Эта система команд может быть записана на той же ленте, что и исходная информация.
|
|
|
 |
Рисунок 1.9
Важной особенностью моделирующей машины является то, что ее система команд SU (и соответственно структура блока управления) не зависит от алгоритма работы моделируемой машины Т. Машина Тьюринга, которая может моделировать работу любой другой машины Тьюринга, называется универсальной. Вариант структуры универсальной машины Тьюринга (УМТ) приведен на рисунке 1.9.
Лента УМТ разделена на три зоны: зону данных, зону режима и зону команд.
В зоне данных записана исходная информация, которая должна быть обработана моделируемой машиной Тьюринга. В этой же зоне записываются результаты работы УМТ.
В зоне режима записаны текущее состояние Qt и текущий входной символ Xt, который прочитан из ячейки зоны данных в данном такте.
В зоне команд записана система команд моделируемой машины. Команды упорядочены по группам. В первую группу входят команды, начинающиеся с символа Q0, во вторую - с символа Q1 и т.д. Внутри каждой группы команды упорядочены по значению символа Xt. Таким образом, команды на ленте расположены так, как они размещены в таблице работы моделируемой машины.
Чтение информации с ленты и запись на ленту выполняются при помощи трех головок: Гд - головка данных, Гр- головка режима, Гк - головка команд. Каждая головка может перемещаться по своей зоне ленты.
Перед началом работы УМТ в каждой зоне ленты должна быть записана соответствующая информация. Головки должны быть установлены над левым символом в каждой зоне.
Работа УМТ происходит по циклам, в каждом цикле моделируется выполнение одной команды моделируемой машины. Граф работы УМТ показан на рисунке 1.10.
 |
Рисунок 1.10
На рисунке 1.10 приняты следующие обозначения:
Q Гк П (Гк Л, Гр П, Гр Л, Гд П, Гд Л) - перемещение одной из головок
вправо или влево;
Q (Гк), (Гд), (Гр) - информация, читаемая одной из головок;
|
|
|
Q (Гк ) à (Гр) - чтение данных головкой команд и запись этих дан-
ных при помощи головки режима в зону режима ленты;
Q а - вспомогательная переменная, которая принимает значение 1, ес-
ли символы, читаемые головками Гк и Гр, совпадают;
Q в - вспомогательная переменная, которая принимает значение 1, ес-
ли символы текущего (Qt) и заключительного (Qz) cостояний сов-
падают;
Q р - сигнал, принимающий значение 1, если головка команд при
движении влево вышла за границы зоны команд;
В каждом цикле работы УМТ выполняются следующие шаги:
u поиск зоны команд;
u поиск команды в зоне;
u моделирование выполнения команды.
Поиск зоны команд начинается со сравнения текущего состояния Qt из зоны режима с состоянием Qi, записанным в начале первой команды в зоне команд. Если эти состояния не равны, то головка команд перемещается в начало следующей команды, для чего выполняются пять шагов головки вправо (состояния U0- U4). При совпадении символов Qt и Qi головка команд оказывается в начале первой команды нужной зоны. Далее начинается поиск команды, соответствующей символам Qt и Xt зоны режима. Для этого головка режима устанавливается над символом Xt зоны режима, а головка команд - над символом Xi в текущей команде.
Поиск команды в зоне выполняется аналогично поиску зоны команд. При этом головка команд перемещается вправо на пять шагов (состояния U5 - U9) до тех пор, пока не произойдет сравнение символов Xt и Xi.
Выполнение команды (состояния U10 - U17) начинается с перемещения головки команд на один шаг вправо, после чего символ Yt, прочитанный из найденной команды, при помощи головки данных записывается в зону данных вместо считанного ранее символа Xt. После очередного шага головки команд вправо из найденной команды считывается символ перемещения головки данных (Yd) и головка данных перемещается в соответствии с этим символом (П, Л). Под ней оказывается очередной обрабатываемый символ (Xt+1), который при помощи головки режима записывается в зону режима для подготовки следующего цикла. Далее головки команд и режима устанавливаются так, чтобы в зону режима можно было записать очередное состояние Qt+1 (состояния
|
|
|
U14,U15). В состоянии U16 проверяется условие окончания решения. Если символ очередного состояния не совпадает с символом конечного состояния моделируемой машины (Qz), то решение задачи не закончено, и в состоянии U17 головка команд перемещается в исходное положение (в начало первой команды первой зоны). При этом УМТ оказывается готовой к выполнению следующего цикла, т.е. к моделированию выполнения следующей команды.
При совпадении символов Qt и Qz решение задачи заканчивается и УМТ переходит в конечное состояние Uz.
При анализе процесса работы УМТ можно сделать важный вывод о том, что алгоритм работы УМТ не зависит от того, какую именно задачу решает моделируемая машина Тьюринга. Поэтому структура блока управления УМТ не меняется при моделировании различных машин, т.е. не зависит от решаемых задач. Именно поэтому УМТ действительно является универсальной машиной, при помощи которой выполнить любой алгоритм без изменения ее структуры.
Поскольку процесс выбора очередной команды УМТ и ее выполнения связан с последовательным перебором ячеек ленты, решение задач на УМТ требует слишком много времени. Поэтому машина Тьюринга, в том числе и универсальная, никогда не была построена, однако нетрудно увидеть в ней аналог современных ЭВМ. Так система команд в зоне команд УМТ аналогична машинной программе, при этом пара символов Qt и Xt играют роль адреса машинной команды.
Однако машина Тьюринга является довольно удобным средством для описания алгоритмов и широко используется в теории алгоритмов.
Контрольные вопросы
ü1.Что такое композиция машин Тьюринга?
ü2.Для чего используется композиция машин Тьюринга?
ü3.Может ли одна машина Тьюринга моделировать работу другой машины
Тьюринга?
ü4.Какие действия выполняются при этом?
ü5.Поясните структуру универсальной машины Тьюринга?
ü6.Какая информация записывается в зонах ленты УМТ?
ü7.Что такое система команд машины Тьюринга?
ü8.Какие шаги содержит цикл работы УМТ?
ü9.Поясните содержание шага «поиск зоны команд».
ü10.Поясните содержание шага «выполнение команды».
ü11.Какие особенности имеет процесс обработки информации при помощи
машины Тьюринга?
|
|
|
|
