Лекции по теории алгоритмов. Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов
![]()
|
Определим, в какое слово переработает это слово машина. Так машина находится в состоянии q1, обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q1 и строки 1 функциональной схемы. Это команда q2a0Л. После ее выполнения машина перейдет в следующее состояние:
После выполнения следующей команды q2*Л (записанной на пересечении столбца q2 и строки 1) машина перейдет в следующее состояние:
На пересечении столбца q2 и строки 1 в функциональной схеме машины Тьюринга записана команда q21Л, выполнение которой приведет к состоянию:
Полагая, что принцип работы с функциональной схемой машины Тьюринга изложен выше достаточно понятно, далее будем указывать только команды и результат их выполнения. q21→q21Л
q2a0→q31П
q31→q31П
q31→q31П
q3*→q3*П
q3a0→q1a0Л
q1*→q0a0
Таким образом, машина Тьюринга, определенная приведенной выше функциональной схемой, перерабатывает слово 11*1 в слово 111. Взяв в качестве исходных слов 111*111, 111*11 и т.п., можно усмотреть определенную закономерность в работе машины. Определение 3.1.1. Пусть на некотором множестве слов алфавита {a1, a2, … al} заданафункцияkпеременных, значениями которой являются слова в том же алфавите. Предположим, что имеется машина Тьюринга с алфавитом A={a0, a1, a2, … al} (nl), которая любой набор из k слов, входящий в область определения функции, записанный последовательно с промежутком в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе. А на любом наборе из kслов, не входящих в область определения функции, машина работает бесконечно. Тогда про такую машину Тьюринга говорят, что она вычисляет данную функцию, а сама функция называется вычислимой по Тьюрингу. 2. Не распознаваемость самоприменимости машины Тьюринга Приведем доказательство о не распознаваемости самоприменимости машины Тьюринга. Для этого нам понадобятся следующие теоремы и определения. Теорема 3.2.1. (о композиции машин Тьюринга). Каковы бы ни были машины Тьюринга Т1 и Т2 в алфавите А, можно построить работающую в том же алфавите такую машину Т, что для всех слов над алфавитом А будет выполнено равенство Т()=Т2(Т1()). Доказательство этой теоремы осуществляется просто. Внутренние состояния машин Т1 и Т2 (включая начальные состояния) переименовываются, причем в функциональной схеме машины Т1 переход в заключительное состояние заменяется переходом в начальное состояние машины Т2. При этом функциональные схемы объединяются в одну. Теорема 3.2.2. (о двоичном моделировании машины Тьюринга) Какова бы ни была машина Т1 в алфавите А, может быть построена такая машина Т в алфавите В={a0, 0, 1}, что для любых слов 1, 2 над алфавитом А и их кодов 1, 2 над алфавитом В Т(1)= Т(2) тогда и только тогда, когда Т1(1)= 2. Из этой теоремы следует, что в теории машин Тьюринга вполне можно рассматривать только те машины, которые работают в двоичном алфавите. Более того, кроме двух способов задания машины Тьюринга (в виде функциональной схемы и списка команд) возможен третий способ ее записи – в виде двоичного слова. При этом с помощью побуквенного обратимого (конструктивного) двоичного кодирования кодируются в общем случае: – символы внешнего алфавита и алфавита внутренних состояний, – символы, используемые при записи команд машины Тьюринга (Л, П, →, «оставаться на месте»), – символ, фиксирующий начало и конец программы, – символ, служащий разделителем между командами. Подчеркнем, что сама двоичная кодировка указанных символов может осуществляться разными способами (один из способов можно найти в []). Важно лишь то, что кодирование обязательно должно быть обратимым. В этом случае двоичная запись машины Тьюринга (Т), которую далее будем обозначать, следуя [] Т ( условная запись двоичного кода символа, фиксирующего начало и конец программы), будет однозначно задавать функциональную схему машины Т.
Рассматривая далее множество машин Тьюринга {T} будем считать, что каждая из них задана своей двоичной записью Т. Широко известная в теории алгоритмов массовая проблема остановки в этих терминах формулируется следующим образом. Применима ли машина Тьюринга Т, заданная своей записью Т, к двоичному слову p или нет? Еще одна известная массовая проблема теории алгоритмов – проблема самоприменимости – звучит так. Применима ли машина Тьюринга Т, заданная своей записью Т, к своей записи Т или нет? Очевидно, что проблема самоприменимости является частным случаем проблемы остановки. И если проблема самоприменимости алгоритмически неразрешима, то и проблема остановки относится к числу алгоритмически неразрешимых проблем. Тот факт, что проблема самоприменимости алгоритмически неразрешима, фиксирует следующая теорема. Теорема 3.2.3. (о нераспознаваемости самоприменимости). Не существует машины Тьюринга S, которая по записи Топределяла бы, самоприменима машина Т или нет. Доказательство. Предположим противное и допустим, что существует машина Тьюринга S, распознающая самоприменимость. Без ограничения общности можно считать, что S(C)=1, а S(Н)=0, где C – произвольная самоприменимая машина Тьюринга, а Н – произвольная несамоприменимая машина Тьюринга. Введем в рассмотрение машину Т1 с алфавитом внутренних состояний Q={q0, q1, q2 }, работающую в алфавите A={a0, 0, 1} в соответствие со следующей функциональной схемой.
Как видно из приведенной схемы, если первая буква исходного слова есть 0, то Т1()=. Если же исходное слово пусто или начинается с 1, то Т1 неприменима к слову , Т1()=1111… Определим теперь новую машину Тьюринга S1 как композицию машины S и машины Т1, полагая S1()=Т1(S()). Предположим далее, что машина S1 самоприменима. Это означает, что S1 – запись самоприменимой машины и по определению машины S S(S1)=1. В то же время, S1(S1)=Т1(S(S1))=Т1(1)=111…., что означает несамоприменимость машины S1. Противоречие налицо. Предположение о том, что машина S1 несамоприменима, влечет за собой (по определению машины S) соотношение S(S1)=0. Но по определению машины S1 S1(S1)=Т1(S(S1))=Т1(0)=0, что означает самоприменимость машины S1. Вновь получаем противоречие. Иными словами, предположение о существовании машины S, распознающей самоприменимость приводит к противоречию. Теорема доказана. Следствие. Проблема остановки алгоритмически неразрешима. Проблема самоприменимости в теории алгоритмов явилась первой алгоритмически неразрешимой проблемой, от которой отталкивались в дальнейших исследованиях. |