функции - Невычислимая функция

Так как нормально вычислимых функций счётное множество, то перенумеруем все эти функции. Таким образом, всякая нормальная функция имеет некоторый номер. Пусть P0, P1, P2 ... - все нормально вычислимые функции. Определим функцию f следующим образом:
f(x) = {Px(x)+1, если Px(x) определено; 1, если Px(x) не определено.

Если предположить, что функция f(x) нормально вычислима, то получим, что f(x) = Pk(x) для некоторого k из множества N0 (натуральные и 0). Так как f(x) всюду определена, то и Pk(x) определена всюду на N0.

Тогда f(k) = Pk(k). Но по опрeделению функции f(x) имеем: f(k) = Pk(k)+1.
Из двух последних равенств получаем противоречивое равенство: Pk(k) = Pk(k)+1.
Таким образом, определённая выше функция f(x) не является нормально вычислимой. И потому не является вычислимой по Тьюрингу и частично рекурсивной, то есть для вычисления всех её значений не существует алгоритма.

Взято отсюда: Дискретная математика. Кулабухов С.Ю, страница 143.