Известно, что с помощью счетного набора алгоритмов (характеризуемых числом Гёделя) мы не можем вычислить (построить двоичный алгоритм, который проверяет принадлежность) все подмножества N.
Доказательство может быть обобщено следующим образом: если бы мы могли, то множество всех подмножеств N было бы счетным (мы могли бы связать с каждым подмножеством число Гёделя алгоритма, который его вычисляет). Поскольку это неверно, это доказывает результат.
Мне нравится это доказательство, так как оно показывает, что проблема эквивалентна тому, что подмножества N не являются счетными.
Теперь я хотел бы доказать, что проблема остановки не разрешима, используя только один и тот же результат (несчетность N подмножеств), потому что, я думаю, это очень близкая проблема. Можно ли доказать это таким образом?
Ответы:
Теорема об остановке, теорема Кантора (неизоморфизм множества и его набор степеней) и теорема Гёделя о неполноте - все это примеры теоремы Лаврэра о неподвижной точке, которая говорит, что для любой декартовой замкнутой категории, если существует эпиморфное отображение то каждое имеет фиксированную точку.f : B → Be : A → ( A ⇒ B ) е: B → B
Хорошее введение в эти идеи см. В блоге Андрея Бауэра .
источник