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

Существование всюду определённой вычислимой универсальной функции невозможно, потому что это противоречит одному из свойств вычислимых функций. new2.intuit.ru neerc.ifmo.ru

Доказательство основано на «диагональной конструкции». new2.intuit.ru old.mccme.ru Если допустить, что существует всюду определённая вычислимая универсальная функция U, то можно рассмотреть функцию d(n) = U(n, n) + 1. new2.intuit.ru neerc.ifmo.ru

Доказательство: на аргументе n функция u совпадает с функцией Un, а функция d(n) отличается от Un. new2.intuit.ru old.mccme.ru Значит, вычислимая всюду определённая функция d(n) отличается от всех сечений Un, и поэтому функция U не является универсальной. new2.intuit.ru old.mccme.ru

Однако для класса всех вычислимых функций (в том числе частичных) это рассуждение не проходит, так как значение d(n) = U(n, n) + 1 не обязано отличаться от значения Un(n) = U(n, n), так как оба они могут быть не определены. new2.intuit.ru old.mccme.ru