Apa set minimum instruksi mutlak yang diperlukan untuk membangun prosesor lengkap Turing

Saya memiliki ide umum tentang bagaimana prosesor menangani instruksi tetapi menghabiskan waktu saya bekerja di sebagian besar bahasa tingkat tinggi. Mungkin seseorang yang bekerja lebih dekat dengan setrika dapat memberikan wawasan yang berharga.

Dengan asumsi bahwa bahasa pemrograman pada dasarnya abstraksi tingkat yang sangat tinggi dari set instruksi prosesor, apa set instruksi paling dasar yang diperlukan untuk membuat mesin turing lengkap?

Catatan: Saya tidak tahu apa-apa tentang keragaman arsitektur perangkat keras tetapi - demi kesederhanaan - mari kita asumsikan itu adalah prosesor khas dengan ALU (jika perlu) dan tumpukan instruksi. *

Ternyata Anda hanya perlu satu instruksi untuk membangun mesin yang mampu melakukan komputasi Turing. Kelas mesin ini yang hanya memiliki satu instruksi dan Turing-complete disebut One Instruction Set Computers atau juga agak bercanda Ultimate RISC .

Ada banyak cara untuk mengimplementasikan sesuatu yang bisa diterapkan oleh mesin turing.

Saat Anda melihat prosesor, salah satu yang paling berlaku mungkin adalah model mesin register . Yang paling sederhana dari ini (dalam hal simbol) adalah simbol mulit-tape dua ( markdan blank). Jika Anda menggunakan sesuatu yang tidak terlalu esoterik, maka inc(r), dec(r)dan jz(r,z)(lompat jika register rnol untuk instruksi z) atau clr(r)(bersih r) inc,, je(i,j,z)(lompat jika register i dan j sama dengan instruksi z).

Saya telah melihat penyebutan mesin register yaitu:

• inc (i, m) - register kenaikan i dan pergi ke baris m
• jzdec (i, m1, m2) - jika register i adalah 0 pergi ke baris m, kalau tidak decrement saya, dan pergi ke baris m2

yang turing lengkap juga - ini adalah mesin register Minsky meskipun memiliki kendala lain pada data dalam rekaman (itu harus nomor Gödel menyimpan negara daripada register individu)

Itu dia. Tidak ada lagi.

Jadi, mengapa prosesor ultra risc ini tidak digunakan? Sungguh menyakitkan untuk menulis kompiler untuk mereka dan Anda menyerahkan banyak hal lain yang dapat dilakukan prosesor. Ini benar-benar baik untuk memiliki bitwise and, dan adddaripada mencoba melakukan semuanya dengan register dan perulangan yang meningkat. Itulah dasar bahasa pemrograman favorit berjudul Brainfuck yang memiliki 8 instruksi.

• > menambah penunjuk data
• < mengurangi pointer data
• + increment data di penunjuk data
• - mengurangi data pada penunjuk data
• . mengeluarkan data pada penunjuk data
• , baca input, simpan data di pointer data
• [jika data pada pointer adalah nol, bukannya bergerak penunjuk instruksi maju satu, melompat ke depan untuk perintah setelah pencocokan ]perintah
• ]jika data pada pointer adalah nol, bukannya bergerak instruksi pointer ke depan, melompat kembali ke perintah setelah pencocokan ]perintah

Seseorang dapat menemukan kompiler untuk Brainfuck, meskipun itu benar-benar tidak menyenangkan untuk melakukan bahkan hal-hal sederhana di dalamnya. Kecuali Anda menikmati frustrasi, yang merupakan tujuan dari bahasa tersebut.

Bacaan terkait:

• (Esolang) Turing tarpit
• Apa yang membuat bahasa Turing-lengkap? (untuk bahasa pemrograman)
• Mengapa FRACTRAN turing lengkap? (pada mesin register berbasis nomor Gödel)

Saya menduga bahwa mesin Post adalah tentang bentuk paling sederhana dari perangkat Turing-complete. Anda memerlukan persediaan memori bit-addressable, register alamat yang menunjuk ke lokasi data saat ini, dan lima instruksi:

• Atur bit di lokasi saat ini;
• Setel ulang bit di lokasi saat ini;
• Pindah ke alamat berikutnya (daftar alamat data increment);
• Pindah ke alamat sebelumnya (register alamat data penurunan);
• Periksa bit di lokasi data saat ini.

Saya tidak berpikir itu mudah untuk menemukan sesuatu yang jauh lebih sederhana dari segi perangkat keras, meskipun sesuatu yang bahkan lebih berkurang mungkin ada.

Implementasi

Jawaban ini akan fokus pada implementasi yang menarik dari set instruksi tunggal CPU, kompiler dan assembler.

penggerak

https://github.com/xoreaxeaxeax/movfuscator

Mengkompilasi kode C hanya menggunakan movinstruksi x86, menunjukkan dengan cara yang sangat konkret bahwa satu instruksi saja sudah mencukupi.

Kelengkapan Turing tampaknya telah terbukti dalam sebuah makalah: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

subleq

https://esolangs.org/wiki/Subleq :

• https://github.com/hasithvm/subleq-verilog Verilog, Xilinx ISE.
• https://github.com/purisc-group/purisc Verilog dan VHDL, Altera.
• http://mazonka.com/subleq/sqasm.cpp | http://mazonka.com/subleq/sqrun.cpp C ++ assembler dan emulator.

Lihat juga

/programming/3711443/minimal-instruction-set-to-solve-any-problem-with-a-computer-program/38523869#38523869

Apa set minimum instruksi mutlak yang diperlukan untuk membangun prosesor lengkap Turing?

Jörg W Mittag berkata, "satu," tetapi bagaimana dengan nol?

Mengapa Anda menganggap bahwa "prosesor" harus memiliki "instruksi"?

Mesin Turing adalah prosesor Turing-lengkap, dan tidak beroperasi pada "instruksi" seperti itu. Ini memiliki aturan , tetapi aturan tersebut bukan instruksi yang diambil dari memori akses acak.

Ketika Alan Turing memikirkan mesin eponymous-nya, ia mencari model "komputasi" yang paling sederhana sehingga ia dapat menggunakan teknik matematika untuk menjawab pertanyaan, "Apa yang bisa dihitung?"

Anda akan sulit sekali mendesain mesin setara Turing yang lebih sederhana dari mesin Turing yang sebenarnya.

FWIW, jenis prosesor yang Anda pikirkan --- yang mengambil instruksi dari memori, menerjemahkannya, dan mengeksekusinya, dan yang beroperasi pada data yang disimpan dalam sistem memori yang sama --- dikenal sebagai Arsitektur Von Neumann

https://en.wikipedia.org/wiki/Von_Neumann_architecture