Машина Тьюринга для правильного вычисления функции

Дальневосточный Государственный Гуманитарный Университет

Факультет: ФЕНМиИТ

 

 

 

 

 

 

 

 

Реферат

По теме: «1.Самоприменимые алгоритмы;

2.Машина Тьюринга для правильного вычисления функции

 »

 

 

 

 

 

 

Выполнила: Желдоченко Е.А.

Группа: 232

 

 

 

1.Самоприменимые алгоритмы

Теоретические сведения:

 

В первом приближении самоприменимым называют алгоритм (скажем, нормальный  алгоритм Маркова (НАМ)), который применим к самому себе. Однако это некорректное определение, поскольку на вход НАМ можно подавать только слова (линейные последовательности символов), а НАМ таковым не является. Поэтому, чтобы сделать это определение корректным, надо как-то «вытянуть» НАМ в линию. Для этого вводится понятие записи алгоритма: записью НАМ называется слово, состоящее из последовательно записанных через точку с запятой формул подстановки этого алгоритма (точки с запятой отделяют друг от друга соседние формулы). При этом предполагается, что точки с запятой не входят в формулы; если это не так, то вместо точки с запятой можно использовать любой другой символ, не входящий в формулы.

Пусть, к примеру, имеются следующие алгоритмы H1 и H2:

    

H2:

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

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

 

 

Алгоритм же H2 несамоприменим, т.к. он зацикливается на своей записи:

4 5 5 5

а→b;b→bb  → b→b;b→bb → bb→b; b→bb → bbb→b;b→bb →...

 

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

Пример 1

Построить НАМ, который несамоприменим, но применим к любому слову в алфавите {a,b}.

Решение

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

 

 

Пример 2

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

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

Пусть НАМ имеет вид . Тогда можно использовать

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

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

 

 

 

 

 

 

 

 

2.Машина Тьюринга для правильного вычисления функции

 

Соглашение:

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

ми, а все остальные клетки содержат символ #. При этом головка

расположена непосредственно слева от входных данных.

 

2. После завершения работы результатом является то слово на ленте (по-

следовательность букв между соседними "#"), на которое указывает

головка. Последнее означает, что головка остановилась внутри слова

или непосредственно слева от него. В частности, если головка оста-

новилась на букве # и в соседней справа клетке также стоит #, то

результат — пустое слово.

 

3. При вычислении функций нескольких переменных аргументы на лен-

те разделяются одним символом #.

 

 

 

 

 

Литература:

1. М.В. Шаповалов, Л.А. Моисеенко УМК по дисциплине «теория алгоритмов» стр [60-64].

2. lpcs.math.msu.su/vml2008/t5turing.pdf

Хабаровск 2014