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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.