Jelas, lengkap, bukti bahwa suatu bahasa Turing Bersaing?

Saya telah melihat situs web yang mengaku "membuktikan" bahwa HTML5 + CSS Turing Lengkap.

Saya telah melihat situs web yang mengaku "membuktikan" bahwa SQL adalah Turing Lengkap.

Saya telah melihat banyak situs web yang dimaksudkan untuk "menjelaskan" apa artinya menjadi Lengkap Turing.

Cukup!

Di mana saya dapat menemukan buku (ditulis oleh pakar teori komputabilitas) atau artikel yang ditinjau oleh rekan sejawat (dalam jurnal yang memiliki reputasi baik) yang menunjukkan bukti, "Bahasa ini XYZ mampu menggambarkan mesin komputasi yang memiliki kekuatan komputasi yang sama. sebagai Mesin Turing "?

computability turing-machines automata turing-completeness church-turing-thesis Roger Costello
sumber

Tidak ada ahli yang akan menulis makalah seperti itu karena tidak ada gunanya.

Andrej Bauer

Tetapi ada kertas yang melakukan itu. Pertimbangkan sirkuit quasi-delay-insensitive adalah Turing-complete yang memiliki bukti oleh konstruksi.

Dan D.

Saya akan makan topi saya jika Anda dapat menemukan makalah peer-review yang memiliki bukti rinci bahwa HTML5 + CSS, atau SQL, atau PHP sudah lengkap.

Andrej Bauer

@ andrej coba yang ini. cukup dekat? XSLT Versi 2.0 adalah Turing-Lengkap: Bukti Berbasis Transformasi Murni . mungkin hanya makan sayuran Anda: p

vzn

lihat juga apa yang membuat bahasa turing lengkap , programmer.se

vzn

Jawaban:

Setiap bahasa yang dapat mengimplementasikan dua penghitung (yaitu dua register yang dapat menyimpan dua bilangan bulat besar sewenang-wenang) dan program yang dibuat dengan urutan berlabel dari dua instruksi dasar ini adalah Turing lengkap: $C_1, C_2$

TAMBAH untuk melawan , instruksi GOTO $1$ $C_i$ $I_j$
SUBTRACT dari counter jika dan instruksi GOTO ; jika tidak (jika ) Instruksi GOTO $1$ $C_i$ $C_i > 0$ $I_j$ $C_i = 0$ $I_k$

Hasilnya terbukti dalam:

Marvin L. Minsky, "Unsurvabilitas Rekursif atas Masalah Tag dan Topik-Topik Lain dalam Teori Mesin Turing" (1961)

Jangan lupa bahwa model komputasi (dalam kasus Anda bahasa pemrograman + perangkat yang menjalankan program yang ditulis dalam bahasa itu ) dapat dianggap Turing lengkap hanya jika mendukung akses ke jumlah memori yang tidak terbatas (yaitu ruang) atau dapat menyimpan ( dalam beberapa bentuk) bilangan bulat besar sewenang-wenang. Implementasi bahasa pemrograman pada komputer nyata setara dengan Linear Bounded Automaton .

Anda juga dapat menemukan banyak referensi di halaman Wikipedia tentang model RAM dan model RASP .

Akhirnya buku yang bagus berfokus pada kesetaraan model komputasi yang berbeda adalah:

"Model Komputasi: Pengantar Teori Komputasi", oleh Maribel Fernandez

Vor
sumber

"Jangan lupa bahwa bahasa pemrograman dapat dianggap Turing lengkap hanya jika mendukung akses ke memori tak terbatas" Karena itu tidak mungkin ada implementasi bahasa Turing Lengkap? Apakah ini kesimpulan Anda? Atau apakah Anda ingin mengatakan bahwa semua (sebagian besar) bahasa yang kami gunakan adalah Turing Lengkap karena persyaratan itu mudah dicapai? Kedua kesimpulan itu valid dari jawaban Anda, seperti yang ada sekarang.

Bakuriu

bakuriu lihat TM lengkap & daya komputasi

vzn

@ Bakuriu: memang kalimatnya agak ambigu; Maksud saya hanya bahwa model komputasi dapat dianggap Turing lengkap jika - dalam beberapa bentuk - memungkinkan untuk menggunakan penyimpanan tanpa batas. Kebanyakan bahasa pemrograman Turing lengkap karena dalam spesifikasi (sintaksisnya) mereka tidak memiliki batasan pada ukuran variabel atau pointer, tetapi implementasinya terbatas; lihat misalnya C's <Limit.h>. Jadi, bahkan jika Anda memiliki komputer dengan memori tidak terbatas yang menjalankan implementasi C, Anda tidak dapat menggunakan memori itu kecuali jika Anda menyediakan "mekanisme ekstra" yang bukan bagian dari bahasa.

Vor

Secara teknis, implementasi bahasa pemrograman pada komputer sungguhan bahkan bukan perwujudan automata terbatas linear yang sesungguhnya, karena mereka tidak dapat menerima CSL sewenang-wenang ... karena alasan yang sama komputer tidak setara dengan mesin Turing, yaitu, tidak cukup Penyimpanan. Berapa banyak memori yang dibutuhkan mesin untuk menerima bahasa yang peka konteks ? Saya kira Anda mungkin keberatan bahwa Anda akan dapat menyelesaikannya asalkan Anda memiliki cukup ruang untuk menuliskan pertanyaan, tetapi itu tidak mengubah fakta bahwa kami tidak dapat membuat model fisik yang setara dengan

{w . w ∣ w \in {0, 1}}

$\{w.w \mid w \in \{0, 1\}\}$

LBA

Dua buku teks yang paling banyak digunakan tentang teori komputasi dan kompleksitas adalah:

Michael Sipser: Pengantar Teori Komputasi , 2 / e, Cengage, 2005.

John E Hopcroft; Jeffrey D Ullman: Pengantar Teori Automata, Bahasa dan, Komputasi , Addison-Wesley, 1979.

Ada juga monografi filosofi yang indah untuk umat awam yang bekerja melalui rincian teknis teori komputabilitas tanpa bukti formal.

Douglas Hoftstadter: Gödel, Escher, Bach , Basic Books, 1979.

Akhirnya, pengantar terbaik untuk komputasi dapat berupa buku puzzle oleh ahli logika terkenal:

Raymond Smullyan: The Lady or the Tiger dan Other Logic Puzzles , Penguin, 1983. (Sekarang dalam edisi Dover yang murah, 2009.)

(Dia mulai dengan sekelompok teka-teki berdasarkan paradoks Liar, dan kemudian membuatmu melalui konstruksi pernyataan referensial diri dengan kedok teka-teki gaya Sherlock Holmes tentang kotak terkunci yang misterius.)

Logika Pengembaraan
sumber