Wiem, że problem zatrzymania jest ogólnie nierozstrzygalny, ale niektóre maszyny Turinga oczywiście zatrzymują się, a niektóre oczywiście nie. Która ze wszystkich możliwych maszyn Turinga jest najmniejsza, w której nikt nie ma dowodu, czy się zatrzymuje?
halting-problem
Aaron
źródło
źródło
Odpowiedzi:
Największe maszyny Turinga, dla których można rozwiązać problem zatrzymania, to:
Komentarz Kaveha i odpowiedź Mohammada są poprawne, więc w celu formalnej definicji standardowych / niestandardowych maszyn Turinga zastosowanych w tego rodzaju wynikach zobacz Turlough Neary i Damien Woods pracują na małych uniwersalnych maszynach Turinga, np . Złożoność małych uniwersalnych maszyn Turinga: ankieta (zasady TM 110 są mało uniwersalne).
źródło
Chciałbym dodać, że istnieje kilka maszyn Turinga, dla których problem zatrzymania jest niezależny od ZFC.
Na przykład weź maszynę Turinga, która szuka dowodu sprzeczności w ZFC. Zatem, jeśli ZFC jest spójne, nie zatrzyma się, ale nie można tego udowodnić w ZFC (z powodu drugiego twierdzenia Gödela o drugiej niepełności).
Więc nie chodzi tylko o to, że nie znalazłem jeszcze dowodu, czasem dowody nawet nie istnieją.
źródło
Nikt nie ma dowodu na to, czy Universal Turing zatrzyma się czy nie. W rzeczywistości taki dowód jest niemożliwy z powodu nierozstrzygalności problemu Haltinga. Najmniejsza jest 2-state 3-symbol uniwersalny Turinga maszyna, która została znaleziona przez Alex Smith za który otrzymał nagrodę w wysokości $ 25.000.
źródło
niedokładnie sformułowane, ale uzasadnione pytanie ogólne, które można zbadać na kilka szczególnych sposobów technicznych. istnieje wiele „małych” maszyn mierzonych stanami / symbolami, w których zatrzymanie jest nieznane, ale żadna „najmniejsza” maszyna nie jest możliwa, chyba że ktoś wymyśli jakąś uzasadnioną / kwantyfikowalną metrykę złożoności bazy TM, która uwzględnia zarówno stany, jak i symbole (najwyraźniej jak dotąd nikt jej nie zaproponował).
źródło