Неотделимые множества

Лемма:

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

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

[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = U(n, n) + 1[/math], где [math]U(n, n)[/math] — универсальная функция. Предположим, у нее существует всюду определенное продолжение [math]g(n)[/math]. Это значит, что [math]\forall n: g(n) \neq \bot [/math] и [math]f(n) \neq \bot \Rightarrow g(n) = f(n)[/math]. По определению универсальной функции [math]g(n) = U(i, n)[/math] для некоторого [math]i[/math]. Тогда [math]g(i) = U(i, i)[/math]. Поскольку [math]g(n)[/math] всюду определена, то [math]f(i) = U(i, i) \neq \bot[/math]. Значит, [math]g(i) = f(i) = U(i, i) + 1[/math]. Получили противоречие. Таким образом, построенная функция [math]f(n)[/math] не имеет всюду определенного вычислимого продолжения.

[math]\triangleleft[/math]