ТМВ-2020-Лекция-28.04.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Доказательство существования алгоритмически неразрешимых проблем.

Вычислимость, разрешимость и перечислимость

Вычислимые функции

\(f:N_{0}^k \rightarrow N_0\)

\(\exists\) алгоритм \(A:\) если \(f\) определено для набора аргументов, то \(A\) завершает на этом наборе аргументов работу за конечное число шагов и печатает значения функций. В ином случае алгоритм зацикливается.

Разрешимые множества

\(X \sqsubseteq N_0 - \)разрешимо, если характеристическая функция

\( f_x(n) = \begin{cases} 1 \mbox{, n $\in$ X } \\ 0 \mbox{, n $\notin$ X } \end{cases} \)

вычислима.

Перечислимые множества

\(X \sqsubseteq N_0, A-\) алгоритм, который в процессе работы печатает числа из \(X, \forall n \in X\) алгоритм печатает \(n\) через конечное число шагов и не печатает числа из \(\bar X\).

Когда множество является перечислимым?

Утверждение 1

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

Алгоритм: у нас есть всевозможные числа, на которых алгоритм работает: \(1, 2, 3, 4, ..., n, ...\). Алгоритм разделен на элементарные шаги, соответственно мы будем выполнять эти шаги последовательно для разных аргументов:

Перечислимое множество.png

Выполняем в новом алгоритме шаг старого алгоритма для другого входа. Таким образом гарантируется, что для любого входа выполнится произвольное наперёд заданное количество шагов. Можно сказать, за какое время выполнится \(p-й\) шаг для входа \(k\), где \(k<p\). Также требуется алгоритму конечная память.

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

Утверждение 2

2) Множество перечислимо, если оно - множество значений вычислимой функции.

Утверждение 2

3) Если \(A,B-\)перечислимы, то \(A \cup B\) и \(A \cap B-\) тоже перечислимы

Теорема Поста

1) Всякое разрешимое множество перечислимо.

2) Если \(A\) и \(\bar A-\) перечислимы, то \(A-\) разрешимо.

На какой вопрос теорема Поста не даёт ответа?

Существует ли перечислимое множество с неперечислимым дополнением?

Универсальные функции

Универсальная функция для некоторого класса вычислимых функций одного аргумента

{\(u_1, u_2, ... u_n, ...\)}, \(u_i: N_0 \rightarrow N_0\)

\(u(n,x)=u_n(x)\)

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

Утверждение 1

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

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

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

\(p_0,p_1,...,p_n,...\)

Например, в порядке возрастания длины(мы можем добыть по номеру программы текст программы).

Универсальная функция получает номер(#) программы. Соответственно после этого ей доступны коды этой программы, так как все программы перечислимы. Дальше мы эту программу вычисляем. Но так как эта программа - программа некой вычислимой функции, то эту функцию мы можем вычислить.

\(u(n,x)=I(p_n)(x)\), где(I-) интерпретатор.

Итого для всех вычислимых функций одного аргумента мы можем найти универсальную функцию

Утверждение 2

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

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

1) Пусть \(U:N_{0}^2 \rightarrow N-\)всюду определённая вычислимая функция двух аргументов.

Введем функцию \(u(n)=U(n,n)\)(диагонализация)

Введем функцию \(d(n)=u(n)+1\)

Замечаем, что для \(\forall i \exists x: d(x) \neq u(i,x)\)

Например, \(u(i,i) \neq u(i,i) + 1 = u(i) + 1 = d(i)\)

Кроме того, \(d-\)всюду определена и вычислима. \(d-\)функция одного аргумента.Следовательно, \(U\) не является универсальной.

Почему же одновременно выполнены утверждения 1 и 2?

Дело в том, что

\(u(i,i) \neq u(i,i) + 1 = u(i) + 1 = d(i)\) (смотри доказательство утверждения 2)

не работает в том случае, если функция всюду определённая.

Если функция не всюду определённая, то и \(d\), и \(u\) могут быть не определены, соответственно, неравенства не будет.

Остальные утверждения

Утверждение 1

Существует вычислимая функция \(u\) такая, что никакая вычислимая функция не может отличаться от \(u\) всюду.

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

Пусть \(u-\)универсальная функция для класса вычислимых функций одного аргумента

Пусть \(u(x)=U(x,x)\)

Пусть \(z-\) вычислимая функция одного аргумента

\(z=U_i\)

\(u(i)=U(i,i)=z(i)\)

Таким образом либо мы получаем какое-то значение, либо функции зацикливаются одновременно.

Утверждение 2

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

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

\(d(n) = u(n)+1\)

Предположим, что у этой функции существует всюду определённое вычислимое продолжение.

Пусть \(d_0-\)всюду определённое вычислимое продолжение \(d\), например\[ d_0(x) = \begin{cases} d(x) \mbox{, если d(x) определено} \\ \in N_0 \mbox{, если d(x) не определено } \end{cases} \]

По утверждению 1 \( \exists i:d_0(i)=u(i) \in N_0\)

\(d_0(i)=u(i)+1,\) если \(d_i\) определено

\(d_0(i) \neq u(i)\)

\(d_0(i) \in N_0,\) по \(u(i)\) не определено, если \(d(i)\) не определено

\(d_0(i) \neq u(i)\)

Следовательно, не существует \(d_0\) с указанными свойствами.

Утверждение(очень важное)

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

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

Возьмем функцию \(f -\) функция, не имеющая всюду определённого вычислимого продолжения.

Пусть \(F - \)область определения \(f\)

\(F - \) перечислимое множество по свойству 2

Если \(F - \)разрешимо, то

\( q(x) = \begin{cases} f(x) \mbox{, x \in F} \\ 0 \mbox{, иначе } \end{cases} \)

\(q -\)всюду определённое вычислимое продолжение \(f\)

Такого не может быть. Следовательно, \(F\) неразрешимое множество

//следствие

\(\bar F\) не является перечислимым

Проблема останова

Берём алгоритм, перечисляющий \(F - A\). Строим новый алгоритм:

\(B(x)\) запускает \(A\) и останавливается, когда \(A\) производит \(x\) и печатает 1. Не существует алгоритма, определяющего. завершит ли\(B\) работу на произвольном числе \(n\).

Проблема останова является алгоритмически неразрешимой.