Существование перечислимого неразрешимого множества

В данной статье будет доказан теорема о существовании перечислимого, но неразрешимого множества. Напомню, что по теореме Поста перечислимое множества разрешимо тогда и только тогда, когда его дополнение перечислимо.

Основные определения, такие как вычислимость, разрешимость и перечислимость, можно найти в соответствующей статье.

1. УНИВЕРСАЛЬНЫЕ ФУНКЦИИ

"Определение. " Функция U(n,x) называется "универсальной " для класса вычислимых функций одного аргумента, если для каждого n функция U_n(x) является вычислимой и если все вычислимые функции (одного аргумента) встречаются среди U_n.

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

Теорема 1.1

"Существует вычислимая " функция двух аргументов, являющаяся универсальной для класса вычислимых функций одного аргумента.

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

Запишем все машины Тьюринга, вычисляющие функции одного аргумента, в последовательность возрастания их длины (количество команд):

M₀, M₁, M₂, ...

Пусть U(m,x) есть m-я машина от переменной x, т.е. M_m(x).

Таким образом, M_m будет вычислять U_m. А саму функцию U будет вычислять алгоритм, по номеру m определяющий какую машину Тьюринга запустить.

"Определение. " Множество W ⊂ N × N называют универсальным для некоторого класса множеств натуральных чисел, если все W_n={x|(n,x)∈ W} принадлежат этому классу и других множеств в классе нет.

Теорема 1.2

"Существует перечислимое " множество пар натуральных чисел, универсальное для класса всех перечислимых множеств натуральных чисел.

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

Пусть W — область значений универсальной вычислимой функции U. По определению W — перечислимое множество. Очевидно также, что оно является универсальным: W_n есть область значений функции U_n.

2. ДИАГОНАЛЬНАЯ КОНСТРУКЦИЯ

Рассмотрим следующий массив: его i-я строчка будет представлять собой значения функции U_i, а j-й столбец — значения функций при аргументе j (рассматриваются функции от натурального аргумента).

Таким образом пересечение i-й строчки и j-го столбца есть U_i(j). Очевидно, что данный массив — это таблица значений универсальной функции U от 2-х аргументов. Первый аргумент (номер соответствующей функции) откладывается по вертикали, а ее аргумент — по горизонтали.

В этой таблице могут быть пустые клетки, если функция U_i(j) не определена для j.

Рассмотрим следующую функцию u(n):u(n)=U(n,n)=U_n(n)Функция u(n) называется "диагональной " (очевидно, все ее элементы лежат на диагонали введенного нами массива).

Теорема 2.1

Существует вычислимая функция v(n) (с натуральными аргументами и значениями), от которой никакая вычислимая функция f не может всюду отличаться, т.е. найдется для любой f такое n, что f(n)=v(n).

"Замечание: " Последнее равенство означает либо равенство значений функций, либо то, что они обе не определены.

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

Действительно, такая функция v(n)=u(n)=U(n,n)

Предположим, существует такая вычислимая функция g(x), что при любом n g(n)≠ u(n).

Функция g(x) вычислима, следовательно, ей соответствует некоторый номер m, так что: U_m(x)=g(x). Тогда получаем для n=m:

g(m)=U_m(m)=U(m,m)=u(m), противоречие.

Следовательно, наше предположение неверно, и такая функция существует.

Однако благодаря рассуждениям в доказательстве предыдущей теоремы можно прийти к следующему факту:

Теорема 2.2

Не существует "вычислимой всюду определенной " функции двух аргументов, универсальной для класса вычислимых "всюду определенных " функций одного аргумента.

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

Рассмотрим функцию d(n)=u(n)+1, где функция u(n)=U(n,n).

Предположим обратное: функция U вычислимая всюду определенная универсальная функция для класса функций одного аргумента. Это означает, что существует такой номер m, что U_m(x)=d(x), для любого x.

Пусть x=m: d(m)=u(m)+1=U(m,m)+1=U_m(m)+1

Получаем противоречие, следовательно, такой функции U не существует.

Может возникнуть вопрос, как так получается, что мы в теореме 1.1 доказали существование универсальной вычислимой функции для всех вычислимых функций одного аргумента, но в то же время для всех вычислимых и "всюду определенных " функций такой универсальной функции нет?

Дело в том, что при присутствии в классе частичных функций значения d(m)=U_m(m) и u(m)+1=U_m(m)+1 могут быть равны в том смысле, что они оба будут не определены.

Докажем еще один важный факт:

Теорема 2.3

Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.

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

Возьмем функцию h(n)=u(n)+1, где функция u(n)=U(n,n), и рассмотрим ее продолжение.Действительно, там, где функция u определена, она равна h(n)=u(n)+1, следовательно, и ее продолжение не равно u(n).

Там же, где функция u не определена, любое продолжение h отличается от нее (так как продолжение является "всюду " определенным).Получаем, что продолжение h всюду отличается от u. Из теоремы 2.2 следует, что продолжение h (если оно всюду определено) не вычислимо.

3. ПЕРЕЧИСЛИМОЕ НЕРАЗРЕШИМОЕ МНОЖЕСТВО

Теорема 3.1

Существует перечислимое неразрешимое множество.

"Замечание: " Утверждение можно переформулировать, используя теорему Поста: существует перечислимое множество с неперечислимым дополнением.

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

Рассмотрим вычислимую функцию h(x), которая не имеет всюду определенного вычислимого продолжения, а, вернее, ее область определения H.

H перечислимо по определению перечислимого множества.

Докажем неразрешимость H. Действительно, пусть H разрешимо. Тогда функция

g(x)= h(x), если x ∈ H

0, если x ∉ H

является всюду определенным вычислимым продолжением функции h. Но у нас функция h не имеет такого продолжения, получаем противоречие. Следовательно, H перечислимое неразрешимое множество.

Добавим, что получившееся множество не что иное, как множество тех n, для которых U(n,n) определено, то есть тех n, при которых n-я машина Тьюринга (алгоритм) завершает работу (останавливается) на входе n. Часто говорят так: "проблема самоприменимости " (применимости машины Тьюринга к своему номеру) "неразрешима ".

Отсюда следует, что и область определения функции U является перечислимым неразрешимым множеством пар. А, следовательно, нельзя узнать алгоритмически, остановится ли машина Тьюринга на данном n или нет, что является широко известной в теории алгоритмов «проблемой остановки».

Литература:

* 1) Н.К. Верещагин, А. Шень «Вычислимые функции», М.: МЦНМО, 2002, 192 с. ISBN 5-900916-39-1

* 2) Дж. Булос, Р. Джеффри «Вычислимость и логика», М.: «Мир», 1994, 396с. ISBN 5-03-003067-0