Perhatikan: Saya bersedia memberikan hadiah untuk setiap jawaban yang menurut saya menarik.
Tantangan Anda adalah merancang komputer set instruksi (TIS) yang lengkap-Turing :
OISC adalah mesin abstrak yang hanya menggunakan satu instruksi - menghindari kebutuhan untuk opcode bahasa mesin. Dengan pilihan yang bijaksana untuk instruksi tunggal dan sumber daya yang diberikan tak terbatas, OISC mampu menjadi komputer universal dengan cara yang sama seperti komputer tradisional yang memiliki banyak instruksi.
Berikut adalah beberapa contoh perintah tunggal yang membuat TIS-lengkap OISC.
Aturan:
Anda harus memberikan interpretasi atau bukti daripadanya
Anda harus menyediakan juru bahasa untuk bahasa Anda. Penerjemah ini hanya boleh dibatasi oleh memori / waktu (mis. Tidak boleh memiliki batasan yang dikenakan pengguna) Jika Anda tidak menyediakan juru bahasa untuk bahasa Anda (untuk alasan apa pun selain kemalasan), Anda harus membuktikan bahwa mungkin saja satu untuk ditulis. Seorang juru bahasa harus dimungkinkan .
Anda harus membuktikan kelengkapan Turing-nya
Anda harus menyertakan bukti resmi bahwa bahasa Anda Turing-lengkap. Cara sederhana untuk melakukan ini adalah dengan membuktikan bahwa itu dapat menafsirkan atau memiliki perilaku yang sama dengan bahasa Turing-lengkap lainnya. Bahasa yang paling dasar untuk ditafsirkan adalah Brainf ** k .
Misalnya, bahasa normal yang memiliki semua perintah yang sama dengan Brainf ** k (dan kurangnya batasan memori yang dipaksakan oleh pengguna) adalah Turing-complete karena apa pun yang dapat diimplementasikan dalam Brainf ** k dapat diimplementasikan dalam bahasa .
Berikut adalah daftar bahasa Turing-lengkap yang sangat mudah diimplementasikan.
Persyaratan OISC tambahan
OISC ini seharusnya hanya memiliki satu instruksi - itu tidak dapat memiliki banyak instruksi dengan salah satu dari mereka membuatnya Turing-lengkap.
OISC Anda dapat menggunakan sintaksis yang Anda suka. Anda harus menentukan dalam jawaban Anda apa itu instruksi, apa itu data, dan apa itu no-op (mis. Spasi kosong). Jadilah kreatif!
Argumen tidak hanya perlu bilangan bulat. Sebagai contoh, /// adalah contoh indah dari OISC Turing-complete.
Bagaimana dan jika input dan output diambil dan diberikan diserahkan kepada Anda. Sebagian besar OISC menerapkan I / O melalui lokasi memori tertentu, tetapi mungkin ada cara lain untuk melakukannya, dan Anda dianjurkan untuk menemukannya.
Jawaban yang valid harus memberikan beberapa kode contoh dalam OISC Anda, baik dengan memasukkannya dalam pos atau menghubungkan ke tantangan sederhana yang diselesaikan dalam bahasa.
Pemungutan suara
Pemilih, harap diingat untuk tidak membatalkan pengiriman yang membosankan. Contoh:
- Bahasa -setara
- Implementasi OISC yang ada (penjawab, silakan buat sendiri!)
- "OISC" di mana argumen pertama menentukan perintah untuk memanggil ( contoh )
Namun, Anda harus mengambil alih pengiriman yang menarik dan kreatif, seperti:
- OISC didasarkan pada persamaan matematika
- ZISC Turing-complete berdasarkan pada jaringan saraf
- OISC di mana output I / O terjadi dengan cara lain selain lokasi memori tertentu
Kemenangan
Seperti halnya kontes popularitas , jawaban dengan suara terbanyak menang! Semoga berhasil!
Jawaban:
XOISC
OISC ini didasarkan pada X-combinator Fokker yang didefinisikan sebagai berikut:
Jika kita mengakui fakta bahwa SKI-kalkulus adalah Turing lengkap, kobinator di atas juga Turing lengkap. Ini karena S , K dan saya dapat ditulis dalam bentuk X , seperti ini:X S K saya X
Cara kerja XOISC
Secara internal XOISC memiliki tumpukan (awalnya kosong), dari sana instruksi mengambil sebagai argumen melakukan hal berikut:n
Setelah tidak ada instruksi lagi yang tersisa XOISC akan mendorong semua argumen baris perintah (jika ada) ke stack, misalnya:
Perhitungan akhir akan .( ... ( ( ... ( s1 s2) ... ) s M.) a 1) ... ) aN
Karena satu instruksi dalam XOISC hanya membutuhkan satu argumen (memory offset), tidak ada alasan untuk menggunakan nama untuk instruksi tersebut. Jadi file sumber yang valid hanya akan terdiri dari bilangan bulat yang dipisahkan oleh baris baru atau spasi putih, seperti misalnya:
Cobalah online!
Contoh
Mari kita ambil contoh di atas (tumpukan tumbuh ke kanan):
Akhirnya mengevaluasi tumpukan: atau dengan kurang kurung X ( X X ) ( X X ) ( X X ) yang kita kenal sebagai tua yang baik S K K identitas fungsi.( ( X ( X X) ) ( X X) ) ( X X) X ( X X) ( X X) ( X X) S K K
Turing kelengkapan
Ide bukti
0
0
2
0
2
Jadi kita berakhir dengan program XOISC yang berbeda (namun sama-sama semantik):
0 0 2 0 2 0 2
Cobalah online!Bukti formal
Mengingat bahwa SKI-kalkulus sudah selesai Turing, kita perlu menunjukkan dua hal:
Bagian pertama - membuktikan ketiga persamaan dalam pendahuluan - sangat membosankan dan memakan tempat, juga tidak terlalu menarik. Jadi alih-alih meletakkannya di pos ini, Anda dapat menemukannya di sini * .
Yang pertama adalah sepele karenaX F1... FN G1... GK f g f g
0
akan meninggalkan di tumpukan sebagai satu ekspresi. Sekarang kita anggap ada dua program ( F 1 ... FProgramF1... FN G1... GK- 1 ( GK+ 1 ) f g g f f g
Penerjemah
Input
Karena kalkulus lambda yang tidak diketik mengharuskan kita untuk menentukan tipe data kita sendiri untuk semua yang kita inginkan dan ini rumit penafsir menyadari angka - angka Gereja - ini berarti ketika Anda memberikan input, maka secara otomatis akan mengubah angka menjadi angka Gereja yang sesuai.
Sebagai contoh, inilah program yang mengalikan dua angka: Coba online!
Anda juga dapat menyediakan fungsi sebagai argumen dengan menggunakan indeks De Bruijn , misalnya
S
kombinator\\\(3 1 (2 1))
(atauλλλ(3 1 (2 1))
). Namun itu juga mengakuiS
,K
,I
dan tentu sajaX
combinator.Keluaran
Secara default, interpreter memeriksa apakah output mengkodekan integer, jika itu akan menampilkan nomor yang sesuai (di samping hasilnya). Untuk kenyamanan ada
-b
bendera yang memberitahu penerjemah untuk mencoba mencocokkan boolean sebagai gantinya (lihat contoh terakhir).Assembler
Tentu saja bahasa tingkat rendah mana pun memerlukan assembler yang mengubah bahasa tingkat tinggi ke bahasa itu, Anda cukup menggunakan input apa pun (lihat di atas) dan menerjemahkannya ke program XOISC dengan menggunakan
-a
bendera, coba online! *** Jika tautannya tidak aktif, ada salinan sebagai komentar HTML di pos ini.
** Ini menghasilkan program yang menguji keutamaan, coba online!
sumber
Seri
Draw adalah OISC yang bekerja pada grid 2D, menandai kotak dengan cara yang mirip dengan mesin Wang B. Namun, untuk menjaga bahasa sesederhana dan OISC-y mungkin, semua instruksi (yang jumlahnya sangat banyak) menandai kotak yang baru saja diinjak, dan, agar dapat berhenti, menginjak sebuah kotak yang ditandai mengakhiri program.
Program ini terdiri dari urutan garis yang berisi pengenal garis (string arbitrer tidak termasuk # atau spasi putih), dua bilangan bulat (
x
dany
) dan dua pengidentifikasi garis lainnya (a
danb
).Program berjalan sebagai berikut:
Mulai dari garis yang diidentifikasi
start
dengan penunjuk yang menunjuk ke posisi (0, 0), gerakkan penunjuk dengan jumlah yang diberikan olehx
dany
dan tandai kotak dengan penunjuk sekarang (kecuali kotak sudah ditandai, dalam hal eksekusi berakhir). Kemudian, lompat ke garisa
jika setidaknya salah satu dari kotak yang berbatasan langsung juga ditandai, dan berbarisb
sebaliknya.Penerjemah didorong untuk menampilkan hasil akhir dari grid seperti semacam gambar, kanvas, dll.
Turing-Kelengkapan
Draw adalah Turing-complete karena memungkinkan untuk mengkompilasi versi yang dimodifikasi (disebut Alternate) dari mesin Minsky ke dalam bahasa.
Tindakan alternatif mirip dengan mesin Minsky dua-penghitung, tetapi ada batasan besar pada perintah: perintah harus bergantian antara menargetkan penghitung pertama dan kedua. Untuk menyiasati modifikasi ini, perintah tambahan telah ditambahkan:
nop
. Perintah ini tidak mengubah penghitung yang ditargetkan sama sekali, yang memungkinkan untuk "pad" perubahan berurutan ke satu penghitung, memenuhi batasan yang diuraikan di atas. Ini juga berarti bahwa register yang akan diubah tidak harus diberikan dan, untuk setiap instruksi yang diberikan, dapat disimpulkan secara langsung dari instruksi dari mana eksekusi dapat melompat ke sana.Contoh: mesin Minsky ini
berubah menjadi program Alternatif ini:
Pembatasan ini diperlukan karena cara program Draw yang terakhir menangani register, yang mengatakan bahwa itu tidak membedakan mereka sama sekali. Sebaliknya, program Draw hanya menyalin register yang belum diubah oleh instruksi sebelumnya, memodifikasinya sesuai dengan instruksi yang dieksekusi.
Kemudian, program Alternate langsung diterjemahkan ke dalam Draw sebagai berikut:
Program dimulai dengan blok ini.
inc
,dec
dannop
diterjemahkan dengan cara yang hampir sama satu sama lain. Dalam semua kasus, tidak ada perbedaan antara mengubah register pertama atau kedua (seperti yang dijelaskan di atas). Ini kenaikan, setara denganinc 2
:Ubah angka di
i1_x
bagian ke indeks instruksi saat ini, dan dii2_x
bagian ke indeks instruksi berikutnya yang akan dieksekusi.The
nop
instruksi dapat diterjemahkan seperti:Ini adalah penurunan:
i3_x
mengacu pada instruksi yang akan dipanggil jika penghitung sudah 1.Berhenti:
Ubah label dengan tepat dan rangkai semuanya menjadi satu. Melakukan ini untuk contoh dari atas memberikan program Draw di repositori dari atas.
Penerjemah
Saat ini ada dua penerjemah, keduanya ditulis dalam Python. Mereka dapat ditemukan di repositori Draw's GitHub .
tujuangrafis yang lebih mudahdan salah, mengambil sumber melalui kotak sembulan saat memulai skrip. Golly bisa sedikit rewel dengan Python, jadi pastikan Anda telah menginstal Python 2 (dan jangan campur 32-bit Golly dengan 64-bit Python atau sebaliknya). Output disediakan melalui grid sel bawaan Golly.Gambar berikut adalah contoh untuk output dari juru bahasa kedua. Menjalankan contoh program di repositori memberikan ini (atau yang serupa):
sumber
-3
Inilah intinya.
Ingatan
Memori adalah peta kaset, di mana kuncinya adalah string dan nilainya adalah bilangan bulat berukuran arbitrer.
Selain itu, ada satu set label, tempat program dapat melompat ke.
Ada tumpukan, yang berisi operan, yang merupakan string.
Ada offest, yang mengontrol di mana dalam kaset memori itu dapat diakses.
Instruksi Satu
-
. Pertama, ia mengeluarkan stringLABEL
dari stack. Jika ituLABEL
tidak didefinisikan sebagai label, itu mendefinisikan label, dan membersihkan sumber label itu (yaitu dari mana ia didorong dari) dan instruksi saat ini. Kalau tidak, ia melakukan perhitungan berikut, menggunakan dua nilai teratas,A
danB
:Perhatikan bahwa jika ada argumen berlebih atau argumen tidak mencukupi, program akan kesalahan keluar, menunjukkan status program.
Offset dapat dimodifikasi dengan mengakses nilai
.
.Kode contoh
Ini menetapkan variabel
i
menjadi7
, dengan menambah7
waktu.Ini dikalikan
i+1
dengan konstanta2
.Bukti Kelengkapan Turing
Mengabaikan ukuran int C ++ (yaitu, dengan asumsi mereka tak terbatas), -3 adalah Turing Lengkap dengan reduksi ke brainfuck 3-sel . Saya dapat mengabaikan ukuran ini karena dapat ditulis interpreter untuk -3 pada komputer dengan memori tak terbatas yang memiliki sel-sel besar yang sewenang-wenang.
Saya juga percaya bahwa BCT dapat ditulis sebagai program -3.
sumber