Czy istnieje ukryty związek między istnieniem niepoliczalnych zbiorów a nierozstrzygalnością problemu zatrzymania?

9

Ponieważ oba dowody wykorzystują argument przekątny, zastanawiam się, czy istnieje niejasny związek między istnieniem niezliczonych zestawów nieskończonych a nierozstrzygalnością problemu zatrzymania. Czy problem zatrzymania byłby rozstrzygalny, gdyby wszystkie zestawy były policzalne?

halting-problem Lenar Hoyt
źródło
10
Tak, przekątny argument!
Mahdi Cheraghchi,
1
@MCH Myślałem, że może istnieć inna charakterystyka oprócz przekątnego argumentu łączącego oba te elementy. To pytanie może być zbyt rozmyte dla SE.
Lenar Hoyt,
4
Może to być link częściowy: oczywiście zestaw wszystkich języków danego alfabetu jest niepoliczalny. Jednak zestaw wszystkich maszyn Turinga jest policzalny. To bezpośrednio implikuje istnienie nierozwiązywalnych problemów. Jednak to rozumowanie nic nie wskazuje na problem zatrzymania.
042
9
Z pewnością istnieją teoretyczne modele ZFC, w których wszystkie zbiory są policzalne (chociaż nie w obrębie modelu), ale problem zatrzymania jest zawsze nierozstrzygalny. Zobacz to pytanie MathOverflow .
Peter Shor,
4
Proszę, odtąd proszę powiedzieć nierozstrzygalność.
Vijay D

Odpowiedzi:

14

To nie jest ukryty link, ale został wyraźnie określony przy użyciu języka teorii kategorii, a także bardzo naturalne pytanie, które należy zadać i przestudiować. Na ten temat jest sporo materiału.

Vijay D.
źródło