Czy istnieje baza TM, która zatrzymuje się na wszystkich danych wejściowych, ale tej właściwości nie da się udowodnić?

17

Czy istnieje maszyna Turinga, która zatrzymuje się na wszystkich wejściach, ale z jakiegoś powodu ta właściwość nie jest możliwa do udowodnienia?

Zastanawiam się, czy to pytanie zostało zbadane. Uwaga: „nie do udowodnienia” może oznaczać „ograniczony” system dowodowy (który w słabym sensie uważa, że odpowiedź musi być twierdząca). Jestem oczywiście zainteresowany najsilniejszą możliwą odpowiedzią, tj. Taką, której nie da się zatrzymać przy wszystkich danych wejściowych, powiedzmy, teorii zbiorów ZFC lub czymkolwiek.

Przyszło mi do głowy, że może to dotyczyć funkcji Ackermanna, ale nie jestem pewien szczegółów. Nie wydaje się, że Wikipedia jasno opisuje ten aspekt.

computability reference-request turing-machines halting-problem vzn
źródło

3

Arytmetyka Peano wystarczy, aby udowodnić, że funkcja Ackermanna jest całkowita: oto ćwiczenie 17 wstępu Jaap van Oosten do notatek PA .

David Richerby

total computable fn defn wikipedia. zwróć uwagę, że to pytanie było częściowo motywowane spojrzeniem na collatz fn, gdzie jest to powiązane długo otwarte pytanie ...

dniu

2

To głupia uwaga, ale zauważ, że dla każdej maszyny Turinga M, która kończy się na wszystkich wejściach, teoria jest spójną teorią. Ale używając twierdzenia Gödla, możemy wykazać, że nie ma jednej teorii rekurencyjnej, która mogłaby udowodnić zakończenie wszystkich takich maszyn.

P A + " M terminates on all input"

$\mathrm{PA}+\mbox{"$M$ terminates on all input"}$

cody

12

Tak. Maszyna Turinga, która oblicza sekwencję Goodsteina, zaczynając od jej wejścia i kończąc, gdy sekwencja osiągnie zero. Zawsze kończy się, ale nie można tego udowodnić w arytmetyki Peano. Jestem pewien, że istnieją równoważne rzeczy dla ZFC lub innego systemu, który możesz wybrać.

Edycja Dla ZF, Hartmanis i Hopcroft pokazują, że istnieje maszyna Turinga która odrzuca każde wejście, ale nie można tego udowodnić w ZF. Nie jestem pewien, czy ZF może udowodnić, że zawsze zatrzymuje się, ale z pewnością nie może udowodnić, że maszyna "Jeśli akceptuje to zapętla się na zawsze, w przeciwnym razie zatrzymanie" zawsze zatrzymuje się, nawet jeśli tak jest. To wciąż pozostawia ZFC otwarte, ale ZF jest silniejszy niż PA. $M$ $M$ $M'(x)$ $=$ $M$ $x$

Patrz ust. 3 ankiety Scotta Aaronsona na temat niezależności P = NP dla prezentacji wyników Hartmanisa – Hopcrofta i cytatów z ich oryginalnych prac.

David Richerby
źródło

O dodaniu aksjomatu wyboru: ZFC nie może zrobić nic lepszego niż ZF dla „prostych” instrukcji, takich jak problem z zatrzymaniem (w tym przypadku

jeśli się nie mylę). Wynika to z tego, że ZF i ZFC dowodzą dokładnie takich samych instrukcji

.

Π_{2}^{0}

$\Pi^0_2$

Π_{2}^{0}

$\Pi^0_2$

cody

6

Weźmy teorię która jest co najmniej tak silna jak „podstawowa” arytmetyka i która jest rekurencyjnie policzalna (możliwe jest wyliczenie każdego twierdzenia o ). ${\cal T}$ ${\cal T}$

Skonstruuj następującą maszynę , która zachowuje się jak na wejściu : $M$ $n$

If there is no proof of 0 = 1 in less than n steps in T, ACCEPT
Otherwise, LOOP.

Za pomocą drugiego twierdzenia o niekompletności dość łatwo jest wykazać, że nie może udowodnić, że kończy się na wszystkich danych wejściowych (i jest to zgodne). ${\cal T}$ $M$

To oczywiście działa dla , , , ... o ile są one spójne. ${\cal T}=\mathrm{ZFC}$ ${\cal T}=\mathrm{PA}$ ${\cal T}=\mathrm{PA²}$

cody
źródło

5

$N$

Daniil
źródło

Czy istnieje baza TM, która zatrzymuje się na wszystkich danych wejściowych, ale tej właściwości nie da się udowodnić?

Odpowiedzi: