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

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

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

Пример 5.1. Приведем программы машин Тьюринга, правильно вычисляющих функции S(x) = x+1 и O(x) = 0. Функция S(x) = x+1 осуществляет перевод: 0 => . Ее программа: 0 > П, 1 > 1П, 0 > 1, 1 > 1Л, 0 > 0. Функция O(x) = 0 осуществляет перевод: 0 => . Ее программа: 0 > 0П, 1 > 1П, 0 > 0Л, 1 > 0, 0 > 0Л, 0 > 0. Соответствующую машину Тьюринга обозначили О.

Пример 5.2. Построить две машины «левый сдвиг» и «правый сдвиг» . Первая из начального стандартного положения перерабатывает слово 0 в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово 0 перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.

Программа машины: 0 > 0Л, 1 > 1Л, 0 > 0. Ясно, что программа машины получается из программы предыдущей машины заменой символа «Л» символом «П».

Композиция машин Тьюринга

Определение 6.1: Пусть заданы машины Тьюринга и, имеющие общий внешний алфавит {, …,} и алфавиты внутренних состояний {, …,} и {, …, } соответственно. Композицией (или произведением) машины на машину называется новая машина с тем же внешним алфавитом {, …,}, внутренним алфавитом {, …, …, } и программой, получающейся следующим образом. Во всех командах из, содержащих символ остановки, заменяем последний на. Все остальные символы в командах из остаются неизменными. В командах из символ остается неизменным, а все остальные состояния (i = 1, …, t) заменяем соответственно на. Совокупность всех так полученных команд образует программу машины-композиции.

Введенное понятие является удобным инструментом для конструирования машин Тьюринга. Покажем это на примере.

Пример 6.1. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы (, …,) = (1? m ? n).

Рассмотрим сначала конкретный случай n=3, m=2, т.е. функцию (,) = . Мы должны переработать слово 0 в слово 0. Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга, В, О:

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

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

Затем, двигаясь влево, транспонировать (с помощью В) массив с каждым соседним слева массивом, пока массив не выйдет на первое место:

Теперь нужно дойти до крайнего правого массива с помощью (n-1) - кратного применения правого сдвига:

Наконец, нужно стирать последовательно справа налево все массивы единиц, кроме первого:

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

Рисунок 1.6

На рисунке 1.6 приняты следующие обозначения:

Т 1 , Т 2 - машины Тьюринга;

ST 1 , ST 2 - системы команд машин Т 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.

Лента УМТ разделена на три зоны: зону данных, зону режима и зону команд.

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

В зоне режима записаны текущее состояние Q t и текущий входной символ X t , который прочитан из ячейки зоны данных в данном такте.

В зоне команд записана система команд моделируемой машины. Команды упорядочены по группам. В первую группу входят команды, начинающиеся с символа Q 0 , во вторую - с символа Q 1 и т.д. Внутри каждой группы команды упорядочены по значению символа X t . Таким образом, команды на ленте расположены так, как они размещены в таблице работы моделируемой машины.

Чтение информации с ленты и запись на ленту выполняются при помощи трех головок: Г д - головка данных, Г р - головка режима, Г к - головка команд. Каждая головка может перемещаться по своей зоне ленты.

Перед началом работы УМТ в каждой зоне ленты должна быть записана соответствующая информация. Головки должны быть установлены над левым символом в каждой зоне.

Работа УМТ происходит по циклам, в каждом цикле моделируется выполнение одной команды моделируемой машины. Граф работы УМТ показан на рисунке 1.10.

Рисунок 1.10

На рисунке 1.10 приняты следующие обозначения:

Q Г к П (Г к Л, Г р П, Г р Л, Г д П, Г д Л) - перемещение одной из головок

вправо или влево;

Q (Г к), (Г д), (Г р) - информация, читаемая одной из головок;

Q (Г к) à (Г р) - чтение данных головкой команд и запись этих дан-

ных при помощи головки режима в зону режима ленты;

Q а - вспомогательная переменная, которая принимает значение 1, ес-

ли символы, читаемые головками Г к и Г р, совпадают;

Q в - вспомогательная переменная, которая принимает значение 1, ес-

ли символы текущего (Q t) и заключительного (Q z) cостояний сов-

Q р - сигнал, принимающий значение 1, если головка команд при

движении влево вышла за границы зоны команд;

В каждом цикле работы УМТ выполняются следующие шаги:

u поиск зоны команд;

u поиск команды в зоне;

u моделирование выполнения команды.

Поиск зоны команд начинается со сравнения текущего состояния Q t из зоны режима с состоянием Q i , записанным в начале первой команды в зоне команд. Если эти состояния не равны, то головка команд перемещается в начало следующей команды, для чего выполняются пять шагов головки вправо (состояния U 0 - U 4). При совпадении символов Q t и Q i головка команд оказывается в начале первой команды нужной зоны. Далее начинается поиск команды, соответствующей символам Q t и X t зоны режима. Для этого головка режима устанавливается над символом X t зоны режима, а головка команд - над символом X i в текущей команде.

Поиск команды в зоне выполняется аналогично поиску зоны команд. При этом головка команд перемещается вправо на пять шагов (состояния U 5 - U 9) до тех пор, пока не произойдет сравнение символов X t и X i .

Выполнение команды (состояния U 10 - U 17) начинается с перемещения головки команд на один шаг вправо, после чего символ Y t , прочитанный из найденной команды, при помощи головки данных записывается в зону данных вместо считанного ранее символа X t . После очередного шага головки команд вправо из найденной команды считывается символ перемещения головки данных (Y d) и головка данных перемещается в соответствии с этим символом (П, Л). Под ней оказывается очередной обрабатываемый символ (X t +1), который при помощи головки режима записывается в зону режима для подготовки следующего цикла. Далее головки команд и режима устанавливаются так, чтобы в зону режима можно было записать очередное состояние Q t +1 (состояния

U 14 ,U 15). В состоянии U 16 проверяется условие окончания решения. Если символ очередного состояния не совпадает с символом конечного состояния моделируемой машины (Q z), то решение задачи не закончено, и в состоянии U 17 головка команд перемещается в исходное положение (в начало первой команды первой зоны). При этом УМТ оказывается готовой к выполнению следующего цикла, т.е. к моделированию выполнения следующей команды.

При совпадении символов Q t и Q z решение задачи заканчивается и УМТ переходит в конечное состояние U z .

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

Поскольку процесс выбора очередной команды УМТ и ее выполнения связан с последовательным перебором ячеек ленты, решение задач на УМТ требует слишком много времени. Поэтому машина Тьюринга, в том числе и универсальная, никогда не была построена, однако нетрудно увидеть в ней аналог современных ЭВМ. Так система команд в зоне команд УМТ аналогична машинной программе, при этом пара символов Q t и X t играют роль адреса машинной команды.

Однако машина Тьюринга является довольно удобным средством для описания алгоритмов и широко используется в теории алгоритмов.

Контрольные вопросы

ü1.Что такое композиция машин Тьюринга?

ü2.Для чего используется композиция машин Тьюринга?

ü3.Может ли одна машина Тьюринга моделировать работу другой машины

Тьюринга?

ü4.Какие действия выполняются при этом?

ü5.Поясните структуру универсальной машины Тьюринга?

ü6.Какая информация записывается в зонах ленты УМТ?

ü7.Что такое система команд машины Тьюринга?

ü8.Какие шаги содержит цикл работы УМТ?

ü9.Поясните содержание шага «поиск зоны команд».

ü10.Поясните содержание шага «выполнение команды».

ü11.Какие особенности имеет процесс обработки информации при помощи

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

Со­че­та­ния ал­го­рит­мов - это на­зва­ние, уста­но­вив­ше­еся за ря­дом кон­крет­ных спо­со­бов кон­стру­иро­ва­ния но­вых ал­го­рит­мов из не­ско­ль­ких за­дан­ных.

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

Со­че­та­ния ал­го­рит­мов для ма­ши­ны Тью­рин­га опи­сы­ва­ют­ся опе­ра­ци­ями над ма­ши­на­ми Тью­рин­га.

1. Опе­ра­ция ком­по­зи­ции.

Пусть M 1 и M 2 - ма­ши­ны Тью­рин­га, име­ющие оди­на­ко­вый вне­шний ал­фа­вит A« {a 0 ,a 1 ,...,a p }. Обоз­на­чим мно­же­ст­ва их со­сто­яний со­от­ве­т­ст­вен­но Q1 « {q 0 ,q 1 ,...,q n } и Q2 « {q 0" ,q 1" ,...,q m" }.

Опре­де­ле­ние.

Ком­по­зи­ци­ей ма­шин M 1 и M 2 на­зы­ва­ют ма­ши­ну, обоз­на­ча­емую M=M 1 ×M 2 , про­грам­ма ко­то­рой име­ет ал­фа­вит A, мно­же­ст­во со­сто­яний Q« {q 0 ,q 1 ,...,q n ,q n+1 ,...,q n+m } и по­лу­ча­ет­ся из про­грамм ма­шин M 1 и M 2 сле­ду­ющим об­ра­зом: вез­де в про­грам­ме ма­ши­ны M 1 , где встре­ча­ют­ся "трой­ки" с сим­во­лом q 1 (за­клю­чи­те­ль­ное со­сто­яние ма­ши­ны M 1), он за­ме­ня­ет­ся на сим­вол q 0" (на­ча­ль­ное со­сто­яние ма­ши­ны M 2); все оста­ль­ные сим­во­лы в про­грам­мах ма­шин M 1 и M 2 оста­ют­ся не­из­мен­ны­ми (в за­вер­ше­ние оста­ёт­ся пе­ре­ну­ме­ро­вать все со­сто­яния ма­ши­ны M: {q 0 ,q 1" ,q 2 ,...,q n ,q 0" ,q 2" ,...,q m" }).

Ком­по­зи­ция на­чи­на­ет "ра­бо­тать" как ма­ши­на M 1 , но в тех слу­ча­ях, ког­да ма­ши­на M 1 до­лжна оста­но­ви­ть­ся, про­ис­хо­дит пе­ре­клю­че­ние на про­грам­му ма­ши­ны M 2 , вслед­ст­вие за­ме­ны q 1 на q 0" . Оче­вид­но, что опе­ра­ция ком­по­зи­ции ас­со­ци­атив­на, но не ком­му­та­тив­на.

Её работа равносильна последовательной работе машин T1 и T2 .

На рисунке изображена композиция машин Тьюринга, реализующая оператор суперпозиции для n=1 и m=1.

Рисунок 1.

Опре­де­ле­ние.

Ите­ра­ци­ей ма­ши­ны Тью­рин­га M бу­дем на­зы­вать ма­ши­ну

2. Опе­ра­ция вет­вле­ния.

Пусть M 1 , M 2 и M 3 - ма­ши­ны Тью­рин­га, име­ющие оди­на­ко­вый вне­шний ал­фа­вит A« {a 0 ,a 1 ,...,a i ,...,a j ,...,a p } и, со­от­ве­т­ст­вен­но, мно­же­ст­ва со­сто­яний: Q1 « {q 0 ,q 1 ,...,q n }, Q2 « {q 0" ,q 1" ,...,q m" }, Q3 « {q 0", q 1" ,...,q l" }.

Опре­де­ле­ние.

Ре­зу­ль­та­том опе­ра­ции вет­вле­ния над ма­ши­на­ми Тью­рин­га M 1 , M 2 и M3 на­зы­ва­ет­ся ма­ши­на Тью­рин­га M, про­грам­ма ко­то­рой по­лу­ча­ет­ся из про­грамм ма­шин M 1 ,M 2 и M 3 сле­ду­ющим об­ра­зом: за­пи­са­на про­грам­ма ма­ши­ны M1 , за­тем при­пи­са­ны про­грам­мы ма­ши­ны M 2 и M 3 . Ес­ли в за­клю­чи­те­ль­ном со­сто­янии q 1 ма­ши­ны M1 на­блю­да­ет­ся сим­вол a i , то управ­ле­ние пе­ре­да­ет­ся на ма­ши­ну M 2 , т.е. сим­вол q 1 за­ме­ня­ет­ся сим­во­лом q 0" и на­чи­на­ет ра­бо­тать ма­ши­на M 2 . Ес­ли же в за­клю­чи­те­ль­ном со­сто­янии q 1 ма­ши­ны M 1 на­блю­да­ет­ся сим­вол a j , то управ­ле­ние пе­ре­да­ет­ся на ма­ши­ну M 3 , т.е. сим­вол q 1 за­ме­ня­ет­ся сим­во­лом q 0" и на­чи­на­ет ра­бо­тать ма­ши­на M 3 . Все оста­ль­ные сим­во­лы в про­грам­мах ма­шин M 1 и M 2 оста­ют­ся не­из­мен­ны­ми. Ма­ши­на M за­вер­ша­ет ра­бо­ту в за­клю­чи­те­ль­ном со­сто­янии q 1 (в за­клю­че­ние оста­ет­ся осу­ще­ст­вить сквоз­ную пе­ре­ну­ме­ра­цию со­сто­яний ма­ши­ны M).

Ре­зу­ль­тат опе­ра­ции вет­вле­ния над ма­ши­на­ми Тью­рин­га M 1 , M 2 и M3 обоз­на­ча­ет­ся сле­ду­ющим об­ра­зом:

Для двух­бук­вен­ных ма­шин Тью­рин­га (ма­шин Тью­рин­га с двух­бук­вен­ным ал­фа­ви­том) опе­ра­ция вет­вле­ния над про­из­во­ль­ны­ми ма­ши­на­ми Тью­рин­га M1 , M2 и M3 обоз­на­ча­ет­ся сле­ду­ющим об­ра­зом:

т.е. ес­ли при ра­бо­те ма­ши­ны M1 в со­сто­янии q 1 на­блю­да­ет­ся сим­вол a 0 , то управ­ле­ние пе­ре­да­ет­ся на ма­ши­ну M2 , в про­тив­ном слу­чае - на ма­ши­ну M3.

3. Опе­ра­ция за­цик­ли­ва­ния.

Пусть M - ма­ши­на Тью­рин­га с ал­фа­ви­том A« {a 0 ,a 1 ,...,a p } и мно­же­ст­вом со­сто­яний Q« {q 0 ,q 1 ,...,q n }.

Опре­де­ле­ние.

Ре­зу­ль­та­том опе­ра­ции за­цик­ли­ва­ния бу­дем на­зы­вать ма­ши­ну Тью­рин­га, обоз­на­ча­емую (i=0,2,3,...,n; j=0,1,2,...,p; s=0,2,3,...,n)

про­грам­ма ко­то­рой по­лу­ча­ет­ся из про­грам­мы ма­ши­ны M за­ме­ной в кон­сек­вен­т е ко­ман­ды q i a j ®q 1 a t r, rÎ{L,R,L}, t=0,1,2,...p, сим­во­ла q 1 на сим­вол q s .

2 .4 Варианты машины Тьюринга

Модель машины Тьюринга допускает расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями. Однако все эти машины являются полными по Тьюрингу и моделируются обычной машиной Тьюринга .

В качестве примера такой эквивалентности рассмотрим сведение любой МТ к МТ, работающая на полубесконечной ленте .

Теорема: Для любой машины Тьюринга существует эквивалентная машина Тьюринга, работающая на полубесконечной ленте.

Доказательство:

Рассмотрим доказательство Ю. Г. Карпова . Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Рисунок 1.

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Рисунок 1.

2.5 Вычислимость по Тьюрингу и разрешимость

Выше было доказано, что классы функций, вычислимых с помощью рекурсивных функций, машин Тьюринга или нормальных алгоритмов Маркова, совпадают. Это позволяет рассматривать понятие «вычислительный алгоритм» инвариантным к способу описания. Различия наблюдаются лишь в использовании алгоритмических объектов. Если для рекурсивных функций объектами являются числа и числовые функции, а процесс вычисления задан операторами суперпозиции, рекурсии, минимизации и итерации, то для машин Тьюринга такими объектами являются символы алфавитов внешней и внутренней памяти, а процесс вычисления задан протоколом, использующим функции выхода, перехода и перемещения головки. Для нормального алгоритма Маркова такими объектами являются слова или последовательности символов, а процесс вычисления задан правилами подстановки или продукциями, изменяющими состав и структуру исходной последовательности символов до искомого результата.

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

Для алгоритмических проблем типичной является ситуация, когда требуется найти алгоритм для вычисления числовой функции f(x 1 , x 2 , …, x n), зависящей от целочисленных значений аргументов x 1 , x 2 , …, x n .

Функцию f:N n →N назовем вычислимой , если существует алгоритм, позволяющий для любого набора значений ее аргументов вычислить значение функции (или указать, что функция на данном наборе не определена). Так как в определении вычислимой функции используется интуитивное понятие алгоритма, то часто вместо термина «вычислимая функция» используется термин «интуитивно вычислимая функция». Таким образом, массовая проблема имеет решение, если арифметическая функция, соответствующая этой проблеме, является интуитивно вычислимой.

Функция f(x 1 , x 2 , …, x n) называется эффективно вычислимой , если для заданных значений k 1 , k 2 , …, k n аргументов можно найти значение функции f(k 1 , k 2 , …,k n) с помощью некоторой имеющейся механической процедуры (алгоритма).

Вместо уточнения понятия алгоритма можно рассматривать уточнение понятия «вычислимая функция». Обычно при этом действуют по следующей схеме:

1. Вводят точно определенный класс функций.

2. Убеждаются, что все функции из этого класса являются вычислимыми.

3. Принимают гипотезу (тезис) о том, что класс вычислимых функций совпадает с введенным классом функций.

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

Тезис Тьюринга . Всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.

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

Следует отметить, что в этих случаях достаточно использовать алфавит {0,|}, где 0 – пустой символ. Например, натуральные числа, включая 0, в этом алфавите кодируются следующим образом: 0 - |; 1 - ||; 2 -

N - ||…| (n + 1 раз). Частичная числовая n – местная функция f(x1 , x2 , …, xn) называется вычислимой по Тьюрингу , если существует машина М, вычисляющая ее в следующем смысле: 1. Если набор значений аргументов принадлежит области определения функции f , то машина М, начиная работу в конфигурации 0 |x1+1 0 |x2+1 … 0 |xn q1 |, где |x = ||… | (x раз) , и воспринимается самый правый символ, останавливается, заканчивая работу в конфигурации 0|yq0 |, где y = f(x1 , x2 , …, xn). 2. Если набор значений аргументов не принадлежит области определения функции f , то машина М, начиная работу в исходной конфигурации, работает бесконечно, то есть не приходит в заключительное состояние. Машина Тьюринга есть точное формальное определение алгоритма. С помощью этого понятия можно доказывать разрешимость или неразрешимость алгоритмических проблем. Если для решения задачи, принадлежащей единому классу задач, найден алгоритм вычисления, то о задаче говорят как об алгоритмически разрешимой проблеме . Иначе говоря, обязательным условием вычислимости или результативности вычисления является её алгоритмическая разрешимость. В этом смысле понятие «разрешимость» является также основным понятием в теории алгоритмов. Анализ трех типов моделей показывает, что основные свойства дискретности, детерминизма, массовости и результативности остаются неизменными для различных способов описания: Свойство дискретности: алгоритм состоит из отдельных элементарных действий, выполняемых по шагам; множество элементарных шагов, из которых состоит алгоритмический процесс, конечно и счетно. Свойство детерминированности: после каждого шага дается точное указание, как и в какой последовательности выполнять следующие шаги алгоритмического процесса. Свойство массовости: использование алгоритма допустимо для множества алгоритмических объектов данного типа и данного класса задач. Свойство результативности: остановка алгоритмического процесса обязательна после конечного числа шагов с указанием искомого результата. Однако , тезис невозможно доказать, так как он связан точным понятием вычислимости по Тьюрингу с неточным понятием интуитивно вычислимой функции.

ПРОБЛЕМА САМОПРИМЕНИМОСТИ

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

П: q i a a j a ® q r a a s a S t a , a = 1, 2, …, k , где S 1 - R, S 2 - L , S 3 - C . (*)

При этом можно считать, что существуют некоторые общие алфавиты A 0 и Q 0 , в которых записываются символы a и q для всех машин Тьюринга. Тогда символы q i a , a j a , q r a , a s a , S t a являются символами алфавитов A 0 и Q 0 .

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

Геделева нумерация машин Тьюринга. Пусть p 1 , p 2 , p 3 , … - последовательность простых чисел, расположенная в порядке возрастания, например, 2, 3, 5, 7, 11, 13, …

Номером машины Тьюринга с программой (*) называется число

n(T) = .

Пример

Машина, реализующая функцию S (x ) = x + 1 , имеет программу в алфавите {0,  } . Номер этой программы с учетом того, что a 0 = 0 , a 1 = | будет число:.

n(T)= 2 1 3 1 5 1 7 1 11 1 13 1 17 0 19 0 23 1 29 3 .

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

Машина T , применимая к слову n (T) (то есть к коду своего собственного номера), называется самоприменимой .

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

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

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

Пусть, например, данная машина T применяется к коду n (T * ) . Если машина T * самоприменима, то заключительная конфигурация машины T имеет вид a" q 0 | B" , а в случае, если машина T * несамоприменима, то заключительная конфигурация машины T имеет вид a" q 0 0 B ". Здесь a", B", a", B" – слова.

Теорема Проблема самоприменимости алгоритмически неразрешима, то есть не существует машины Тьюринга, решающей эту проблему в указанном выше смысле.

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

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

Проблема применимости к начальному слову состоит в следующем: создать алгоритм, который по машине T и слову X устанавливал бы, применима машина T к слову X или нет (иначе проблема останова).

В терминах машин Тьюринга, аналогично формулировке проблемы самоприменимости, эта проблема формулируется так: можно ли построить машину, которая была бы применима ко всем словам вида n (T)0X , где T произвольная машина, X – произвольное слово, и в случае, если машина T применима к слову X a" q 0 |B" , а в случае, если машина T не применима к слову Х , приводила бы к заключительной конфигурации a"q 0 0 B" . Здесь a" , B" иa", B" – произвольные слова.

Теорема Проблема применимости к начальному слову алгоритмически неразрешима, то есть не существует машины Тьюринга, решающей эту проблему в указанном выше смысле.

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

Нумерация алгоритмов

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

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

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

Пусть имеется некая массовая проблема с множеством исходных объектов X и множеством искомых объектов Y. Для существования решения массовой проблемы необходимо, чтобы элементы множеств X и Y были конструктивными объектами. Следовательно, элементы этих множеств можно занумеровать натуральными числам. Пусть x∈ X – некий исходный объект, обозначим через n(x) его номер. Если в массовой проблеме по исходному объекту x требуется получить искомый объект y∈ Y с номером n(y), то определим арифметическую функцию f: Nn →N, такую что f(n(x))=n(y).

В качестве примера построения арифметических функций по массовым проблемам рассмотрим массовые проблемы.

1. Если дан массив ] натуральных чисел, то ему в соответствие можно поставить натуральное число 2x1, 3x2,... p(n)xn , где p(n) – n-е простое число. Рассмотрим для примера массив длины 5:

] 2x13x25x37x411x5.

Данная нумерация определяет арифметическую функцию f (например, f(73500) = f(22315372110) = 20315272113 = 4891425).

2. Любое рациональное число имеет некоторый натуральный номер. Нумерация множества искомых объектов проблемы тривиальна:

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

3. Нумерация текстов программ может быть осуществлена следующим образом: любую программу можно воспринимать как запись числа в 256-ричной системе счисления (если для записи программы использовались символы таблицы ASCII).

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

Нумерация наборов чисел

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

Рисунок 1.

Пусть пары (x, y) формируют частично упорядоченное множество N (2) . Если дано h(x, y) = n, то существует обратное отображение: x = h -1 1 (n) и y= h -1 2 (n), т. е. h(h -1 1 (n), h -1 2 (n)) = n. Это позволяет вычислять номер n для любой пары (x, y) и, наоборот, по номеру n вычислять значения x и y:

Используя эти правила, можно вычислять нумерацию троек h 2 (x, y, z) = h(h(x, y), z) = n и, наоборот, по номеру тройки - значения x, y, z. Например, если h 2 (x, y, z) = n, то z= h -1 2 (n), y= h -1 2 (h -1 1 (n)), x= h -1 1 (h -1 1 (n)), h 2 (x, y, z) = h(h(h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n))), h -1 2 (n)). Тройки (x, y, z) формируют частично упорядоченное множество N (3) . Аналогично для произвольного количества чисел имеем:

h n-1 (x1, x2,…, xn)=h(h…h(h(x1, x2), x3)… x n-1), xn). Если h n-1 (x1, x2,…, xn)=m, то xn = h -1 2 (m), x n-1 =h -1 2 (h -1 1 (m)), ....................................., x2 = h -1 2 (h -1 1 (...h -1 1 (m)...)), x1 = h -1 2 (h (...h (m)...)).

Имея нумерацию множеств наборов N (1) , N (2) ,..., N (i) ,..., N(n , где N (i) – множество наборов (i) чисел, можно установить объединенную нумерацию произвольных наборов чисел M = N (1) N (2) ... N (i) .. N(n) , где M N. Для любого n N имеем h(x1,x2,..., xn )= h(h n−1 (x1,x2,..., xn), n −1).

Если h(x ,1x ,2..., x)n = m, то h n−1 (x ,1x ,2..., x)n = h -1 1 (m), n= h -1 2 (m)+1. Используя вышеприведенные формулы, можно восстановить значения x1, x2,…, xn.

Похожая информация.

Определение, функционирование и способы задания машины Тьюринга

Под машиной Тьюринга понимается некоторая гипотетическая (абстрактная) машина, состоящая из следующих частей (рис. 3.1.)

1) бесконечная в обе стороны лента, разбитая на ячейки, в каждой из которых может быть записан только один символ из алфавита , а также пустой символ l ;

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

Рис. 3.1. Машина Тьюринга

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

1. рабочая головка считывает (обозревает) символ ;

2. в зависимости от своего состояния и обозреваемого символа головка вырабатывает символ и записывает его в обозреваемую ячейку (возможно =) ;

3. головка перемещается на одну ячейку вправо (R) , влево (L) или остается на месте (E) ;

4. головка переходит в другое внутреннее состояние . (возможно =).

Состояние называется начальным, - заключительным. При переходе в заключительное состояние машина останавливается.

Полное состояние МТ называется конфигурацией . Это распределение букв по ячейкам ленты, состояние рабочей головки и обозреваемая ячейка. Конфигурация в такте t записывается в виде: , где - подслово слева от обозреваемой ячейки, - буква в обозреваемой ячейке, - подслово справа.

Начальная конфигурация и конечная называются стандартными.

Для описания работы МТ существует 3 способа:

Система команд вида

Функциональная таблица;

Граф (диаграмма) переходов.

Рассмотрим их на примерах.

Пример 1. Построить МТ, реализующую конкатенацию двух слов в алфавите . Слова на ленте разделены знаком * . Начальная конфигурация является стандартной.

Система команд МТ имеет вид:

В состоянии осуществляется движение головки вправо до пустого символа.

Самый правый символ стирается.

Звездочка стирается, если первое слово пустое.

Правое слово посимвольно сдвигается влево на одну позицию.

Переход в стандартную конечную конфигурацию.

Функциональная таблица

Прочерки в таблице означают, что символ l не может быть встречен в состояниях .

Стандартная заключительная конфигурация.

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

С помощью МТ можно описывать выполнение арифметических операций над числами. При этом числа представляются на ленте как слова в алфавите, состоящем из цифр какой-нибудь системы счисления, и разделяющихся специальным знаком, не входящем данный алфавит, например, * . Наиболее употребительной системой является унарная, состоящего из одного символа –1. Число Х на ленте записывается словом , (или сокращенно ) в алфавите А={1} .

Числовая функция правильно вычислима (или просто вычислима) по Тьюрингу, если существует МТ, которая переводит конфигурацию в конфигурацию , когда =y , или работает бесконечно, когда не определена.

Пример 2. Операция сложения двух чисел в унарном коде.

Начальная конфигурация:

Конечная конфигурация: т.е. сложение фактически сводится к приписыванию числа b к числу a . Для этого первая 1 стирается, а * заменяется на 1.

Приведем описание МТ в виде функциональной таблицы:

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

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

Опишем 4 основных способа композиции МТ:

Последовательная композиция (суперпозиция);

Параллельная композиция;

Разветвление

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

и обозначается .

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

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

Пример 3. Построить алгоритм умножения 2*Х в унарном коде с использованием машины копирования , переводящей слово a в слово a*a и машины сложения . Искомая МТ выглядит следующим образом:

Параллельной композицией машин и , вычисляющих словарные функции и в алфавитах А и В соответственно, называется машина Т , вычисляющая словарную функцию . Здесь знак используется для разделения слов при параллельной композиции МТ.

и обозначается: .

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

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

Для реализации параллельной композиции n машин используется n– этажная лента.

Команда МТ с двухэтажной лентой записывается следующим образом:, где - буквы, записанные соответственно на первом и втором этажах.

Пример 4 . Реализовать параллельную композицию машин и , вычисляющих функции в двоичной системе счисления и a + b в унарной системе.

Входное слово имеет вид: .

Опишем работу МТ системой команд:

Движение вправо до слова b

Перезапись слова b на второй этаж

Движение влево до слова a

Прибавление 1 к числу Х.

Движение вправо к слову b.

Перепись b на 1-й этаж с одновременным сложением чисел a и b .Т соответственно. Команды в фигурных скобках, добавленные к системе команд

Конечное состояние всей МТ.

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

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

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

Функционирование машины Тьюринга:

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

Машина Тьюринга работает с тремя алфавитами:

1. входной алфавит А ={а 0 …а n }, с помощью которого записывается входная, промежуточная, выходная информация. а 0 – пустой символ (незначащий ноль, Ù, В , #), а 1 – 1 или |

2. внутренний алфавит, или алфавит состояний Q ={q 0 …q m }, q 0 - заключительное состояние q 1 – начальное состояние q 0 …q n – рабочее состояние

3. алфавит сдвига {Л, В, Н} или {-1, +1, 0} (влево, вправо, на месте)

Машина Тьюринга состоит из следующих частей:

1) лента , потенциально бесконечная в обе стороны. Потенциальная бесконечность означает, что в каждый момент времени на ленте записано конечное слово, но в случае необходимости слева и справа от слова можно достроить необходимое количество ячеек. Лента разделена на ячейки, в каждой из которых записан только один символ входного алфавита. В пустых ячейках записан пустой символ. Если в ячейке информацию необходимо стереть, то достаточно записать в неё пустой символ.

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

3) головка (считывающее и записывающее устройство) в каждый момент времени выполняет следующие действия

· считывает символ, записанный в ячейке

· заменяет его на другой символ алфавита А или оставляет прежним

· сдвигается по ленте вправо, влево на одну ячейку или остается на месте

Правило работы машины Тьюринга:

Машина Тьюринга, находясь в состоянии q i и считывая символ a j , записывает в данную ячейку символ а k , переходит в состояние q e , осуществляет сдвиг. При этом говорят, что машина выполнила одну команду: a j q i ®a k q e S SÎ{Л, П, Н}

Совокупность команд называется программой МТ.

a j q i – исходные символы команд должны быть различны. Если это условие выполняется, машина называется детерминированной , в противном случае – недетерминированной . Машина работает в дискретные моменты времени.

Таким образом, полное описание машины Тьюринга в каждый момент времени, по которому можно определить её дальнейшее поведение, содержит инфу о:

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

Работа машины Тьюринга может быть представлена как последовательность конфигураций k 1 ®k 2 ®…®k n .

Стандартная начальная конфигурация – считывание крайнего левого непустого символа в состояние q 1

Стандартная заключительная конфигурация – машина перешла в заключительное состояние:

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

МТ представляет собой совокупность, состоящую из входного алфавита, алфавита состояний и программы. M = . А – входной алфавит Q – внутренний алфавит П – программа

Программа машины может быть задана следующим образом:

1) списком команд: a j q i ®a k q n S

2) с помощью таблицы

3) с помощью графа предикатов (вершины – состояния, каждой команде соответствует дуга)

Конструирование машин Тьюринга:

Сконструировать машину Тьюринга – построить её программу. Проходит в два этапа:

1) словесное описание алгоритма решаемой задачи

2) перевод словесного описания алгоритма на язык машины Тьюринга (для этого задаются A , Q , П )

Пример : построить машину Тьюринга, которая вычисляет функцию f(n)=n+1, где n задано в двоичной системе исчисления.

А ={0,1,a 0 }, множество Q определяется в процессе построения программы.

Алгоритм:

1. перевести головку из крайнего правого состояния в крайнее левое

2. если в крайнем правом положении машина считывает 0, то положить в ячейку 1 и остановиться, если головка считывает 1, положить в ячейку 0 и сдвинуться на один шаг влево.

Повторить Шаг 2

Пример : На ленте записано натуральное десятичное число. Необходимо сконструировать машину Тьюринга, увеличивающую это число на 1. Изначально головка указывает на первую цифру числа. Получаем: A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0 }, Q = {q 1 , q 2 , q 0 }. П – см. таблицу.

Общая идея – переместить головку на последнюю цифру числа, и если эта цифра не 9, то увеличить её на единицу, иначе обратить в ноль и перейти к предыдущей ячейке.

Композиция машин:

Композиция машин представляет собой последовательное выполнение двух машин.

Т 1 =(A 1 , Q 1 , П 1 ) Т 2 =(A 2 , Q 2 , П 2 ) Q 1 Ç Q 2 =Æ

Композицией машин Т 1 °Т 2 называется машина Т (A , Q , П ), где А =А 1 ÈA 2 ; Q =(Q 1 ÈQ 2 )\{q 10 } (q 10 – заключительное состояние Т 1 ). Машина Т работает по следующему правилу: U – некоторое слово, Т (U )=Т 1 °Т 2 (U )=Т 2 (Т 1 (U ))

Теорема. Композиция машин Т 1 °Т 2 существует.

Q 1 ={q 10 , q 1 ,…, q n }

Q 2 ={q 20 , q` 1 , …, q` n }, тогда для построения Q удалим состояние q 10 , переобозначив его в q n +1 , которое совпадает с начальным состоянием второй машины, а все остальные состояния - в q` i =q n + 1 .

Вычислимые по Тьюрингу функции:

Функция f(x 1 …x n) называется вычислимой по Тьюрингу , если существует машина Тьюринга, вычисляющая значение этой функции, когда заданы значения аргументов. Функция f(x 1 …x n) задана на множестве натуральных чисел, но теория алгоритмов рассматривает расширенное множество натуральных чисел NÈ{0}.

Аргументы функции f(x 1 …x n) на ленте представляются в виде следующего слова:

Каждому аргументу соответствует столько палочек, каково значение этого аргумента. Если функция f определена на данном наборе значений переменной x 1 …x n , то в результате работы машины Тьюринга на ленте должно остаться такое количество палочек, записанных подряд, которое равно значению функции на данном наборе. Если функция f не определена на данном наборе, то машина Тьюринга должна работать бесконечно.

Начальная конфигурация – считывание крайней левой палочки.