В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 11

Кроме того f x ( x) + 1 , если g ( x) = 1Ф ( x) =  0 , если g ( x) = 0(5)Нам нужно доказать невычислимость функции g . Ясно, что извычислимости функции g следует вычислимость функции Ф. Предположим, чтофункция Ф вычислима. Тогда существует число n , такое, чтоФ(x)= U (n, x ) = f n ( x ) .Поскольку Ф(x)-всюду определена, то должно бытьg (n) = 1 .Значит, имеем Ф(n)= f n ( x ) и Ф(n)= f n ( x ) + 1 .Поскольку при x=n63функция Ф(x) определена, то получаем противоречие.

Следовательно Ф(x)невычислима, откуда следует, что функция g ( x ) - невычислима.ч.т.д.Обозначим через Wn область определения функции f n ( x ) впоследовательности (2).Теорема 3 .Проблема " n ∈Wn ", n ∈ N 0 алгоритмически неразрешима.Док-во.Рассмотрим характеристическую функцию проблемы:1 , если x ∈Wxf ( x) = (6)0,еслиxW∈xи построим новую функцию g ( x ) , где0 , если x ∈Wxg ( x) = (7)неопределена,еслиx∈WxЯсно, что из вычислимости функции f следует вычислимость функции g .Кроме того, справедливо соотношение ∀ x ∈ N 0 :g ( x ) определена ⇔ f x ( x ) не определена(8)Предположим теперь, что функция g вычислима.

Тогда существует числоm , такое, что g = f m . Тогда имеем m ∈Wm ⇔ g (m) определено ⇔ f m (m) неопределено ⇔ m ∈Wm . Получили противоречие, и поэтому g - невычислима и,следовательно, f невычислима.ч.т.д.Следствие ("Проблема применимости").Проблема " f x ( y ) -определена", x , y ∈ N 0 - неразрешима.Док-во.

Если бы данная проблема была разрешима,то и проблема " x ∈Wx "была бы разрешима. ч.т.д.30 ) Рассмотрим теперь алгоритмический приём, позволяющий эффективноработать с номерами частично рекурсивных функций. Пусть f ( x , y ) вычислимая функция. Фиксируем x=a и положим ga ( y ) = f (a , y ) . Функцияga ( y) - одноместная и вычислимая.

Значит, существует номер l , такой, чтоga ( y ) = f l ( y ) в последовательности (2). Покажем, что данный номер находитсяэффективно.Теорема 4.Для всякой вычислимой функции f ( x , y ) существует общерекурсивнаяфункция s(x), такая чтоf ( x , y ) = f s( x ) ( y )(9)Док-во.Пусть F - программа МПД , вычисляющая f ( x , y ) . Фиксируем x=a , ирассмотрим программу МПД Qa , где64T (1,2)Z(1)S(1)Qa :...S(1)FЛегко убедиться, что данная программа Qa вычисляет f (a , y ) . Пусть s(a) номер программы Qa .

Согласно построению f ( a , y ) = f s( a ) ( y ) . При этом,поскольку F фиксирована, то s(a) - эффективно вычислима.ч.т.д.Теперь, в силу вычисимости f ( x , y ) сущеструет n , такое, чтоf ( x , y ) = U 2 (n, x , y ) , где U 2 - универсальная функция для двухместныхчастично рекурсивных функций. Тогда в предыдущей конструкции при x=aимеем s=s(n,a) и выполнено f s( n, a ) ( y ) = U ( s(n, a ), y ) , где U - универсальная дляодноместных частично рекурсивных функций. Таким образом ,используя тезисЧерта и приведенную выше конструкцию ,установленаТеорема 5.(нумерационная)Существует общерекурсивная функция s(n,x) ? такая,что выполненоU ( 2 ) (n, x , y ) = U ( s(n, x ), y )(10)Данная теорема справедлива и в более общей ситуации, которую отметим бездоказательства.Теорема 6.Для любых m, n ≥ 1 существует общерекурсивная функция Snm ( k , x ) , такая,что выполненоU ( m + n ) ( k , x , y ) = U ( n ) ( Snm ( k , x ), y ) ,где k ∈ N 0 , x = ( x1 ,..., xn ) , y = ( y1 ,..., yn )Данное утвертдение называют S-m-n -теорема.Теорема 7.Проблема " f x = 0 ", x ∈ N 0 - неразрешима.

(Здесь 0 означает функцию,таждественно равную нулю).Док-во.Рассмотрим следующую функцию0 , если x ∈Wxf ( x, y) = не оп ределена , если x ∈WxЛегко видеть, что функция f ( x , y ) вычислима, поскольку универсальнаяфункция U (n, x ) вычислима. По теореме существует общерекурсивная функцияs(x) такая, что f ( x , y ) = f s( x ) ( y ) = U ( s( x ), y ) . Имеем по определениюx ∈Wx ⇔ f s( x ) ( y ) = 0(12)Если бы проблема f z ( y ) = 0 , z ∈ N 0 была разрешима, то тогда проблема" x ∈Wx " была бы разрешимой, что противоречило бы теореме 3.ч.т.д.65Следствие.Проблема “ f x ≡ f y ”, x , y ∈ N 0 неразрешима.Теорема 8. (Клини).Для любой частично рекурсивной функции h( x ) существует число a , такое,чтоf h(a ) = f a ( x)(13)Док-во.Пусть задана частично рекурсивная функция h( x ) .

Рассмотримвспомогательную функциюf ( y , x ) = U (h( s( y , y ), x )) ,где s - функция из тождества (10), существующая понумерационной теореме 5. Поскольку функция f ( y , x ) - частично рекурсивна,то существует число n ,такое,что f ( y , x ) = U (h( s( y , y ), x )) = U 2 (n, y , x ) .По нумерационной теореме 5 имеем f ( y , x ) = U ( s(n, y ), x )или U (h( s( y , y ), x )) = U ( s(n, y ), x ) . Теперь положим y=n и поскольку функция sобщерекурсивна, то s(n,n)определено. Тогда получаемU (h( s(n, n), x )) = U ( s(n, n), x ) .Обозначая s(n,n)=a имеемU (h(a ), x ) = U (a , x )илиf h(a ) ( x ) = f a ( x)ч.т.д.4 0 ) Теперь используем полученные результаты для установленияфундаментального факта, полученного Раисом, показывающего, что проблемапроверки любого нетривиального свойства частично рекурсивных функцийнеразрешима.Произвольное множество A ⊆ N 0 называется рекурсивным, еслисоответствующая характеристическая функция χ a ( x ) ,где 1 , если x ∈ Aχ a ( x) = 0 , если x ∈ A(14)вычислима.

Ясно, что рекурсивное множество А характеризуется тем, чтопроблема " x ∈ A " разрешима. Пусть F множество одноместных частичнорекурсивных функций, отличных от пустого множества и от множества всеходноместных частично рекурсивных функций. (т.е.F - нетривиальноемножество). Обозначим NF - множество всех номеров функций из F.Теорема 9. (Раис) Множестео NF нерекурсивно.Док-во.Предположим ,что множество NF рекурсивно.

Тогда его дополнениеN F = N 0 \ N F также рекурсивно, т.к.χ NF ( x) = 1 −& χ NF ( x)66По условию оба множества N F и N F непустые. Выберем некоторые α ∈ N F ,β ∈ N F и определим функциюα , если x ∈ NFg ( x) = (15)β,еслиx∈NFФункция g ( x ) общерекурсивна, т.к. выполнено равенствоg( x) = α χ N F ( x) + β χ N F ( x)По теореме 8 для функции g ( x ) существует число a , такое, чтоf g ( x) ( x) = f a ( x) .Тогда должно быть либо a ∈ N F либо a ∈ N F . Если a ∈ N F ,то, поопределению, f a ( x ) ∈ F и т.к. f g ( a ) = f a , то f g ( a ) ( x ) ∈ F .Однако,из a ∈ N Fследует по (15) g (a ) = β ∈ N F , т.е.

g (a ) ∈ N F и тогда f g ( a ) ( x ) ∈ F . Полученопротиворечие.Если a ∈ N F , то, по определению, f a ( x ) ∈ F и в силу f g ( a ) = f a имеемf g ( a ) ( x ) ∈ F .Однако, из a ∈ N F имеем по (15) g (a ) = α ∈ N F , т.е. g (a ) ∈ N Fи значит f g ( a ) ∈ F . Снова получено противоречие. Итак, число a не содержитсяни в одном из множеств N F и N F , чего быть не может, т.к.N 0 = N F ∪ N F .Противоречие является следствием предположениярекурсивности множества N F .Ч.Т.Д.Пусть Q - некоторое нетривиальное свойство одноместных частичнорекурсивных функций,т.е., имеются функции как обладающие своайством Q ,так и не обладающие свойством Q.Теорема 10Проблема " f обладает свойством Q” f ∈ E ′ , неразрешима.Док-воПусть проблема " f обладает свойством Q” f ∈ E ′ разрешима, т.е.

существуетМПД, которая для лбой f ∈ E ′ начальную конфигурацию (n,0,...), где n - номерфункции f , через конечное число шагов переводит в заключительнуюконфигурацию (1,*,...), если f обладает свойством Q , и в заключительнуюконфигурацию (0,*,...), если f не обладает свойством Q. Тогда для множестваN FQ номеров функций из E ′ , обладающих свойством Q, можно указатьразрешающую процедуру для проблемы n ∈ N FQ соотношением n ∈ N FQ ⇔МПД дает результат 1.Данное соотношение показывает, что множество N FQрекурсивно, что противоречит теореме 9.Ч.Т.Д.67Теорема 9 имеет многочисленные применения в теоретическомпрограммировании и позволяет доказать неразрешимость многих задач,связанных с вычислением на машинах.Большое число алгоритмически неразрешимых проблем имеется в книгеРоджерса X.[14].50 ) Приведем одно важное понятие теории алгоритмов, связанное свычислимостью.

Выше была установлена невычислимость характеристическойфункция предиката " x ∈Wx ". В то же время частичная характеристическаяфункция, определенная соотношением1 , x ∈Wxf ( x) = не оп ределена , elseявляется вычислимой. Это следует из тезиса Черча.

Поэтому говорят, чтопроблема " x ∈Wx ” полувычислима.Многие проблемы, будучи неразрешимыми, являются полувычислимыми.Дядим общееОпределение.Предикат M ( x ) на натуральных числах ( здесь x = ( x1 ,..., xn ) ) называетcяполувычислимым, если частичная характеристическая функция f ,1 , M( x) = Ине оп ределена , если M( x) = Лопределенная соотношением: f ( x) = вычислима.Замечание.

В литературе также используются равносильные термины :частичная разрешимость, рекурсивная перечислимость.Примеры:1. Любой разрешимый предикат полувычислим.2. Для любой вычислимой функции g ( x ) проблема " x ∈ D( g ) " являетсяполувычислимой, т.к. вычислима функция 1( g ( x )) (здесь 1 ( y ) = 1 , ∀y ).3. Проблема " x ∈ Wx " не является полувычислимой.

Действительно, если f соответствующая частичная характеристическая функция, тоx ∈ D( g ) ⇔ x ∈ Wx .Значит, D( f ) отличается от области определения любой одноместнойвычислимой функции. Поэтому f не может быть вычислимой.Теорема 11. Предикат M ( x ) полувычислим тогда и только тогда, когдасуществует вычислимая функция g ( x ) , такая, что M ( x ) = И ⇔ x ∈ D( g ) .Док-во.Если M ( x ) полувычислим и f - соответствующая частичнаяхарактеристическая функция, то по определению M( x) = И ⇔ x ∈ D( g ) .Обратное следует из примера 2.Определение.68Множество А из N 0 называется рекурсивно перечислимым, если частичная1 , x∈Aне оп ределена , еслихарактеристическая функция, где f ( x) = x∈Aвычислима.Это равносильно тому, что предикат " x ∈ A " полувычислим. Теорема 11 можетбыть перефразирована так.Теорема 12.Множество является рекурсивно перечислимым тогда и только тогда,когда оно является областью определения одноместной вычислимой функции.69§ 11.