Есть ли скрытая связь между существованием несчетных множеств и неразрешимостью проблемы остановки?

9

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

halting-problem Ленар Хойт
источник
10
Да, диагональный аргумент!
Махди Черагчи
1
@MCH Я думал, что, возможно, есть и другая характеристика, кроме диагонального аргумента, который связывает оба. Этот вопрос может быть слишком размытым для SE.
Ленар Хойт
4
Это может быть частичная ссылка: ясно, что множество всех языков в данном алфавите неисчислимо. Однако набор всех машин Тьюринга исчислим. Это прямо подразумевает существование неразрешимых проблем. Однако это рассуждение ничего не говорит о проблеме остановки.
042
9
Конечно, существуют теоретико-множественные модели ZFC, где все множества счетны (хотя и не в модели), но проблема остановки всегда неразрешима. Смотрите этот вопрос MathOverflow .
Питер Шор
4
Пожалуйста, пожалуйста, скажите, пожалуйста, неразрешимость отныне.
Виджай Д

Ответы:

14

Это не скрытая ссылка, а явная, с использованием языка теории категорий, а также очень естественный вопрос для изучения и изучения. На эту тему есть немало материала.

Виджай Д
источник