Игошин Математическая логика и теория алгоритмов (1019110), страница 92
Текст из файла (страница 92)
Возникает массовая проблема распознавания самопримеияемых машин Тьюринга, состоящая в следующем. По заданной ФУнкциональной схеме (программе) машины Тьюринга установить, к какому классу относится машина: к классу самоприменимых машин или к классу несамоприменимых машин. 369 Теорема Зб.З. Проблема распознавания саиоприменимых машин Тьюринга алгоритмически не разрешима. Д о к а з а те л ь с т в о. Допустим противное, т.е.
алгоритм для такого распознавания существует. Значит, на основании тезиса Тьюринга, существует машина Тьюринга, реализующая данный алгоритм. Пусть Π— такая машина. На ее ленту заносится соответствующим образом закодированная программа той или иной машины Тьюринга. При этом, если машина самоприменима, то занесенное слово перерабатывается машиной О в какой-то символ и (имеющий смысл утвердительного ответа на поставленный вопрос о самоприменимости). Если же машина несамоприменима, то занесенное на ленту слово, кодирующее ее программу, перерабатывается машиной О в какой-то символ т (имеющий смысл отрицательного ответа на поставленный вопрос). Рассмотрим теперь такую машину Тьюринга О,, которая по- прежнему перерабатывает несамоприменимые коды в т, а к само- применимым кодам машина О, уже не применима.
Такая машина получается из машины О, если следующим образом слегка изменить ее программу: после появления символа о вместо остановки машина должна неограниченно его повторять. Итак, О, применима ко всякому несамоприменимому коду (вырабатывая символ т) и не применима к самоприменимым кодам. Это приводит к противоречию, потому что такая машина не может быть ни самоприменимой, ни несамоприменимой. В самом деле, если машина О, самоприменима, то она не применима к своему коду. Значит, машина несамоприменима. Противоречие.
С другой стороны, если машина О, несамоприменима, то ее код должен перерабатываться самой машиной О, в символ т. Значит, О, применима к собственному коду, т.е. самоприменима. Снова противоречие. Оно и доказывает теорему. П На основании доказанной теоремы устанавливается алгоритмическая неразрешимость и некоторых других массовых проблем, возникающих в теории машин Тьюринга, например проблема распознавания применимости для машин Тьюринга, которая состоит в следующем. Заданы функциональная схема (программа) какой-нибудь машины Тьюринга и конфигурация в ней: узнать, применима ли машина к данной конфигурации или нет. Теорема Зб.4.
Проблема распознавания применимых машин Тьюринга алгоритмически не разрешима. Доказательство. Если бы существовал алгоритм для решения этой проблемы, то с его помощью можно было бы узнать, применима ли машина к слову, кодирующему ее собственную программу, т.е. самоприменима ли она. Но на основании предыдущей теоремы известно, что такого алгоритма не существует. П Алгоритмически неразрешимые проблемы в обшей теории алгоритмов. Итак, мы установили алгоритмическую неразрешимость 370 вух проблем, связанных с машинами Тьюринга: проблема распознавания самоприменимых машин Тьюринга (теорема 36.3) и проблема распознавания применимости для машин Тьюринга (теорема 36А). Каждое из этих утверждений может быть сформулировано и доказано и в обшей теории алгоритмов (в инвариантном виде).
Теорема о неразрешимости проблемы остановки (т.е. проблемы распознавания применимости алгоритма) звучит так. Не существует алгоритма, который по номеру х любого алгоритма (в произвольной, но фиксированной нумерации) и исходным данным у определял бы, остановится алгоритм при этих данных или нет; иначе говоря, не существует алгоритма В(х, у), такого, что для любого алгоритма А„(с номером д '(А) = х) )'1, если А,(у) определен, '10, если А„(у) не определен. Теорему об алгоритмической неразрешимости проблемы само- применимости алгоритмов можно сформулировать так. Не существует алгоритма В,(х) такого, что для любого алгоритма А„ )'1, еслиА„(х) определен, '(О, если А„(х) не определен.
Рассмотрим еще одну алгоритмическую проблему об алгоритмах и докажем ее неразрешимость. Это проблема определения общерекурсивности алгоритмов (и функций), т.е. проблема определения того, ко всяким ли допустимым начальным данным применим алгоритм. Прежде докажем лемму. .аелииа 36.5. Для любого перечисления любого множества Ф всюду определенных вычислииых (т. е. общерекурсивных) функций существует общерекурсивная функция, не входящая в это перечисление. Доказательство. Пусть цг — перечисление множества Ф, порождающее последовательность Аы Аь Ан ... всюду определенных вычислимых функций.
Введем функцию В(х) = А,(х) + 1. Так как А„общерекурсивна, то и В(х) общерекурсивна. Если предположить, что В е Ф, то В имеет некотоРый номеР хе и, следовательно, В(х) = А„,(х). Тогда в точке х = хе по определению В(хе) = = А„(х,)+ 1, а в силу последнего соотношения имеем В(хе) = А„,(х,). Получаем противоречие, из которого следует, что В не входит в перечисление, порождаемое цг. (Заметим, что если бы в перечислении допускались частичпые функции, то такое определение функции В не привело бы к "ротиворечию, а означало бы лишь, что В не определена в точке хы) П 371 Теорема Зб.б. Проблема определения общерекурсивности олгорит мов неразрешима, т.е.
не существует алгоритма В(х), такого, чт„ для любого алгоритма А, ]1, если А, всюду определен, В(х) = ( ' !О, если А„не всюду определен. Доказател ьств о. Допустим противное, т.е. такой алгоритм В(х) существует. Тогда он определяет общерекурсивную функцихз )(х).
Определим функцию я(х) следующим образом: к(0) = !ц~1)1у) = 1]," я(х+ 1) = !гу[у>б(х) л Ду) = !]. Так как номеров всюду определенных функций (и, следовательно, точек у, в которых)(у) = 1) бесконечное множество, то функция я(х) всюду определена. Ясно, что функция я(х) принимает значение 1 на каждой всюду определенной вычислимой (т.е. общерекурсивной) функции, т.е. является перечислением множества всех общерекурсивных функций.
Но, на основании предыдущей леммы, такого перечисления не существует. Противоречие. Следовательно, не существует и алгоритма В(х), определенного в условии теоремы, т.е. проблема определения общерекурсивности алгоритмов неразрешима. С) Раз нельзя указать единого алгоритма, отличающего всюду определенные вычислимые (т.е. общерекурсивные) функции от частично рекурсивных, попытаемся подойти к проблеме частично рекурсивных функций с другой стороны.
Может быть, возможно каждую частично рекурсивную функцию доопределить на неопределимых точках так, чтобы получилась рекурсивная (т.е. общерекурсивная) функция. Оказывается, и эта задача неразрешима, что следует из теоремы, приведенной ниже. Теорема Зб. 7. Существует такая частично рекурсивная функцияз, что никакая общерекурсивная функция я не является ее доонределением. До казател ьств о. Как и прежде, считаем, что выбрана некоторая вычислимая нумерация ф: )ч' — з А1* и для каждого алгоритма А„значение д-'(А„) = х — его номер в этой нумерации.
Рассмотрим следующую частичную функцию: ]'А„(х) + 1, если А„определен„ )(х) = 1не определена, если А„не определен. Ясно, что функция)(х) вычислима и, значит, частично рекурсивна. Пусть теперь «(х) — произвольная общерекурсивная функци» и х~ — ее номер в нумерации у, т.е. д '(я) = х . Так как е всюдУ 372 „пределена, то я(х ) = А„„(хг) определена и, следовательно, Ях ) = б(х,)+ 1.
Таким образом, для любой общерекурсивной функции я имеем7(х ) в я(х ). Это и означает, чтог в я. Теорема доказана. П Следовательно, существуют частичные алгоритмы, которые нельзя доопределить до всюлу определенных алгоритмов. Теорема Райса. Эта теорема описывает в рамках общей теории алгоритмов еще один достаточно обширный круг алгоритмически не разрешимых проблем.
Рассмотренные ранее подобные проблемы носили довольно экзотический характер: все они были так или иначе связаны с самоприменимостью алгоритма, когда алгоритм работает с собственным описанием (находится значение вычислимой функции 7„' в точке, являющейся ее собственным номером в выбранной нумерации вычислимых функций: Цх)). Теорема Райса, опираясь на неразрешимость этой проблемы, устанавливает алгоритмическую неразрешимость вообще всякого нетривиального свойства вычислимых функций.
По-прежнему имеется некоторая нумерация алгоритмов ~р: У-ь -~ А!', в которой каждый алгоритм А„имеет номер цг'(А„) = х. Этот же номер имеет и функциями„', которую вычисляет алгоритм А„. (Следует помнить, что одна и та же функция, будучи вычисляема разными алгоритмами, может иметь в данной нумерации много номеров. Но это обстоятельство не влияет на нижеследующую теорему.) Теорема 36.8 (Райс). Пусть С вЂ” любой непустой собственный класс вычислимых функций от одного аргумента (существуют как функции, принадлежащие С, так и вычислимые функции, не принадлежащие С).
Тогда не существует алгоритма, который бы по номеру х функции ~ определял бы, принадлежит г"„классу С или нет. Иначе говоря, множество (х: ~ а С) неразрешимо. Доказательство. Допустим противное,т.е. множество(х:у„а е С) разрешимо. Тогда оно обладает вычислимой характеристической функцией: )'1,еслиха М, т.е.7„'а С, '(О, если х я М, т.е. 7„' я С. Пусть |ь — нигде не определенная функция.
Рассмотрим сначала случай, когдауь я С. Выберем тогда какую-нибудь конкретную вычислимую функцию 7; а С и определим функцию г"(х, у): (~;(у), если значение7„(х) определено, г"(х,у) =1 ' ~Д(у), если значениег„(х) не определено. Функция г(х, у) вычислима. Для ее вычисления надо вычислять |(х): если Ях) определена, то этот процесс когда-нибудь ~становится и нужно будет перейти к вычислению7',(у); если же 373 Цх) не определена, то процесс не остановится, что равносильно вычислению функции,4(у).
Зафиксируем в функции Г(х, у) аргумент х. Тогда Гстанет вы числимой функцией от одного аргумента у. Номер этой функции в единой нумерации д вычислимых функций зависит от значения х т. е. является всюду определенной функцией «(х). Ясно, что функ ция я(х) вычислима, так как является суперпозицией двух вычис лимых функций: я(х) = ср 'Щх, у)).
Таким образом, Г(х, у) =7 ья(у) и, значит, ) 7,(у), если 7;(х) определена, ~Д(у), еслибы„(х) не определена. Отсюда ясно, что )',я в С тогда и только тогда, когда У,'<л — — У; (так как7; я С), т.е. Цх) ойределена. (В случае же, когда7„(х) не определена, мы имеем Д„.> — — У и, следовательно, У „> я С, так как 4 я С.) Другими словами, я(х) в М тогда и только тогда, когда Цх) определена. Это означает, что характеристическая функция ум на аргументах я(х) имеет вид: ) 1, еслибы„(х) определена, 10, если У;(х) не определена.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
