Учебное пособие: Алгоритмічні проблеми

1, якщо xÎ W_x

f(x)=0, якщо xÏ W_x

Припустимо, що функція f обчислювана, і приведемо це припущення до протиріччя. Саме за допомогою діагонального методу ми побудуємо обчислювану функцію g, таку, що Dom(g)¹W_x (= Dom(ф_x )), при всіх х, чого, мабуть, бути не може.

Як завжди при використанні діагонального методу, ми будемо прагнути до того, щоб множина Dom(g) відрізнялося від W_x у njxці х. Тому будемо домагатися того, щоб

x Î Dom (g)Ûx ÏW_x

Визначимо тепер функцію g у такий спосіб:

g(x)=0, якщо xÏ W_x (тобто якщо f(x)=0),

не визначена, якщо xÎ W_x (тобто якщо f(x)= 1).

Оскільки функція f обчислювана, то (по тезі Черча) обчислювана і функція g, що і дає необхідне протиріччя. (Більш докладно, оскільки функція g обчислювана, візьмемо таке т, що g =f_m , тоді т ÎW_m Ûт Î Dom (g)Ûт ÏW_m , чого не може бути.)

Отже, ми робимо висновок, що функція f не є обчислюваною, і, отже, проблема «x Î W_x » нерозв'язна. ÿ

Зауважимо, що ця теорема зовсім не затверджує, що ми не можемо для будь-якого конкретного числа а сказати, чи буде визначене значення f_a (a ). Для деяких чисел зробити це дуже просто. Наприклад, якщо ми написали програму Р, щообчислює тотальну функцію, і Р=Р_a , то ми відразу