Сводимость - Рекурсивные функции

Помимо построения контрпримеров, в математических доказательствах часто используют метод сведения, который на практике мы часто формулируем в виде рассуждения типа "решение этой проблемы дает решение другой (известной) проблемы" или, в случае доказательства "от противного" - "если бы эта проблема решалась (таким-то образом), то другая (известная) проблема решалась бы (таким-то образом), что невозможно (приводит к противоречию)"

Приведем примеры применения метода сведения при доказательстве неразрешимости.

Теорема (примеры неразрешимости).

Следующие предикаты (проблемы) - неразрешимы:

Предикат 'X(y) определена' ( проблема остановки: предъявить алгоритм, распознающий, сходиться липрограмма x на входе y);

Предикат ' y X(y)=0' неразрешим. (проблема распознавания 0-функции).

Предикат ' y X1(y)=X2(y)' (проблема распознавания функциональной эквивалентности программ);

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

(Сведение к частичной проблеме остановки). Если бы функция

F1= x IF ( X(y), 1, 0)

Была вычислимой, то вычислимой была бы и функция x f1(x, x),что противоречит неразрешимости проблемы 'X(x) определена'.

(Сведение к проблеме остановки).

Пусть, от противного, функция

F2= x IF ( y X(y)=0, 1, 0)

Вычислима. Тогда функция f= x, y ( X(x), 0, ) вычислима как композиция вычислимых, x, y f(x, y)=0(u(x, y)). Потеоремео параметризации, существует вычислимая функция kтакая, что x, yK(x)(y)=f(x, y).

Тогда

Если X(x) определена, то y (f(x, y)=0)и f2(k(x))=1, и

Если X(x) не определена, то y(f(x, y) неопределена),следовательно, y (f(x, y) 0) и f2(k(x))=0.

Иначе говоря, если f2 вычислима, то разрешима проблема частичной остановки, что противоречит доказанному ранее.

(Сведение к проблеме распознавания 0-функции)

Пусть, от противного, функция

F3= x1,x2 IF( y (X1(y)=X2(y) ), 1,0)

Вычислима, а c0 - некоторый индекс 0-функции, y ( C0(y)=0). Тогдаодноместнаяфункция x с(x, c0)такжевычислима, что противоречит доказанному в предыдущем пункте.

Похожие статьи




Сводимость - Рекурсивные функции

Предыдущая | Следующая