Проблема остановки, неисчислимые множества: общее математическое доказательство?

29

Известно, что с помощью счетного набора алгоритмов (характеризуемых числом Гёделя) мы не можем вычислить (построить двоичный алгоритм, который проверяет принадлежность) все подмножества N.

Доказательство может быть обобщено следующим образом: если бы мы могли, то множество всех подмножеств N было бы счетным (мы могли бы связать с каждым подмножеством число Гёделя алгоритма, который его вычисляет). Поскольку это неверно, это доказывает результат.

Мне нравится это доказательство, так как оно показывает, что проблема эквивалентна тому, что подмножества N не являются счетными.

Теперь я хотел бы доказать, что проблема остановки не разрешима, используя только один и тот же результат (несчетность N подмножеств), потому что, я думаю, это очень близкая проблема. Можно ли доказать это таким образом?

Вейер
источник
Очевидно, что оба результата могут быть доказаны с использованием одного и того же метода (диагонализация). Однако я не думаю, что можно доказать неразрешимость проблемы остановки, просто используя несчетность семейства подмножеств ℕ, поскольку первое касается сравнения между RE и R , оба из которых являются счетными семействами подмножества ℕ.
Tsuyoshi Ito
Существует только много программ, имеющих доступ к оракулу, который снова характеризуется числом Годеля. Тем не менее, проблема остановки является среди этого счетного множества.
Дэвид Харрис

Ответы:

42

Теорема об остановке, теорема Кантора (неизоморфизм множества и его набор степеней) и теорема Гёделя о неполноте - все это примеры теоремы Лаврэра о неподвижной точке, которая говорит, что для любой декартовой замкнутой категории, если существует эпиморфное отображение то каждое имеет фиксированную точку.f : B Bе:A(AВ)е:ВВ

Хорошее введение в эти идеи см. В блоге Андрея Бауэра .

Нил Кришнасвами
источник
7
это довольно опрятно. Я не понимал, что был фактический формальный аргумент, объединяющий их.
Суреш Венкат
8
Я уже научился подозревать, что, если он выглядит одинаково и пахнет одинаково, существует категорический аргумент о том, в каком смысле он одинаков.
Виджай Д
2
ИМО, две действительно хорошие вещи в теореме Лаврэ в том, что (а) это скорее положительное, а не отрицательное утверждение, и (б) доказательство - полдюжины строк простых вычислений лямбда-исчисления.
Нил Кришнасвами
6
Читая вопрос, я подумал, что кто-то должен упомянуть теорему Лаврэ о неподвижной точке. Представьте мое восхищение, когда я прочитал ответ :-)
Андрей Бауэр
1
Быть эпиморфным - не правильное условие. Вам нужна точка-сюръективность, которая не подразумевает и не подразумевает условия эпиморфности. См. Замечание 2.3 ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem
fhyve