Неразрешимость проблемы остановки

Тьюринг был заинтересован следующей проблемой: верно ли, что всякое подмножество натуральных чисел разрешимо. Легко понять, что нет. Действительно, множество подмножеств натуральных чисел несчетно, но, так как множество всех машин Тьюринга счетно, то и множество всех разрешимых множеств счетно. Тем самым, почти все подмножества натуральных чисел неразрешимы.

Тьюринг привел явную конструкцию такого множества. Как мы увидим, он использовал метод, разработанный Кантором для доказательства несчетности множества действительных чисел. Гедель использовал этот же метод для доказательства теоремы неполноты, с помощью которого он построил утверждение J, смысл которого для натуральных чисел моет быть трактован как «J не теорема».

Тьюринг сконструировал диагональное множество K следующим образом:

K = {n | M_n(n)v}.

То есть, K состоит из машин Тьюринга, которые останавливаются на своих собственных программах. Легко понять, что K является рекурсивно перечислимым. Пусть дополнение к K также является рекурсивно перечислимым, и d — номер машины Тьюринга, останавливающейся на дополнении к K. То есть, для любого n,

n? K? M_d?(n)v .

Подставим d вместо n:

d? K? M_d?(d)v .

По определению d:

d? K? M_d?(d)v .

Тем самым, мы получаем.

d? K? d? K,.

что является противоречием. То есть, наше предположение о том, что дополнение к K перечислимо, ложно, и K не разрешимо. Из этого следует, что не существует алгоритма, который бы по машине Тьюринга и ее входу мог определить, останавливается ли машина на этом входе или нет, и, тем самым, проблема остановки неразрешима.