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

Лемма:

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

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

[math]\triangleright[/math]

Рассмотрим функцию [math]f(n) = U(n, n) + 1[/math], где [math]U(n, n)[/math] - универсальная функция.

[math]\triangleleft[/math]