logo
tsvpis

6.3 Неразрешимые проблемы

Определение. Проблема А (х∈А) называется разрешимой, если функция

Вычислима, то есть можно построить, например, МНР, которая по входу х через конечное время работы выдает 1 или 0, в зависимости от того, попадает х в множество А или нет.

Пример. Разрешимые проблемы:

  1. Четно ли число х.

  2. Простое ли число х.

  3. Ориентированный граф или нет(т.е. будет ли его матрица симметричной).

Определение. Проблема А (х∈А) называется частично разрешимой, если функция

Эффективно вычислима, т. е. можно написать МНР, которая в случае, если х∈А за конечное число шагов выпадает 1, и зацикливается, если

Знак означает, что алгоритм расходится при подаче на вход числа х.

Лемма 6.3 Если проблема А разрешима, то она частично разрешима.

Доказательство. У нас есть программа, которая вычисляет функцию ХА(х).

Припишем к этой программе блок, который зациклит программу, если она выдала ноль. Т.о. мы получим программу, которая вычисляет функцию

Лемма доказана

Теорема 6.4 Если проблема А (х∈А) и проблема (х∈сама проблема А будет разрешима.

Доказательство. Пусть у нас есть две программы: р1 и р2. Первая вычисляет функцию:

Вторая – функцию:

Наша задача – написать программу, которая вычисляет

Для этого поступаем следующим образом: возьмем вход х и сделаем один шаг программой р1 и один шаг программой р2. Если какая-то из них закончила работу, то ответом будет 1, если закончила работать программа p1, и ответом будет 0, если закончила работать программа p2. Потом опять берем вход х и делаем по два шага каждой программой и пишем в ответе 0 или 1 в зависимости от того, какая программа, p1 или p2 ­закончила работу. Если же ни одна из них не закончила работу, то берем вход х и делаем по три шага. Рано или поздно либо p1, либо p2 выдадут 1, следовательно, наша программа закончит работу.

Теорема доказана.

Теорема 6.5 Существуют неразрешимые проблемы (например, проблема останова).

Доказательство. Введем универсальную функцию a(n,k)=Pn(k)- результат работы программы номером n(нумерацию берем из теоремы 6.2), на выходе программы k. Заметим, что функция a(n,k) частично вычислима. В самом деле, по номеру n можно восстановить саму программу, а потом промоделировать ее работу на входе k.

Замечание. Функция φ(n) называется частично вычисляемой, если существует программа, которая либо выдает значение этой функции, если х принадлежит области определения φ, либо зацикливается, если х не принадлежит области определения φ (т.е. функция вычисляема не везде, а только на ее области определения).

Рассмотрим проблему останова в следующей постановке: машина Pn на входе k не зацикливается. Т. е. возможно написать программу, которая по коду исходной программы и входным данным выдает ответ 1, если Pn(k) не зацикливается, и 0 если зацикливается.

Для доказательства рассмотрим проблему останова в упращенном варианте. Докажем, что функция:

не вычислима.

Предположим противное, что функция g(n) вычислима. То есть у нас есть некоторая МНР, которая эту функцию вычисляет. Поступим следующим образом, рассмотрим функцию h(n)

То есть применяя «метод испорчивания по диагонали». Наша функция h(n) вычислима (при условии сделанного выше предположения вычислимости g(n)). Построенная нами функция h(n) не совпадает ни с какой другой частично вычислимой функцией, так как:

h(x)≠P1(x) (т.к. h(1)≠P1­(1))

h(i)≠Pi(i).

Таким образом, построенная функция h не совпадает ни с какой другой частично вычислимой функцией (их все мы смогли перенумеровывать в Теореме 6.2).Таким образом, функция h не совпадает ни с какой другой вычислимой функцией.

Теорема доказана.

Данный метод доказательтва («ипорчивание по диагонали») очень похож на доказательство нечетности множества действительных чисел.

Теорема 6.6 Вещественные числа нельзя перечитать.

Доказательство. Докажем, что нельзя пересчитать даже вещественные числа из интервала [0;1]. Пусть их можно пересчитать. х(1),х(2).. – последовательность, которая пересчитывает все числа из интервала [0;1]. Рассмотрим их десятичную запись:

х(1) =0, ,….

х(2)= 0, ,….

Рассмотрим число х, которое отличается от х(1) в первом знаке после запятой, от х(2) во втором знаке после запятой и т. д. х=0, ,… ( - означает(a+b) mod 10). Т.к. х – целое число, оно не совпадает ни с одним из хi.

Полученное противоречие доказывает несчетность множества вещественных чисел.

Теорема доказана.

В Тоереме 6.5 мы очень похожим образом строили функцию h, которая не совпадает ни с одной частично вычислимой функцией Pi.

Заметим, что проблема останова, не будучи разрешимой, тем не менее является частично разрешимой ( нетрудно промоделировать работу нашей машины при данном входе(такая функция либо выдает результат, либо зациклится).

Следствие 6.6 Проблема неостанова не является частично разрешимой.

Доказательство. Если бы проблема неостанова была бы частично разрешимой, то в силу доказанной выше частичной разрешимости проблемы отанова и Теоремы 6.4 мы получили бы, что проблема останова была бы разрешимой, но , как мы уже знаем, это не так по Теореме 6.5.

Следствие доказано.