Apakah ada model perhitungan Turing-complete yang masalah penghentiannya tidak dapat diputuskan?

26

Saya tidak bisa memikirkan model seperti itu, mungkin semacam kalkulus lambda yang diketik? beberapa otomat seluler dasar?

Ini hampir akan menyangkal "Prinsip Kesetaraan Komputasi" dari Wolfram:

Hampir semua proses yang tidak sederhana dapat dilihat sebagai perhitungan kecanggihan yang setara

automata-theory computability turing-machines lambda-calculus universal-computation Diego de Estrada
sumber

Jawaban:

18

Anda dapat dengan mudah membangun model buatan yang tidak lengkap tetapi masalah penghentiannya tidak dapat diputuskan. Misalnya, ambil semua TM yang tidak berhenti pada apa pun kecuali .0

Mengenai pernyataan:

Anda tidak dapat menyangkal pernyataan yang tidak cukup tepat. Hampir tidak ada kata-kata dalam pernyataan yang terdefinisi dengan baik (berikan definisi untuk mereka jika ini tidak terjadi).

Kaveh
sumber
mmm, katakanlah model Turing-complete iff dapat mensimulasikan UTM.
Diego de Estrada
1
Saya pikir prinsip kesetaraan Wolfram lebih dekat dengan fisika daripada logika. Ahli logika tampaknya suka menyerang karena berbagai alasan: tidak tepat, belum terbukti, kita dapat mengatur semuanya jadi salah, dll. Tetapi sebenarnya Wolfram menunjukkan, dengan caranya sendiri, pada fakta yang sangat menarik tentang perhitungan , karena muncul "di alam".
Andrej Bauer
1
Saya tidak tahu tentang memetik ceri, buku itu tampaknya cukup komprehensif bagi saya, terutama semua catatan itu. Apakah ada alasan apriori untuk tidak mengizinkan perubahan definisi standar? Anda mengukur dengan tolok ukur yang salah di sini. Wolfram tidak mengerjakan matematika, paling tidak dalam arti kata tradisional.
Andrej Bauer
4
@Andrej, masalah utama saya adalah pernyataan itu sangat samar sehingga saya tidak melihat bagaimana hal itu dapat membuat prediksi yang dapat diverifikasi / disangkal. Dan ya, jika seseorang mengubah definisi standar hanya untuk dapat menafsirkan apa yang tidak akan menjadi dukungan untuk klaim sebagai dukungan untuk klaim maka saya pikir itu bermasalah.
Kaveh
4
Pernyataan itu tidak jelas, tapi terus kenapa? Itu bukan logika atau matematika. Ini adalah pengamatan, didukung oleh buku tebal yang penuh dengan contoh, bahwa pada dasarnya "sistem komputasi" cenderung sederhana atau sangat rumit, dan "setara" satu sama lain. Daripada mengkritik Wolfram karena tidak berbicara istilah logika dan matematika, akan lebih produktif untuk melihat bahwa ia ada benarnya, dan kemudian merumuskan titik itu dalam formalisme apa pun yang diinginkan hati Anda. Tetapi tentu saja, jika hati Anda tidak menginginkan hal seperti itu, maka Anda tidak akan melakukannya.
Andrej Bauer
4

Saya cukup yakin argumen diagonalisasi berlaku untuk setiap model perhitungan yang:

  • dapat merepresentasikan dirinya sebagai string, dan
  • dapat mensimulasikan mesin lain, mengingat representasi di atas

Jika kita memiliki model yang melanggar salah satu kondisi di atas, kekuatan komputasinya akan sangat terbatas.

gabgoh
sumber
10
∀x.f(x)≠x
2

Saya tidak yakin tentang koneksi yang tepat, tetapi ini tampaknya terkait dengan teorema Friedberg-Muchnik (lihat di sini ): ada set ulang yang derajat Turingnya kurang dari masalah penghentian. Hasil ini menjawab pertanyaan Post yang berpengaruh dan mengarah pada pengenalan "metode prioritas" dalam perhitungan.

Super0
sumber
-2

Mungkin. Ada banyak masalah matematika yang mungkin termasuk beberapa di antaranya, yang tidak dapat diputuskan, yaitu jawabannya adalah "ya" tetapi tidak ada bukti yang ada. Misalnya masalah Collatz 3x +1 muncul dalam pikiran sebagai kandidat. Atau pertanyaan apakah pi berisi string panjang sembarang angka 9s berturut-turut. Masalah seperti itu dapat dianggap sebagai "model perhitungan" yang mungkin jauh lebih kuat daripada UTM, tetapi masih belum dapat dipastikan apakah itu "berhenti" atau apakah "selalu berhenti".

Warren D. Smith
sumber
Saya tidak berpikir pendekatan ini bisa berhasil. Lihat: untuk pernyataan tetap semacam itu, ada algoritma yang memutuskan apakah itu "benar" atau "salah" dalam jumlah waktu yang terbatas, bahkan ketika itu tidak dapat ditentukan dalam ZFC (ref: en.wikipedia.org/wiki/Busy_beaver #Aplikasi ). Di sisi lain, jika Anda menganggap sebagai model perhitungan masalah "diberikan pernyataan, putuskan apakah ia memiliki bukti di ZFC", saya pikir model itu Turing-complete.
Diego de Estrada