В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 10
Описание файла
PDF-файл из архива "В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций)", который расположен в категории "". Всё это находится в предмете "теория интеллектуальных систем" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 10 страницы из PDF
Пусть n = γ ( P ) . Следовательно, f = f Pn и значит f = U (n, x)ч.т.д.Следствие.Для всякого k ≥ 1 существует частично рекурсивная функцияU k (n, x1 ,..., xk ) универсальная для всех k-местных частично рекурсивныхфункций. Это делается с использованием нумерационных функций.Полагаем`U 2 (n, x1 , x2 ) = U (n, p( x1 , x2 ))(12)U 3 (n, x1 , x2 , x3 ) = U (n, p( p( x1 , x2 ), x3 ))и так далее.58Покажем, например, что функция U 2 (n, x1 , x2 ) удовлетворяет нужнымусловиям. Во-первых, функция U 2 - частично рекурсивна , т.к. являетсясуперпозицией частично рекурсивных функций.
Во-вторых, функцияf n ( x1 , x2 ) = U 2 (n, p( x1 , x2 )) - частично рекурсивна, т.к. получается из частичнорекурсивной подстановкой константы. Пусть теперь f ( x1 , x2 ) произвольнаячастично рекурсивная функция. Образуем функцию g ( x ) = f (l ( x ), r ( x )) ,где l , r- нумерационные функции.
Т.к. g ( x ) - частично рекурсивна, то существует n ,такое, что g ( x ) = U ( n, x )Теперь положим x = p( x1 , x2 ) и тогда имеемf ( x1 , x2 ) = g ( p( x1 , x2 )) = U (n, p( x1 , x2 )) = U 2 (n, x1 , x2 ) .Представляет интерес вопрос о существовании универсальной функциидля других рассмотренных выше классов Ч0 и Чпр - общерекурсивных ипримитивно рекурсивных функций соответственно.Теорема 3.Не существует общерекурсивной функции U k (n, x1 ,..., x k ) , универсальной дляkкласса × 0 - k -местных общерекурсивных функций при любом k ≥ 1 .Док-во.Пусть, наоборот, существует такая функция U k (n, x1 ,..., x k ) для некоторого к.Образуем функцию f ( x1 , x2 ..., x k ) = U k ( x1 , x1 , x2 ..., x k ) + 1 .
Согласно свойствууниверсальности существует n0 , такое, чтоU k (n0 , x1 ,..., x k ) = f ( x1 , x2 ..., xk ) = U k ( x1 , x1 , x2 ..., x k ) + 1Поскольку данные функции всюду определены, то они определены и приx1 =... = x k = n0 . Тогда получаем противоречивое равенствоU k (n0 , n0 ..., n0 ) = U k (n0 , n0 ..., n0 ) + 1.Значите предположение о существовании универсальной функции ложно.ч.т.д.В то же время справедлива.Теорема 4.Для каждого k ∈ N класс всех k -местных примитивно рекурсивныхфункций имеет общерекурсивную универсальную функцию.Доказательство данной теоремы довольно громоздко. Полностью оноприведено в [7] ,§5.Заметим, что из данной теоремы следует, что класс общерекурсивныхфункций шире класса примитивно рекурсивных функций, т.к. универсальнаяфункция не может быть примитивно рекурсивной (доказать) и являетсяобшерекурсивной.Дадим еще одно применение универсальной функции.
Пусть f : N 0 → N 0частичная функция. Функцию f 0 будем называть доопределением f , если f 059всюду определена и совпадает с f в ее области определения. Покажем, чторассмотрение частичных вычислимых функций вызвано существом дела, аименно - существуют частичные вычислимые функции, любое доопределениекоторых делает их невычисляемыми.Теорема 5.Существует частично рекурсивная функция f ( x ) , которая не может бытьдоопределена до общерекурсивной.Док-во.Рассмотрим функцию f ( x ) = sg U ( x , x ) , где Uуниверсальная функция. Данная функция частично рекурсивна ,т.к. онаполучается суперпозицией частично рекурсивных функций. Предположим ,чтосуществует общерекурсивная функция f 0 ( x ) ,которая является доопределениемдля f ( x ) .По свойству универсальности Uсушествует n ,такое что f 0 ( x ) = U (n, x ) .Поскольку f 0 ( x )всюду определена ,то она определена при x=n, и тогда значение U(n,n)определено и, следовательно ,определено значение f (n) = sg U (n, n) .
Посколькуf 0 ( x ) есть доопределение f ( x ) ,то в области определения их значиния должнысовпадать , Поэтому имеем f (n) = sg U (n, n) = U (n, n) = f 0 (n) .Однако ,последнее равенство дает противоречие , т.к. если U (n, n) = 0 ,тоsg U (n, n) = 1 ,если U (n, n) ≠ 0 ,то sg U (n, n) = 0 .Значит ,допущение осущесвовании рекурсивного доопределения для функции f ( x ) приводит кпротиворечию.ч.т.д.60§10 Алгоритмически неразрешимые проблемы10 ) В данном разделе устанавливается алгоритмическая неразрешимость рядапроблем, относящихся к теории алгоритмов.
Будем рассматривать такназываемые массовые проблемы. Массовая проблема представляет собойбесконечную серию индивидуальных задач. Например, индивидуальной задачейявляется такая: обладает ли заданным свойством Q конкретная частичнорекурсивная функция. Совокупность всех таких задач (для всех частичнорекурсивных функций) образует массовую проблему распознавания свойства Q.Мы ограничимся такими массовыми проблемами, в которых всеиндивидуальные задачи имеют двузначный ответ ("ДА" или "НЕТ").Массовая проблема П является алгоритмически разрешимой, еслисоответствующая характеристическая функция f , которая определяетсясоотношением: 1 ⇔ инд зада ÷ а π ∈ П имеет ответ " ДА"f (π ) = 0 ⇔ инд зада ÷ а π ∈ П имеет ответ " НЕТ"(1)является вычислимой.Решая конкретную массовую проблему следует считаться с возможностью,что она может оказаться алгоритмически неразрешимой, поэтому необходимоиметь представление о технике доказательства неразрешимости.
Основнойметод, применяемый в доказательствах алгоритмической неразрешимости,базируется на следующем рассуждении. Пусть (имеем две массовые проблемыП1 и П2. Пусть имеется алгоритм А , который по всякой индивидуальной задачеπ 1 ∈ П1 строит индивидуальную задачу π 2 ∈ П2 , такую, что выполнено:π 1 имеет "ДА" ⇔ π 2 имеет "ДА" .В этом случае говорят, что проблема П1 сводится к проблеме П2. Еслипроблема П1 неразрешима, то проблема П2 также неразрешима.
Действительно,пусть это не так, и проблема П2 разрешима. Тогда можно построитьразрешающий алгоритм для проблемы П1. Берем произвольную индивидуальнуюзадачу π 1 ∈П1 . Имея алгоритм А ,строим индивидуальную задачу π 2 = A(π 1 ) .Теперь применяем к задаче π 2 существующий по предположению разрешающийалгоритм для проблемы П2. Если задача π 2 имеет ответ "ДА", то для задачи π 1полагаем ответ "ДА", в противном случае, для задачи π 1 полагаем ответ "НЕТ".Поскольку, по условию, проблема П1 неразрешима, то получим противоречие.Значит, проблема П2 неразрешима. Данное рассуждение называется методомсводимости, и его применение возможно, если уже имеется запас проблем,алгоритмическая неразрешимость которых уже установлена.
Приведем теперьнекоторые из таких проблем.20 ) Рассмотрим так называемую проблему самоприменимости машинТьюринга. Она заключается в следующем. Рассматриваются, машины Тьюринга,внешние алфавиты которых содержат символы О, 1 (наряду с другими). Длякаждой машины Тьюринга Т построим Код (Т) который является ( 0,1) - словом,61и запустим машину Т в начальной конфигурации q1 Код (T) .
Если машина Тостанавливается (т.е.попадает в заключительное состояние) череэ конечноечисло шагов, он называется самоприменимой в противном случае несамоприменимой.Заметим,что имеются как самоприменимые так и несамоприменимые машиныТьюринга.Например, несамоприменимой будет машина Т1 ,у которой всекоманды имеют вид qi a j → qi a j E (в правых частях команд нетзаключительного состояния), самоприменимой будет машина Т2 ,у которой всекоманды имеют вид qi a j → q0a j E ( в правых частях команд имеетсязаключительное состояние).Проблема самоприменимости состоит в том , чтобы по любой машине ТьюрингаТ определить ,является она самоприменимой или нет.Условимся ,что машинаТьюринга m решает проблему самоприменимости ,если для любой машины Тначальную конфигурацию q1 Код (T) она переводит в q11 ,если машина Тсамоприменима ,и в q1 0 , если машина Т несамоприменима.Теорема 1.Не существует машины Тьюринга m , решающей проблемусамоприменимости, т.е.
проблема самоприменимости алгоритмическинеразрешима.Док-во.Предположим противное, т.е. пусть существует машина Тьюринга m решающаяпроблему самоприменимости в указанном выше смысле. Построим новую′машину m0 , добавив новое состояние q0 и объявив его заключительным, атакже добавив новые команды для состояния q0 , которое было заключительнымвm:q0 1 → q0 1Eq 0 → q ′ 0E00(α )(β )Рассмотрим теперь работу машины m0 . Пусть Т - произвольная машина,если Т - самоприменима, то начальная конфигурация q1 Код (T) перейдет спомощью команд машины m через конечное число шагов в конфигурацию q0 1 ,далее применяется команда (α ) , и машина, m0 никогда не остановится. Если Т- несамоприменимая, то начальная конфигурация q0 Код ( T) перейдет спомощью команд машины m через конечное число шагов в конфигурацию q0 0 ,далее применяется команда ( β ) , и машина m0 остановится.
Значит машина m0применима к кодам несамоприменимых машин Т и неприменима к кодамсамоприменимых машин Т. Теперь рассмотрим Код(m0) и применим машинуm0к начальной конфигурации q1Код(m0). Сама машина m0 является либо62самоприменимой, либо несамоприменимой. Если m0 самоприменима, то подоказанному, она никогда не остановится, начав с q1Код(m0) и потому онанесамоприменима. Если m0 несамоприменима, то по доказанному, онаостанавливается через конечное число шагов, начав с q1Код(m0), и потому онасамоприменима.
Получили противоречие, которое является следствиемдопущения существования машины m , реализующей проблемусамоприменимости.ч.т.д.Приведем еще один пример неразрешимой проблемы. Проблемой останованазывают проблему, заключающуюся в том, чтобы по любой машине ТьюрингаТ и слову Р в ее внешнем алфавите узнать, применима ли Т к начальнойконфигурации q1 P .Проблема останова алгоритмически неразрешима, т.к. если бы она быларазрешимой, то взяв в качестве Рслово Код(Т), мы получили бы разрешимость проблемы самоприменимости.2 0 ) Приведем теперь неразрешимые проблемы, связанные о проверкой свойствчастично рекурсивных функций. Пусть U (n, x ) - универсальная функция дляодноместных частично рекурсивных функций и соответствующая ей нумерацияфункцийf0 ( x), f1 ( x),..., fn ( x),...где fn ( x) = U (n, x)(2)Теорема 2.Проблема "функция f n всюду определена", n ∈ N 0 алгоритмическинеразрешима.Док-во.Определим характеристическую функцию данной проблемы1 , еслиg ( x) = 0f x всюду оп ределена,else(3)Определим новую функцию Ф(x)? где f x ( x) + 1 , если f xФ ( x) = 0,всюду оп ределенаelse(4)Заметим,что функция Ф(x) всюду определена.