2.2. Диагональная конструкция

В предыдущем разделе мы построили универсальную функцию для класса всех вычислимых функций одного аргумента. Можно ли сделать то же самое для класса всюду определённых вычислимых функций? Оказывает­ся, что нет.

мирования

ЦГп = {х | (п, х) е

Диагональная конструкция

Теорема 8. Не существует вычислимой всюду опре­делённой функции двух аргументов, универсальной для класса всех вычислимых всюду определённых функций одного аргумента.

<] Воспользуемся «диагональной конструкцией» — точно так же доказывается несчётность множества всех бесконечных десятичных дробей. Пусть U — произволь­ная вычислимая всюду определённая функция двух ар­гументов. Рассмотрим диагональную функцию и(п) = = U(п, п). Очевидно, на аргументе п функция и совпада­ет с функцией Un, а функция d(n) = и(п) + 1 отличается от Un. Таким образом, вычислимая всюду определённая функция d(n) отличается от всех сечений Un, и потому функция U не является универсальной. >

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

Тем не менее, часть рассуждения остаётся в силе.

Теорема 9. Существует вычислимая функция d (с на­туральными аргументами и значениями), от которой ни­какая вычислимая функция / не может всюду отличать­ся: для любой вычислимой функции / найдётся такое чи­сло п, что f(n) = d(n) (последнее равенство понимается в том смысле, что либо оба значения f(n) и d(n) не опре­делены, либо оба определены и равны).

<] По существу всё уже сказано: такова диагональная функция d(n) = U(п, п) (здесь U — вычислимая функция двух аргументов, универсальная для класса вычислимых функций одного аргумента). Любая вычислимая функ­ция / есть Un при некотором п и потому f(n) = Un(n) = = U(n, п) = d(n). >

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

<] Такова, например, функция d'(n) = d(n) + l, где d — функция из предыдущей теоремы. В самом деле, любое её всюду определённое продолжение всюду отличается от d (в тех местах, где функция d определена, функция d! наединицу больше ё и потому любое продолжение функ­ции ё' отличается от ё; там, где ё не определена, любая всюду определённая функция отличается от ё). >

19. Докажите, что и сама функция Л из доказательства предыдущей теоремы не имеет вычислимого всюду опреде­лённого продолжения.