Geum.ru

Задача об остановке произвольной машины Тпри обработке произвольного слова t алгорифмически неразрешима

Вид материалаЗадача

Содержание


Если существует Д ,то существует Е.
Алгоритмы Маркова
Формат команды
Подобный материал:
Нормальные алгоритмы и тезис Маркова. Преобразование машин Тьюринга в нормальные алгоритмы. Понятие алгоритмической разрешимости. Задачи об остановке и печати машин Тьюринга.


Самоанализирующие машины Тьюринга


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

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

Aλ 0RB Aλ0RBBλ0RCCλ1RA

Bλ 1RC с разделителем:

Cλ 1RA Aλ0RBxBλ0RCxCλ1RАx

Ленточные знаки: λ,0,1.

Служебные знаки: A,B,C,R,x.

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

Т Т’ – самоанализирующая машина.


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


ТЕОРЕМА: Задача об остановке произвольной машины Т при обработке произвольного слова t алгорифмически неразрешима.


Иными словами, нельзя придумать универсальный алгоритм, в котором “да”- остановиться либо

“нет” – не остановиться. dT







Т-произвольная машина,

t-произвовольное слово.


# (докажем теорему от противного)
  1. Предположим, что задача об остановке машины Т алгорифмически разрешима.
  2. Это означает что существует алгоритм, который может быть реализован некой машиной Тьюринга Т.
  3. Построим машину Д, на ленте которой записано кодовое описание машины Т и кодовое описание входного слова.

Д: dT t +




кодовое описание кодовое описание

машины Т входного слова


Д обрабатывает эти два слова и пишет “+” , если Т останавливается при обработке t, и “-“ если этого не происходит.

4). Если этот алгорифм работает для любого случая (любой Т), то должно работать и для частного. В качестве начального слова можно выбрать описание машины, т.е. возьмем t = ddT. Т.е. Д может заниматься само анализом .


 dT ddT



Д: Aa bRB



 

t – почти dTпросто вместо А - , R - , В -

. Построим машину Е, которая будет на своей ленте иметь описание произвольной машины Т. Работа машины Е состоит в том, что она копирует описание dT , а затем работает как Д

Е
б
: +

-


dT ddT

Если существует Д ,то существует Е.



6)Построим машину F. F работает как E, отличие состоит в том ,что если после работы на входном слове dT машина Е останавливается с ответом “да ”, то машина F не останавливается, а продолжит бесконечное движение вправо без изменения знаков на ленте. Если же вдруг машина Е останавливается с ответом «нет» (что означает что машина Т не останавливается), то F просто остановится.


7) Если данный алгоритм работает для произвольного Т, то и для конкретного тоже будет работать. Положим Т=F , на ленте машины F мы записываем описание самой F т.е. получим, что машина F анализирует саму себя.


Получаем, что F не останавливается в том случае, если Е остановится с ответом “да”, а это означает что машина Т остановится. Поскольку Т=F, имеем ситуацию: F остановится, если F не остановится, и F не остановится , если F остановится, следовательно мы пришли к нелепости.


Получили противоречие, следовательно F не существует, значит Д не существует, следовательно в целом задача неразрешима.


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





T




D

t работает как T

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


Алгорифмическая неразрешимость задачи о печатании символа точно один раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте точно один раз алгоритмически неразрешима.


Док-во:

Без ограничения общности, возьмем знак «0». Итак, м. Тьюринга Т работает на чистой ленте.

1)Преобразим ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины. Очевидно, что D остановится тогда, когда остановится Т.

2)Построим машину Е, которая работает как D вплоть до ее остановки. После чего машина Е печатает «0» и тоже останавливается.

3) Т.о. получим, что символ «0» печатается точно один раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит задача о печатании нуля равносильна задаче об остановке машины на чистой ленте. Поскольку задача останова алгорифмически неразрешима, то и задача о печатании символа точно один раз тоже не разрешима.


Алгорифмическая неразрешимость задачи о печатании символа бесконечно много раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте бесконечно много раз алгоритмически неразрешима.


Док-во:

Без ограничения общности, возьмем знак «0». Итак, м. Тьюринга Т работает на чистой ленте.

1)Преобразим ее в новую машину Тьюринга D. Если Т не содержит в своем алфавите знака «0», то D просто совпадает с T. Если T имеет этот знак в своем алфавите, то в алфавите машины D знак «0» будет заменен любым знаком, ранее не входящим в алфавит машины. Очевидно, что D остановится тогда, когда остановится Т.

2)Построим машину Е, которая работает как D вплоть до ее остановки. После чего машина Е переходит в состояние А и печатает «0» бесконечно много раз (A  0RA).

3) Т.о. получим, что символ «0» печатается бесконечно много раз в том случае, если произвольная машина Т останавливается на чистой ленте. Значит задача о печатании бесконечно большого числа нулей равносильна задаче об остановке машины на чистой ленте. Поскольку задача останова алгорифмически неразрешима, то и задача о печатании символа бесконечно много раз тоже не разрешима.


Алгорифмическая неразрешимость задачи о печатании символа хотя бы один раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте хотя бы один раз алгоритмически неразрешима.


Док-во:

Без ограничения общности, возьмем знак «0». Итак, м. Тьюринга Т работает на чистой ленте.

1)Построим машину Е, которая работает как Т вплоть до ее остановки. После чего машина Е переходит печатает «0» и останавливается. Таким образом будет напечатан хотя бы один символ «0» (возможно и больше, если ранее машиной Т такой символ уже печатался)

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


Тезис Маркова. Нормальные алгоритмы (не закончено).


Тезис Маркова: любой вычислительный процесс можно преобразовать в нормальный алгоритм.


Алгоритмы Маркова


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


Формат команды (строки) следующий

{ai}  {bj} [•],

где

{ai} – последовательность символов, которая ищется в слове

 - знак перехода к операции записи

{bj} - последовательность символов, которая записывается вместо найденной

[•] - знак принудительного окончания алгоритма (необязательный параметр)

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


Например, алгоритм, состоящий из одной строки, вида

0  *

будучи примененным к слову в алфавите {0,1}, заменит все нули на звездочки.

В свою очередь алгоритм

0  * •

будучи примененным к слову в алфавите {0,1}, заменит на звездочку первый встреченный ноль.

Довольно сложная для реализации на машинах Тьюринга задача сортировки слова по возрастанию, допустим в алфавите {0,1,2}, решается при помощи Маркова весьма изящно:

20  02

10  01

21  12


Некоторые задачи переработки слов нельзя решить без расширения алфавита.

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

Рассмотрим алгоритм вида:

00  •

01  •

10  •

11  •

Если в слове случайно первыми двумя символами были нули (например, «001011»), то алгоритм действительно выполнит указанную задачу. Также работа закончится успешно, если в слове ни разу не встретилось два нуля подряд, а первыми символами оказалась пара 01 (например, «01011101»). Но в слове 1100101 выбросятся два нуля, которые вовсе не являются первыми символами слова. В этом случае существующий алфавит надо расширить вспомогательными буквами, которых нет в начальном слове и которые появляются в ходе вычисления. По сути, это некоторые аналоги внутренней памяти (состояний машин Тьюринга). Они вводятся с помощью формулы λ  α (α – вспомогательная буква) или, что более корректно, пары формул

λ 0  α 0

λ 1  α 1

Применив такие продукции к слову λ 1100101 λ получим:

λ α 1100101 λ

Дальше мы «тащим» эту букву по слову вправо, стирая и отсчитывая символы

(стерли первый):

α 0  β

α 1  β

(стерли второй):

β 0  •

β 1  •

Однако если мы расположит эти строки в обычном порядке, а именно:

λ 0  α 0

λ 1  α 1

α 0  β

α 1  β

β 0  •

β 1  •

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

Правильный алгоритм выглядит следующим образом.

β 0  •

β 1  •

α 0  β

α 1  β

λ 0  α 0

λ 1  α 1


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

α00 •

α01 •

α10 •

α11 •

α0 •

α1 •

λ 0  α 0

λ 1  α 1


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


Нормальные алгоритмы можно рассматривать как обобщение машины Тьюринга. Работу машин Тьюринга можно рассматривать как переработку начального слова некоторого нормального алгоритма. Этот алгоритм получается сразу же из таблицы машины.


Пусть существует следующая машина Тьюринга, которая печатает на чистой ленте последовательность 001001001001….

Aλ  0RB

Bλ  0RC

Cλ  1RA

Работа алгоритма происходит следующим образом (через запятую указаны пара: симовл-состояние)

A, 0 B, 0 0C, 001A

Построит алгоритм Маркова, для чего к внешнему алфавиту {0,1} добавляем внутренний алфавит {A,B,C...}

A  0B

B  0C

C  1A

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


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