Mathematische Vermutungen, die dem Anhalten einer Turingmaschine entsprechen

11

Bei dieser Frage geht es darum, ob jeder mathematische Satz auf die Frage reduziert werden kann, ob eine einzelne Turing-Maschine anhält. Insbesondere interessieren mich Vermutungen, die derzeit nicht bewiesen sind.

Zum Beispiel: Wikipedia sagt, dass es derzeit nicht bekannt ist, ob es ungerade perfekte Zahlen gibt. Da es entscheidend ist, ob eine bestimmte Zahl perfekt ist, könnte man eine Turing-Maschine schreiben, die jede ungerade Zahl nacheinander überprüft und anhält, wenn sie eine findet, die perfekt ist. (Diese Turing-Maschine nimmt keine Eingaben entgegen.) Wenn wir wüssten, ob diese Turing-Maschine anhält, würden wir wissen, ob die Vermutung wahr ist und umgekehrt.

Was ist jedoch als weiteres Beispiel mit der Vermutung der Zwillingsprimzahlen ? Es ist entscheidbar, ob eine bestimmte Zahl die erste Primzahl in einem Zwillingspaar ist, aber in diesem Fall können wir nicht einfach anhalten, wenn wir die erste finden, denn die Frage ist, ob es eine unendliche Zahl gibt. Mir ist nicht klar, ob es möglich ist, eine Turing-Maschine herzustellen, die genau dann anhält, wenn die Vermutung der Doppelprimzahlen wahr ist.

Wir können sicherlich eine Turing-Maschine herstellen, die genau dann anhält, wenn die Vermutung der Doppelprimzahlen innerhalb der Peano-Arithmetik oder eines anderen formalen Systems beweisbar ist, aber das ist eine andere Frage, da sie in dem von uns gewählten System möglicherweise wahr, aber nicht beweisbar ist.

Meine Fragen sind also

  • Ist es möglich, eine Turing-Maschine herzustellen, die genau dann anhält, wenn die Vermutung der Doppelprimzahlen wahr ist? (Und wenn ja, wie?)
  • Ist es im Allgemeinen möglich, eine Turing-Maschine herzustellen, die genau dann anhält, wenn eine bestimmte mathematische Aussage wahr ist? Kann diese Turing-Maschine algorithmisch aus der formalen Anweisung konstruiert werden?
  • Wenn dies im Allgemeinen nicht möglich ist, gibt es eine Möglichkeit, mathematische Aussagen dahingehend zu klassifizieren, ob sie dem Anhalten einer einzelnen Turingmaschine oder einer Turingmaschine mit einem Orakel usw. entsprechen? Wenn ja, ist diese Klassifizierung für eine bestimmte Aussage entscheidbar?
Nathaniel
quelle
Was bedeutet "wahr"? Auf welche Art von Modellen bewerten wir diese Wahrheit relativ? Sie müssen das zuerst definieren, denke ich.
Jake
Ich denke, alle diese Turing-Maschinen können nur die Beweisbarkeit testen. Auch wenn Sie in PE nicht explizit über wahre Aussagen iterieren, suchen Sie dennoch nach einem Beweis in einer anderen Form. Der Unterschied besteht darin, dass die Existenz einer ungeraden perfekten Zahl offensichtlich nicht sowohl wahr als auch unbeweisbar sein kann, während Zwillingsprimzahlen dies könnten.
Karolis Juodelė
Vermutungen über unzählige Mengen können mit Turing-Maschinen nicht geäußert werden.
Raphael

Antworten:

12

Ihre Frage wird durch die arithmetische Hierarchie beantwortet . Das Vorhandensein einer ungeraden perfekten Zahl ist eine Anweisung. Sie können sie daher mit einer Σ 1- Maschine testen , die angehalten wird, wenn die Anweisung wahr ist. Die Twin-Prime-Vermutung ist eine Π 2- Anweisung. Sie können also ein TM mit Zugriff auf das anhaltende Orakel erstellen, das anhält, wenn die Anweisung falsch ist.Σ1Σ1Π2

Im engeren logischen Sinne können Sie immer eine Turing-Maschine erstellen, die die iff-Anweisung anhält :ϕ

  1. Wenn gilt, nehmen Sie eine Maschine, die anhält.ϕ
  2. Wenn nicht hält, nehmen Sie eine Maschine, die nicht anhält.ϕ

Um zu sehen, dass diese Konstruktion gültig ist, betrachten Sie die logische Form Ihrer Aussage:

Sie können diese Verwirrung beseitigen, indem Sie etwas andere Fragen stellen:

ϕT.ϕT halts.

Was ist eine Reihe von Aussagen so , dass es eine Turing - Maschine gibt , die Aussetzer auf φ & egr ; & PHgr; iff φ gültig ist?ΦϕΦϕ

Oben habe ich angegeben, dass Anweisungen eine solche Menge bilden.Σ1

Yuval Filmus
quelle
Vielen Dank, ich denke, die arithmetische Hierarchie ist genau das, wonach ich gefragt habe. Ich denke, was ich eigentlich fragen wollte, war: "Gibt es eine vollständig berechenbare Funktion von (einigen Teilmengen von) mathematischen Anweisungen bis zu Turing-Maschinen, die keine Eingabe akzeptieren, so dass die Maschine, die einer bestimmten Anweisung entspricht, anhält, wenn die Aussage wahr ist?" Aber das entspricht natürlich der von Ihnen vorgeschlagenen Version.
Nathaniel
0

f(1)=2f(2)=4f(n+1)=f(n)!n2nΘn

S{xi!=xk:i,k{1,,n}}{xixj=xk:i,j,k{1,,n}}

x1,,xn1(x1,,xn)min(x1,,xn)f(n)Θ1,,Θ16

Θ16f(16)+3WNWWW

Θ160

Apoloniusz Tyszka
quelle