Dugaan matematika setara dengan penghentian mesin Turing

11

Pertanyaan ini adalah tentang apakah setiap teorema matematika dapat direduksi menjadi pertanyaan apakah satu mesin Turing berhenti. Secara khusus, saya tertarik pada dugaan yang saat ini tidak terbukti.

Sebagai contoh: Wikipedia mengatakan bahwa saat ini tidak diketahui apakah ada angka sempurna yang aneh. Karena dapat diputuskan apakah angka yang diberikan itu sempurna, orang dapat menulis mesin Turing yang memeriksa setiap angka ganjil secara bergantian dan berhenti jika menemukan nomor yang sempurna. (Mesin Turing ini tidak menerima input apa pun.) Jika kita tahu apakah mesin Turing itu berhenti, maka kita akan tahu apakah dugaan itu benar, dan sebaliknya.

Namun, sebagai contoh lain, bagaimana dengan dugaan bilangan prima kembar ? Diputuskan apakah angka yang diberikan adalah prima pertama dalam pasangan kembar, tetapi dalam kasus ini kita tidak bisa berhenti begitu saja ketika kita menemukan yang pertama, karena pertanyaannya adalah apakah ada angka yang tak terbatas. Tidak jelas bagi saya apakah mungkin untuk membuat mesin Turing yang berhenti jika dan hanya jika dugaan bilangan kembar benar.

Kita pasti dapat membuat mesin Turing yang berhenti jika dan hanya jika dugaan prima kembar terbukti dalam aritmatika Peano atau sistem formal lainnya, tapi itu pertanyaan yang berbeda, karena mungkin benar tetapi tidak dapat dibuktikan dalam sistem tertentu yang kita pilih.

Jadi pertanyaan saya adalah

Apakah mungkin untuk membuat mesin Turing yang berhenti jika dan hanya jika dugaan kembar prima itu benar? (Dan jika demikian, bagaimana?)
Apakah mungkin, secara umum, membuat mesin Turing yang berhenti jika dan hanya jika beberapa pernyataan matematika yang diberikan benar? Dapatkah mesin Turing ini dibangun secara algoritmik dari pernyataan formal?
Jika itu tidak mungkin secara umum, apakah ada cara untuk mengklasifikasikan pernyataan matematika menjadi apakah mereka setara dengan penghentian satu mesin Turing, atau mesin turing dengan oracle , dll? Jika demikian, apakah klasifikasi ini dapat dipilih untuk pernyataan yang diberikan?

formal-languages computability mathematical-foundations Nathaniel
sumber

Apa artinya "benar"? Model seperti apa yang kita mengevaluasi kebenaran ini? Anda harus mendefinisikan itu dulu, saya pikir.

Jake

Saya pikir semua mesin Turing seperti itu hanya dapat menguji kemampuan. Bahkan jika Anda tidak secara eksplisit mengulangi pernyataan benar dalam PE, Anda masih mencari bukti dalam bentuk lain. Perbedaannya adalah bahwa keberadaan bilangan sempurna ganjil jelas tidak bisa benar dan tidak dapat dibuktikan, sementara bilangan prima kembar mungkin.

Karolis Juodelė

Dugaan tentang set yang tidak terhitung tidak dapat diekspresikan menggunakan mesin Turing.

Raphael

12

$\Sigma_1$ $\Sigma_1$ $\Pi_2$

$\phi$

$\phi$
$\phi$

Untuk melihat bahwa konstruksi ini valid, pertimbangkan bentuk logis dari pernyataan Anda:

\forall ϕ \exists T . ϕ \Leftrightarrow T halts .

$\forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}.$

$\Phi$ $\phi \in \Phi$ $\phi$

$\Sigma_1$

Yuval Filmus
sumber

Terima kasih, saya pikir hierarki aritmatika adalah apa yang saya minta. Saya pikir apa yang sebenarnya ingin saya tanyakan adalah "adakah fungsi total yang dapat dihitung dari (beberapa subset) pernyataan matematis ke mesin Turing yang tidak mengambil input, sehingga mesin yang sesuai dengan pernyataan yang diberikan berhenti jika pernyataan itu benar?" Tapi tentu saja itu setara dengan versi yang Anda usulkan.

Nathaniel

0

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

S \subseteq {x_{i}! = x_{k} : i, k \in {1, \dots, n}} \cup {x_{i} \cdot x_{j} = x_{k} : i, j, k \in {1, \dots, n}}

$S \subseteq \{x_i! = x_k: i,k \in \{1,\ldots,n\}\} \cup \{x_i \cdot x_j=x_k: i,j,k \in \{1,\ldots,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}$

Pernyataan membuktikan implikasinya: jika ada prime kembar lebih besar dari , maka ada banyak bilangan prima kembar, silakan lihat makalah ini oleh A. Tyszka ( Pada set sedemikian sehingga infinity setara dengan keberadaan di dari elemen yang lebih besar dari angka ambang batas yang dihitung dengan menggunakan definisi ) $\Theta_{16}$ $f(16)+3$ $W \subseteq \mathbb{N}$ $W$ $W$ $W$

Artinya, dengan asumsi pernyataan , permintaan tunggal ke memutuskan masalah utama kembar. $\Theta_{16}$ $0'$

Apoloniusz Tyszka
sumber

Dugaan matematika setara dengan penghentian mesin Turing

Jawaban: