Mesin Turing yang pemutusannya tidak dapat dibuktikan?

Saya punya pertanyaan naif: apakah ada mesin Turing yang pemutusannya benar tetapi tidak dapat dibuktikan oleh teori yang alami, konsisten, dan tidak aksiomatis? Saya meminta bukti keberadaan belaka daripada contoh khusus.

Ini mungkin memiliki beberapa hubungan dengan analisis ordinal . Memang, untuk mesin Turing , kita dapat mendefinisikan sebagai teori paling tidak konsisten dari teori yang membuktikan pemutusannya (atau yang paling tidak dari tata cara ini). Jadi saya kira itu sama dengan bertanya apakah ada sedemikian sehingga ? $M$ $O(M)$ $M$ $O(M) \geq \omega_1^{CK}$

turing-machines proof-theory halting-problem Super8
sumber

Tidakkah kuantifikasi bekerja sebaliknya? Cukup menambahkan penghentian TM X sebagai aksioma akan konsisten untuk X yang benar-benar berhenti pada semua input (dan terbatas jika Anda melakukannya hanya untuk TM yang dipermasalahkan). Dengan bilangan terbalik, bagaimana dengan TM yang berhenti jika input bukan bukti konsistensi untuk sistem aksiomatik dan memasuki loop tak terbatas sebaliknya.

Yonatan N

Saran Anda menarik, terima kasih. Saya menyadari kekhawatiran Anda ketika merumuskan pertanyaan, itu sebabnya saya menambahkan "alami" dalam persyaratan. Tentu saja, masalahnya adalah apakah kita dapat memberikan definisi formal tentang "kealamian" yang akan mengesampingkan konstruksi buatan ini.

Super8

berpikir jawabannya adalah tidak karena jika berhenti, maka orang hanya menjalankan mesin dan itu akan berhenti dalam sejumlah langkah terbatas, dan itu adalah bukti, dan fakta itu dapat dikonversi ke sistem bukti yang cukup kuat. di sisi lain berpikir mungkin untuk menyandikan / mengubah / menerjemahkan godel yang tidak dapat dibuktikan menjadi mesin non-stop yang mana non-halting tidak dapat dibuktikan. pertanyaan ini serupa, apakah ada TM yang berhenti pada semua input tetapi properti tidak dapat dibuktikan cs.se

vzn

Anda dapat membuat Turing mesin

yang menghitung urutan Goodstein ini

dari input

dan pemberhentian saat mencapai

.suatu penghentian

tidak dapat dibuktikan di Peano aritmatika; yaitu Teorema Goodstein tidak dapat dibuktikan menggunakan aksioma aritmetika Peano. Lihat Laurie Kirby, Jeff Paris, Hasil independensi yang dapat diakses untuk aritmatika Peano (1982)

M

$M$

G (n)

$G(n)$

n

$n$

0

$0$

M

$M$

Marzio De Biasi

Terima kasih, saya tidak tahu entri itu. Yang saya minta adalah kuat meskipun, saya ingin wrt ketidakterbuktian untuk setiap teori yang masuk akal (bukan teori tertentu seperti PA). Saya tidak yakin apakah pertanyaannya memiliki jawaban yang pasti.

Super8

Jawaban:

Pemutusan mesin Turing (pada masukan tetap) adalah kalimat dan semua teori aritmatika biasa orde pertama yang lengkap untuk kalimat, yaitu semua benar pernyataan yang dapat dibuktikan dalam teori ini. $\Sigma^0_1$ $\Sigma^0_1$ $\Sigma^0_1$

Jika Anda melihat totalitas sebagai pengganti berhenti , yaitu TM berhenti pada semua input, maka itu adalah -complete kalimat dan untuk setiap teori konsisten yang dapat dihitung secara aksioma yang cukup kuat (misalnya memperpanjang mengatakan teori Robinson ) ada TM yang totalitasnya tidak dapat dibuktikan dalam teori itu. $\Pi^0_2$ $Q$

Kaveh
sumber

Ya, saya mencari totalitas, karena tentu saja masalahnya sepele untuk input tetap. Saya akan memikirkan klaim Anda dan bagaimana membuktikannya, tetapi pada titik ini saya tidak melihat bagaimana mempertimbangkan teori "yang dapat dihindarkan dapat diterima" mengesampingkan masalah yang disebutkan di atas? Juga, dalam pernyataan Anda, TM tergantung pada teori yang dipertimbangkan, dapatkah kita mendapatkan pernyataan kuat saya dengan semacam diagonalisasi?

Super8

Berikut ini cara yang mudah: himpunan fungsi yang dapat dihitung total yang dapat dibuktikan dari teori semacam itu adalah ce, himpunan fungsi total yang dapat dihitung bukanlah ce, atau sebagai alternatif Anda dapat mendiagonalisasi terhadap fungsi total yang dapat dibuktikan dari teori.

Kaveh

Setelah dipikir-pikir, saya sarankan mempertimbangkan pembatasan masalah sebagai berikut. Diberikan sistem notasi ordinal

mewakili

ordinal , kita dapat mendefinisikan "teori dasar" yang sesuai

yang memungkinkan induksi transfinite hingga

. Diberikan TM

, kita kemudian akan mendefinisikan

sebagai

ordinal terkecil sehingga terminasi

dapat dibuktikan oleh teori

σ

$\sigma$

α

$\alpha$

T (α, σ)

$\mathcal{T}(\alpha,\sigma)$

α

$\alpha$

M

$M$

O (M)

$O(M)$

α

$\alpha$

M

$M$

T (α, σ)

$\mathcal{T}(\alpha,\sigma)$ (Yaitu sistem notasi dapat dipilih secara bebas). Apakah definisi ini masuk akal?

Super8

@ Super8, saya tidak yakin. Secara umum asosiasi ordinal dengan teori tidak kanonik, ada berbagai cara untuk mengasosiasikannya. Anda dapat mulai dengan teori yang lemah seperti PRA dan menambahkan induksi lebih dari ordinan yang dapat dihitung dengan urutan fundamental yang bagus, dll. Tetapi saya tidak yakin mengapa Anda ingin melakukannya.

Kaveh

Ok, saya belum menyadari masalahnya, saya akan mencoba mencari definisi yang lebih baik pada saya sendiri.

Super8

Saya bukan ahli logika, tapi saya yakin jawabannya tidak . Jika mesin Turing berhenti, dan sistemnya cukup kuat, Anda harus bisa menuliskan sejarah perhitungan lengkap mesin Turing pada inputnya. Ketika seseorang memverifikasi bahwa hasil perhitungannya adalah urutan pengakhiran transisi, orang dapat melihat bahwa mesin berhenti. Terlepas dari bagaimana Anda meresmikan mesin Turing dalam teori Anda, Anda harus dapat menunjukkan dalam teori yang masuk akal bahwa mesin yang berhenti sebenarnya berhenti. Dengan analogi, pikirkan untuk mencoba membuktikan bahwa jumlah yang terbatas sama dengan apa yang sama dengan itu; misalnya, buktikan bahwa 5 + 2 + 3 + 19 + 7 + 6 = 42, atau 5 + 5 + 5 = 15. Sama seperti ini selalu mungkin selama jumlah langkah terbatas, demikian juga membuktikan hasil perhitungan yang terbatas.

Sama seperti poin jelas tambahan - bahkan jika teori Anda tidak konsisten, Anda masih dapat menunjukkan bahwa mesin berhenti, sebenarnya bahkan jika tidak, karena Anda dapat membuktikan wff dalam teori yang tidak konsisten, terlepas dari apakah itu sebenarnya benar.

Philip White
sumber

Saya setuju dengan poin pertama Anda, lihat jawaban saya di bawah ini. Mengenai poin kedua Anda, teori yang tidak konsisten juga akan membuktikan penghentian TM (sebenarnya tidak menentu), di mana pembatasan untuk teori yang konsisten.

Super8

Saya pikir kita mengatakan hal yang sama; Saya hanya memperhatikan bahwa Anda mengatakan "konsisten" dalam pertanyaan, maaf karena melewatkannya. Saya pikir jawaban Kaveh mencakup semua hal yang sama dan ditulis dengan lebih elegan.

Philip White