Изменения

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

Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод.|универсальная функция]].

Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>\Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: \in \mathbb{N} \ g(n) \neq \bot </tex>.

По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>\Rightarrow g(i) = U(i, i)</tex>.  Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.

Существует [[Вычислимые функции#Основные определения | вычислимая функция]], значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.

0 & \text{, }U(n, n) \neq 0 \text{ и , }U(n, n) \neq \bot \\ 1 & \text{, }U(n, n) = 0 \\ \bot & \text{, }U(n, n) = \bot

Предположим, у нее существует всюду определенное продолжение <tex>g(n) = U(i, n)</tex>для некоторого <tex>i</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>g(i) = U(i, i) \neq \bot</tex> и определено значение <tex>f(i)</tex>. Но по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.}} {{Теорема|statement=Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').|proof=Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> {{---}} функция из леммы 2.

Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция <tex>g(n) = U\begin{cases} 1, & n \in Y \\ 0, & n \notin Y (i, n\in X)\end{cases}</tex> для некоторого множества <tex>iY</tex>.

<tex>g(i) = U(iЗаметим, i)</tex>. Поскольку что <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Но тогда по построению функции и является продолжением <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречиепротиворечит лемме 2.