Apakah ada TM yang menghentikan semua input tetapi properti itu tidak dapat dibuktikan?

17

Apakah ada mesin Turing yang menghentikan semua input tetapi properti itu tidak dapat dibuktikan karena alasan tertentu?

Saya bertanya-tanya apakah pertanyaan ini telah dipelajari. Catatan, "tidak dapat dibuktikan" dapat berarti sistem bukti "terbatas" (yang dalam arti lemah berpikir jawabannya pasti ya). Saya tentu saja tertarik pada jawaban terkuat yang mungkin, yaitu salah satu yang tidak terbukti berhenti pada semua input di katakan teori set ZFC atau apa pun.

Terpikir oleh saya ini bisa jadi benar dari fungsi Ackermann tetapi saya tidak jelas pada detailnya. Sepertinya Wikipedia tidak menggambarkan aspek ini dengan jelas.

3

Aritmatika Peano cukup untuk membuktikan bahwa fungsi Ackermann adalah total: ini adalah latihan 17 dari Pengantar Jaap van Oosten untuk catatan PA .

David Richerby

total computable fn defn wikipedia. perhatikan pertanyaan ini sebagian dimotivasi oleh melihat ke collatz fn di mana itu adalah pertanyaan terbuka panjang terkait ...

vzn

2

Ini adalah pernyataan yang konyol, tetapi perhatikan bahwa untuk setiap mesin Turing M yang berakhir pada semua input, teori

P A + " M terminates on all input"

$\mathrm{PA}+\mbox{"$M$ terminates on all input"}$ adalah teori yang konsisten. Tetapi menggunakan teorema Gödels kita dapat menunjukkan bahwa tidak ada teori rekursif tunggal yang dapat membuktikan penghentian semua mesin tersebut.

cody

12

Iya. Mesin Turing yang menghitung urutan Goodstein dimulai dari inputnya dan berakhir ketika urutannya mencapai nol. Itu selalu berakhir tetapi ini tidak dapat dibuktikan dalam aritmetika Peano. Saya yakin ada hal-hal yang setara untuk ZFC atau sistem lain yang Anda pilih.

Edit Untuk ZF, Hartmanis dan Hopcroft menunjukkan bahwa ada mesin Turing yang menolak setiap input tetapi ini tidak dapat dibuktikan di ZF. Saya tidak yakin apakah ZF dapat membuktikan bahwa selalu berhenti tetapi tentu saja tidak dapat membuktikan bahwa mesin "Jika menerima maka lewati selamanya, yang lain berhenti" selalu berhenti, meskipun demikian. Itu masih membiarkan ZFC terbuka tetapi ZF lebih kuat dari PA. $M$ $M$ $M'(x)$ $=$ $M$ $x$

Lihat Sec. 3 dari survei Scott Aaronson tentang independensi P = NP untuk eksposisi hasil Hartmanis-Hopcroft dan kutipan ke makalah asli mereka.

David Richerby
sumber

Tentang menambahkan aksioma pilihan: ZFC tidak bisa lebih baik daripada ZF untuk pernyataan "sederhana" seperti masalah terputus-putus (dalam hal ini

jika saya tidak salah). Ini karena ZF dan ZFC membuktikan pernyataan yang persis sama

.

Π_{2}^{0}

$\Pi^0_2$

Π_{2}^{0}

$\Pi^0_2$

cody

6

Ambil teori yang setidaknya sekuat aritmatika "dasar", dan itu dihitung secara berulang (dimungkinkan untuk menyebutkan setiap teorema dari ${\cal T}$ ). ${\cal T}$

Buat mesin berikut , yang berperilaku sebagai berikut pada input $M$ $n$ :

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

Sangat mudah untuk menunjukkan menggunakan teorema ketidaklengkapan kedua bahwa tidak dapat membuktikannya ${\cal T}$ berakhir pada semua input (jika konsisten). $M$

Tentu saja ini bekerja untuk , , ${\cal T}=\mathrm{ZFC}$ ${\cal T}=\mathrm{PA}$ ${\cal T}=\mathrm{PA²}$ , ... selama mereka konsisten.

cody
sumber

5

Beberapa tidak dapat dibuktikan dalam PA tetapi teorema yang sebenarnya dapat dikonversi ke mesin Turing. Misalnya, ada (versi yang diperkuat) teorema Ramsey , yang tidak dapat dibuktikan dalam PA, dan kita dapat membangun mesin yang hanya akan mencari tepat . $N$

Daniil
sumber

Apakah ada TM yang menghentikan semua input tetapi properti itu tidak dapat dibuktikan?

Jawaban: