142
правки
Изменения
Нет описания правки
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </tex>.
По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>f(i) = U(i, i) \neq \bot</tex>. Значит, <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
}}
{{Лемма
|statement=
Существует вычислимая функция, значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
|proof=
Рассмотрим функцию
<tex>f(n) = \begin{cases}
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
\end{cases}</tex>
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>.
<tex>g(n) = U(i, n)</tex> для некоторого <tex>i</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>. Получили противоречие.
}}
