Przypuszczenia matematyczne równoważne zatrzymaniu maszyny Turinga

To pytanie dotyczy tego, czy każde twierdzenie matematyczne można sprowadzić do pytania, czy zatrzyma się pojedyncza maszyna Turinga. W szczególności interesują mnie przypuszczenia, które są obecnie niesprawdzone.

Na przykład: Wikipedia mówi , że obecnie nie wiadomo, czy są jakieś nieparzyste liczby idealne. Ponieważ można rozstrzygnąć, czy dana liczba jest idealna, można napisać maszynę Turinga, która po kolei sprawdza każdą liczbę nieparzystą i zatrzymuje się, jeśli znajdzie idealną liczbę. (Ta maszyna Turinga nie przyjmuje żadnych danych.) Gdybyśmy wiedzieli, czy ta maszyna Turinga zatrzymuje się, wtedy wiedzielibyśmy, czy przypuszczenie jest prawdziwe i odwrotnie.

Jednak jako kolejny przykład, co z przypuszczeniem o bliźniaczych liczbach pierwszych ? Można rozstrzygnąć, czy dana liczba jest pierwszą liczbą pierwszą w parze bliźniaków, ale w tym przypadku nie możemy po prostu zatrzymać się, gdy znajdziemy pierwszą, ponieważ pytanie dotyczy tego, czy istnieje liczba nieskończona. Nie jest dla mnie jasne, czy można stworzyć maszynę Turinga, która zatrzyma się wtedy i tylko wtedy, gdy hipoteza podwójnych liczb pierwszych jest prawdziwa.

Z pewnością możemy stworzyć maszynę Turinga, która zatrzymuje się wtedy i tylko wtedy, gdy hipoteza podwójnych liczb pierwszych jest możliwa do udowodnienia w ramach arytmetyki Peano lub w innym systemie formalnym, ale to inne pytanie, ponieważ może być prawdziwe, ale nie do udowodnienia w wybranym systemie.

Więc moje pytania są

• Czy można stworzyć maszynę Turinga, która zatrzyma się wtedy i tylko wtedy, gdy hipoteza o dwóch liczbach pierwszych jest prawdziwa? (A jeśli tak, to w jaki sposób?)
• Czy ogólnie można stworzyć maszynę Turinga, która zatrzyma się wtedy i tylko wtedy, gdy pewne dane matematyczne są prawdziwe? Czy tę maszynę Turinga można skonstruować algorytmicznie na podstawie formalnego oświadczenia?
• Jeśli ogólnie nie jest to możliwe, czy istnieje jakiś sposób na sklasyfikowanie twierdzeń matematycznych pod kątem tego, czy są one równoważne z zatrzymaniem pojedynczej maszyny Turinga, czy maszyny Turinga z wyrocznią itp.? Jeśli tak, to czy ta klasyfikacja ma znaczenie dla danego stwierdzenia?

Na twoje pytanie odpowiada hierarchia arytmetyczna . Istnienie nieparzystej liczby doskonałej jest instrukcją , więc możesz ją przetestować za pomocą maszyny Σ 1 , która zatrzymuje, jeśli instrukcja jest prawdziwa. Hipoteza podwójnej liczby pierwszej jest wyrażeniem Π 2 , więc możesz zbudować bazę TM z dostępem do wyroczni zatrzymującej, która zatrzymuje się, jeśli instrukcja jest fałszywa.$\Sigma_1$$\Sigma_1$$\Pi_2$

W ścisłym logicznym sensie zawsze można stworzyć maszynę Turinga, która zatrzymuje instrukcję iff :$\phi$

1. Jeśli trzyma, weź maszynę, która się zatrzymuje.$\phi$
2. Jeśli się nie trzyma, weź maszynę, która się nie zatrzymuje.$\phi$

Aby sprawdzić, czy ta konstrukcja jest poprawna, rozważ logiczną formę swojego oświadczenia:

Możesz usunąć to zamieszanie, zadając nieco inne pytania:

Co to jest zestaw stwierdzeń , że istnieje maszyna Turinga, która zatrzymuje się na ϕ ∈ Φ iff ϕ, jest ważna?$\Phi$$\phi \in \Phi$$\phi$

Powyżej wskazałem, że oświadczenia tworzą taki zestaw.$\Sigma_1$

$f(1)=2$$f(2)=4$$f(n+1)=f(n)!$$n \geq 2$$n$$\Theta_n$

$x_1,\ldots,x_n$$1$$(x_1,\ldots,x_n)$$\min(x_1,\ldots,x_n) \leq f(n)$$\Theta_1,\ldots,\Theta_{16}$

$\Theta_{16}$$f(16)+3$$W \subseteq \mathbb{N}$$W$$W$$W$

$\Theta_{16}$$0'$