Apa yang membuat bahasa Turing-lengkap?

Apa set fitur / struktur bahasa minimal yang membuatnya Turing-complete?

Sebuah Tarpit Turing adalah jenis bahasa pemrograman esoterik yang berusaha untuk Turing-lengkap saat menggunakan sebagai beberapa elemen mungkin. Brainfuck mungkin adalah tarpit paling terkenal, tetapi ada banyak.

• Iota dan Jot adalah bahasa fungsional dengan dua dan tiga simbol, masing-masing, berdasarkan kalkulus kombinator SK (I) .

• OISC ( One Instruction Set Computer ) menunjukkan jenis perhitungan imperatif yang hanya membutuhkan satu instruksi dari satu atau lebih argumen, biasanya "kurangi dan bercabang jika kurang dari atau sama dengan nol", atau "membalikkan kurangi dan lewati jika meminjam". MMU x86 mengimplementasikan instruksi sebelumnya dan karenanya Turing-complete.

Secara umum, agar bahasa imperatif lengkap dengan Turing, perlu:

1. Suatu bentuk pengulangan bersyarat atau lompatan bersyarat (misalnya while,, if+ goto)

2. Cara membaca dan menulis beberapa bentuk penyimpanan (misalnya, variabel, tape)

Agar bahasa fungsional berbasis kalkulus lambda menjadi TC, perlu:

1. Kemampuan untuk mengabstraksi fungsi atas argumen (mis. Abstraksi lambda, kutipan)

2. Kemampuan untuk menerapkan fungsi ke argumen (misalnya, reduksi)

Tentu saja ada cara lain untuk melihat perhitungan, tetapi ini adalah model umum untuk Turing tarpits. Perhatikan bahwa komputer sungguhan bukanlah mesin Turing universal karena tidak memiliki penyimpanan tanpa batas. Sebenarnya, mereka adalah "mesin penyimpanan terikat". Jika Anda terus menambahkan memori pada mereka, mereka akan secara asimptotik mendekati mesin Turing yang berkuasa. Namun, bahkan mesin penyimpanan terbatas dan mesin keadaan terbatas berguna untuk perhitungan; mereka tidak universal .

Sebenarnya, I / O tidak diperlukan untuk kelengkapan Turing; TC hanya menyatakan bahwa suatu bahasa dapat menghitung fungsi yang Anda inginkan, bukan bahasa yang dapat menunjukkan hasilnya kepada Anda. Dalam praktiknya, setiap bahasa yang bermanfaat memiliki cara berinteraksi dengan dunia.

Dari sudut pandang yang lebih praktis: jika Anda dapat menerjemahkan semua program dalam bahasa Turing-lengkap ke dalam bahasa Anda, maka (sejauh yang saya tahu), bahasa Anda harus Turing-lengkap. Oleh karena itu, jika Anda ingin memeriksa apakah bahasa yang Anda rancang adalah Turing-complete, Anda bisa menulis Brainf *** ke kompiler Bahasa Anda dan membuktikan / menunjukkan bahwa ia dapat mengkompilasi semua program BF legal.

Untuk memperjelas, maksud saya bahwa selain penerjemah untuk Bahasa Anda, Anda menulis kompiler (dalam bahasa apa pun) yang dapat mengkompilasi program BF apa pun ke Bahasa Anda (tentu saja, menjaga semantik yang sama, menjaga).

Suatu sistem hanya dapat dianggap sebagai Turing lengkap jika dapat melakukan apa pun yang dapat dilakukan mesin Turing universal. Karena mesin Turing universal dikatakan mampu menyelesaikan fungsi yang dapat dihitung dengan diberikan waktu, sistem Turing yang lengkap dapat, dengan ekstensi, juga melakukannya.

Untuk memeriksa apakah ada sesuatu yang Turing lengkap, lihat apakah Anda dapat menerapkan mesin Turing di dalamnya. Dengan kata lain, periksa untuk melihat apakah itu dapat mensimulasikan hal berikut:

1. Kemampuan membaca dan menulis "variabel" (atau data yang berubah-ubah) : Cukup jelas.
2. Kemampuan untuk mensimulasikan memindahkan kepala baca / tulis : Tidak cukup hanya dapat mengambil dan menyimpan variabel. Harus juga dimungkinkan untuk mensimulasikan kemampuan untuk menggerakkan kepala pita untuk referensi variabel lain. Ini sering dapat disimulasikan dalam bahasa pemrograman dengan penggunaan struktur data array (atau setara) atau, dalam kasus bahasa tertentu seperti kode mesin, kemampuan untuk referensi variabel lain melalui penggunaan "pointer" (atau setara).
3. Kemampuan untuk mensimulasikan mesin keadaan terbatas : Meskipun tidak sering disebutkan, mesin Turing sebenarnya merupakan variasi dari mesin keadaan terbatas yang sering digunakan dalam pengembangan AI. Alan Turing mengatakan tujuan negara adalah untuk mensimulasikan "berbagai mode penyelesaian masalah" seseorang.
4. Status "berhenti" : Meskipun sering disebutkan serangkaian aturan harus dapat mengulangi dirinya sendiri agar dapat dihitung sebagai Turing yang lengkap, itu sebenarnya bukan kriteria yang baik karena definisi formal tentang apa yang algoritma adalah algoritma negara harus selalu akhirnya menyimpulkan. Jika mereka tidak dapat menyimpulkan dalam beberapa cara, apakah itu Turing tidak lengkap, atau mengatakan algoritma itu bukan fungsi yang dapat dihitung. Turing sistem lengkap yang secara teknis tidak dapat menyimpulkan karena cara kerjanya (seperti konsol game, misalnya) mengatasi batasan ini dengan mampu "mensimulasikan" keadaan terputus-putus dalam beberapa cara. Jangan bingung dengan "masalah terputus-putus", fungsi yang tidak dapat dipastikan yang membuktikannya '

Ini adalah persyaratan minimum yang sebenarnya untuk suatu sistem untuk dianggap sebagai Turing yang lengkap. Tidak lebih, tidak kurang. Jika tidak dapat mensimulasikan semua ini dalam beberapa cara, itu tidak Turing lengkap. Metode yang diusulkan orang lain hanyalah sarana sampai akhir karena ada beberapa sistem lengkap Turing yang tidak memiliki fitur tersebut.

Perhatikan bahwa tidak ada cara yang diketahui untuk benar-benar membangun sistem lengkap Turing yang sebenarnya. Ini karena tidak ada cara yang diketahui untuk benar-benar mensimulasikan ketakbatasan rekaman mesin Turing dalam ruang fisik.

Bahasa pemrograman sudah selesai jika Anda dapat melakukan perhitungan apa pun dengannya. Tidak hanya ada satu set fitur yang membuat bahasa turing lengkap sehingga jawaban yang mengatakan Anda perlu loop atau bahwa Anda perlu variabel salah karena ada bahasa yang tidak memiliki tetapi turing lengkap.

Alan Turing membuat mesin turing universal dan jika Anda dapat menerjemahkan program apa pun yang dirancang untuk bekerja pada mesin universal untuk dijalankan pada bahasa Anda, Turing juga lengkap. Ini juga bekerja secara tidak langsung sehingga Anda dapat mengatakan bahasa X sedang menyelesaikan lengkap jika semua program untuk bahasa lengkap Y dapat diterjemahkan untuk X karena semua program mesin universal turing dapat diterjemahkan ke program Y.

Kompleksitas waktu, kompleksitas ruang, format input / output mudah dan penulisan program apa pun tidak termasuk dalam persamaan sehingga mesin tersebut secara teoritis dapat melakukan semua perhitungan jika perhitungan tidak dihentikan oleh kehilangan daya atau Bumi ditelan oleh matahari.

Biasanya untuk membuktikan kelengkapan, mereka membuat penerjemah untuk bahasa apa pun yang terbukti menjadi bahasa yang lengkap, tetapi agar bisa berfungsi, Anda memerlukan sarana input dan output, dua hal yang benar-benar tidak diperlukan untuk sebuah bahasa agar turing lengkap. Sudah cukup bahwa program Anda dapat mengubah keadaan saat startup dan Anda dapat memeriksa memori setelah program dihentikan.

Untuk membuat bahasa yang sukses dibutuhkan lebih dari turing kelengkapan dan ini berlaku bahkan untuk tarpit turing. Saya tidak berpikir BrainFuck akan populer tanpa ,dan ..

Anda tidak dapat mengetahui apakah itu akan berulang tanpa henti atau berhenti.

-------------

Penjelasan: Diberikan beberapa input, tidak mungkin untuk mengatakan dalam setiap kasus (menggunakan mesin Turing lain) jika benda itu akan berulang tanpa henti atau akhirnya akan berhenti, kecuali dengan menjalankannya (yang memberi Anda jawaban jika berhenti, tetapi tidak jika itu loop!).

Ini berarti bahwa Anda harus dapat menyimpan data dalam jumlah yang berpotensi tidak terbatas dengan cara tertentu - harus ada yang setara dengan rekaman tak terbatas, tidak peduli seberapa berbelit-belit! (Kalau tidak, hanya ada sejumlah negara terbatas dan kemudian Anda dapat memeriksa apakah Anda telah melalui negara itu sebelumnya dan akhirnya berhenti). Secara umum, mesin Turing dapat menumbuhkan atau mengecilkan ukuran negara mereka dengan beberapa cara yang terkendali.

Karena mesin Turing universal asli Turing memiliki masalah penghentian yang tidak dapat diselesaikan, mesin lengkap Turing Anda juga harus memiliki masalah penghentian yang tidak dapat diselesaikan.

Sistem Turing lengkap dapat meniru sistem Turing lengkap lainnya, jadi jika Anda dapat membangun emulator untuk beberapa sistem Turing lengkap yang terkenal di sistem Anda, itu membuktikan bahwa sistem Anda juga Turing lengkap.

Sebagai contoh, misalkan Anda ingin membuktikan bahwa Snakes & Ladders adalah Turing lengkap, diberi papan dengan pola kotak berulang berulang (dengan versi yang berbeda di sisi atas dan kiri). Mengetahui bahwa mesin Minsky 2-counter lengkap Turing (yang memiliki 2 penghitung tidak terbatas dan 1 status dari jumlah terbatas), Anda dapat membuat papan setara di mana posisi X dan Y pada grid adalah nilai saat ini dari 2 penghitung dan jalur saat ini adalah keadaan saat ini. Bang! Anda baru saja membuktikan bahwa Ular & Tangga Turing lengkap.

Satu kondisi yang diperlukan adalah loop dengan jumlah iterasi maksimum yang tidak ditentukan sebelum iterasi, atau rekursi di mana kedalaman rekursi maksimum tidak ditentukan sebelumnya. Sebagai contoh, untuk ... dalam ... loop karena Anda menemukannya dalam banyak bahasa yang lebih baru tidak cukup untuk membuat bahasa turing lengkap (tetapi mereka akan memiliki cara lain). Perhatikan bahwa ini tidak berarti jumlah iterasi atau kedalaman rekursi yang terbatas, tetapi iterasi maksimum dan kedalaman rekursi harus dihitung sebelumnya.

Misalnya, fungsi Ackermann tidak dapat dihitung dalam bahasa tanpa fitur-fitur ini. Di sisi lain, banyak perangkat lunak yang sangat kompleks dan sangat berguna dapat ditulis tanpa memerlukan fitur-fitur ini.

Di sisi lain, dengan setiap iterasi dihitung dan setiap kedalaman rekursi dihitung di depan, tidak hanya itu dapat diputuskan apakah suatu program akan dihentikan atau tidak, tetapi akan dihentikan.

saya tahu ini bukan jawaban yang benar secara formal, tetapi setelah Anda mengambil 'minimal' dari 'Turing-complete' dan meletakkan 'praktis' kembali ke tempatnya, Anda akan melihat fitur paling penting yang membedakan bahasa pemrograman dari bahasa markup adalah

• variabel
• kondisional (jika / kemudian ...)
• loopage (loop / break, while ...)

selanjutnya datang

• fungsi anonim dan bernama

untuk menguji pernyataan ini, mulailah dengan bahasa markup, katakanlah, HTML. kita bisa menciptakan HTML + dengan variabel saja, atau hanya kondisional (MS melakukannya dengan komentar kondisional), atau semacam konstruksi lingkaran (yang jika tidak ada kondisional mungkin akan berakhir seperti sesuatu seperti <repeat n='4'>...</repeat>). melakukan salah satu dari ini akan membuat HTML + secara signifikan (?) lebih kuat daripada HTML biasa, tetapi itu masih lebih berupa markup daripada bahasa pemrograman; dengan setiap fitur baru, Anda membuatnya lebih sedikit sebagai bahasa deklaratif dan lebih penting.

pencarian minimal dalam logika dan pemrograman sungguh penting dan menarik, tetapi jika saya harus mengajar n00bies muda atau tua 'apa itu pemrograman' dan 'cara belajar pemrograman', saya tidak akan memulai dengan luas dan lebar penuh dari landasan teoritis kelengkapan Turing. seluruh inti dari memasak dan pemrograman adalah melakukan hal-hal, dalam urutan yang benar, berulang sampai siap, seperti yang dilakukan ibu Anda. itu tentang jumlah itu bagi saya.

sekali lagi, saya tidak pernah menyelesaikan CS saya.