Tantangan yang saya pikir akan sangat keren adalah membuat penerjemah untuk bahasa Turing-lengkap yang Anda pilih.
Aturannya sederhana:
- Anda dapat menggunakan bahasa apa pun untuk membuat juru bahasa ini meskipun itu lebih baru dari tantangan ini.
- Anda dapat menggunakan bahasa lengkap Turing selama tidak sama dengan yang Anda tulis.
- Anda tidak dapat hanya mengevaluasi kode misalnya menggunakan fungsi eval.
- Penjelasan tentang bagaimana Anda mendekati ini akan menyenangkan tetapi tidak diperlukan.
- Ini akan dinilai dalam byte.
- Setiap pengiriman harus sepenuhnya berfungsi yang berarti bahwa setiap fitur yang bahasa pilihan Anda harus ada.
Sederhananya:
Tugas Anda adalah membuat penerjemah yang berfungsi untuk semua bahasa Turing-lengkap dengan bahasa apa pun yang Anda pilih.
Semoga berhasil!
code-golf
interpreter
arodebaugh
sumber
sumber
eval
solusi sepele .eval
perintah / fungsi, karena beberapa bahasa memiliki built-in untuk mengevaluasi kode dalam bahasa lain.Jawaban:
Brachylog (2) → Posting masalah korespondensi , 9 byte
Cobalah online!
Input adalah daftar daftar string. (Dalam masalah korespondensi Post seperti yang didefinisikan di Wikipedia, daftar bagian dalam masing-masing memiliki dua elemen, walaupun program ini sebenarnya dapat menangani generalisasi untuk sejumlah elemen.) solusi ditemukan. Masalah Post korespondensi diketahui mampu mensimulasikan mesin Turing, dan dengan demikian solusi brute-forcing untuk itu adalah Turing lengkap. Jika dijalankan sebagai fungsi, bukan program, itu sebenarnya menghasilkan output yang bermakna juga.
Program di tautan TIO di atas adalah
[["a","baa"],["ab","aa"],["bba","bb"]]
, yang saya salin dari Wikipedia. Solusinya (yang ditemukan oleh program cukup cepat) adalah["bbaabbbaa","bbaabbbaa"]
.Penjelasan
Ini cukup banyak hanya terjemahan langsung dari masalah korespondensi Post ke Brachylog.
Pada dasarnya, kami membuat daftar yang mengulangi salinan input (sesedikit mungkin, yang berarti bahwa kami tidak melewatkan kemungkinan apa pun saat memaksa), ambil satu elemen dari setiap salinan, lalu gabungkan elemen terkait (seperti dalam korespondensi Post) masalah).
sumber
~dp
(yang tidak berarti hal yang sama tetapi cukup dekat untuk tetap Turing-complete), kecuali bahwa juru bahasa Brachylog belum tahu cara membalikkannyad
.Jelly → "Tambahkan minimum untuk transpos",
54 byteCobalah online! (hanya menjalankan satu iterasi, untuk menghindari timeout)
Konstruksi Turing-complete yang sangat sederhana: kita mengambil matriks persegi sebagai sebuah program, dan mengulang selamanya, mengidentifikasi baris terkecil secara leksikografis, kemudian meningkatkan setiap elemen dari baris pertama dengan elemen pertama dari terkecil secara leksikografis, setiap elemen dari baris kedua oleh elemen kedua terkecil secara leksikografis, dan sebagainya. (Program Jelly adalah "
+"
menambahkan elemen yang sesuai {dari input dan}Ṃ
minimum {dari aslinya},ẞ
loop"; ini adalah byte yang lebih pendek dari program saya sebelumnyaZ+ṂZß
, yang melakukan hal yang persis sama. Jelas saya seharusnya fokus pada golf Jelly, bukan hanya bermain-main dengan bahasa yang diterapkan.)Bahasa yang dihasilkan adalah Turing-lengkap untuk alasan yang sama seperti Kanguru. Elemen pertama dari setiap baris bertindak seperti jumlah lompatan (meskipun alih-alih jumlah lompatan dari setiap perintah berkurang ketika dilewati, kami malah meningkatkan jumlah lewati setiap perintah saat dijalankan, dan mencari perintah dengan jumlah lompatan terendah sebagai gantinya daripada perintah dengan nol lewati hitungan; ini datang ke hal yang sama). Kami memastikan bahwa elemen pertama ini lebih tinggi dari elemen lain (yang mewakili berapa kali setiap perintah muncul di multiset masing-masing perintah), sehingga memastikan bahwa baris pertama tidak pernah minimum; sisa baris pertama bisa menjadi sampah. Satu-satunya masalah yang tersisa adalah memodelkan cara yang memerintahkan dengan jumlah lompatan yang sama dijalankan secara berurutan, tetapi kita dapat melakukannya dengan mengalikan semua jumlah lompatan dengan konstanta besar, kemudian menambahkan "awal" kecil. lewati hitungan ke kolom pertama untuk berfungsi sebagai tiebreak. Ini memberi kita tiebreak dari "perintah pertama yang tidak berjalan berjalan", bukan "perintah yang tidak berjalan berjalan secara siklis secara berurutan", tetapi konstruksi kelengkapan Turing untuk Kanguru tidak peduli dengan perbedaan ini.
sumber
Mathematica menafsirkan Permainan Kehidupan Conway, 64 byte
Permainan Kehidupan Conway dikenal sebagai Turing lengkap; dan automata seluler adalah obsesi Stephen Wolfram yang paling sejati.
CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}
adalah aturan yang mengubah susunan dua dimensi dari 0s dan 1s menurut satu langkah dari Conway's Game of Life. (Saya pikir perilaku default adalah bahwa array ini membungkus ujung-ujungnya, jadi benar-benar torus diskrit.)~Nest~##&
Mengubah aturan ini menjadi fungsi yang, ketika diberi status papan awal (dari dimensi apa pun) dan bilangan bulatn
sebagai argumen, menghasilkan hasiln
iterasi dari aturan Game of Life.Untuk kesenangan Anda sendiri, Anda bisa menggunakan versi yang dibungkus
dan gulir jalan Anda melalui 100 generasi pada papan 50x50.
sumber
Turtlèd menafsirkan CT , 49 byte
Saya mungkin bisa bermain golf ini
Juga, ini tidak menghasilkan sesuatu yang berguna. itu hanya berhenti jika dan hanya jika program CT yang diberikan berhenti.
ini yang saya buat beberapa waktu lalu sebenarnya (kemudian golf beberapa sekarang)
Bagaimana itu bekerja:
Turtlèd menggunakan sel-sel kotak. Ketika saya mengatakan "tulis sesuatu di grid" Maksud saya sekelompok karakter yang berdekatan ditempatkan di grid. contoh
ke dalam program
data dimasukkan terlebih dahulu:
ini pada dasarnya adalah program kucing. itu menulis input ke grid.
kemudian perintah dimasukkan:
apa fungsinya dengan perintah-perintah ini:
perintah ini adalah "produksi". jika bit data paling kiri adalah 1, itu menyalin produksi ke akhir string data. jika tidak, tidak ada yang terjadi. kemudian bit data paling kiri dihapus, dan menggunakan produksi berikutnya dengan bit data paling kiri berikutnya. program berhenti ketika tidak ada bit dalam data string. Cara untuk melakukan produksi ini adalah dengan menangani bit dan akhir produksi secara terpisah. inilah yang dilakukan oleh program kami. secara terpisah menyalin bit dari string perintah ke akhir string data, dan secara terpisah menghapus bit dari datastring
ke bagaimana program ini melakukannya. setelah memasukkan perintah, penyu / penunjuk grid bergerak kembali ke bit paling kiri dari datastring. kemudian masuk ke dalam satu lingkaran
apa yang dilakukannya di loop ini, apakah bergerak naik dari datastring paling kiri, dan menuliskan karakter perintah saat ini (u.). jika;; akhir produksi, bergerak ke bawah dan menghapus bit data paling kiri di bawahnya dan bergerak kembali ke atas (
(;d' u)
). lalu, bagaimanapun, ia bergerak ke bawah satu (d
). jika bit di sana tidak dihapus, itu berarti ia harus memeriksa apakah akan menyalin sedikit dari perintah di akhir. jadi, jika karakter ini adalah databit paling kiri atau adalah 1, itu akan pindah ke ujung kanan dari string data, menyalin bit dari string perintah, dan pindah kembali ke ruang kiri dari data paling kiri bit ((1[ r].[ l])
). sekarang, itu adalah pada databit paling kiri, yang merupakan nol, atau kiri dari databit paling kiri. jadi, kita bergerak ke kanan jika di suatu tempat (( r)
). kemudian, penunjuk perintah bertambah sehingga kita akan menuliskan perintah berikutnya dalam iterasi loop berikutnya. Jika tidak ada lagi datastring, ini berarti kita akan berada di spasi dan loop akan berakhir. kalau tidak kita jalankan kembali loop.sumber
Perl → varian Programmer Tiga Bintang , 26 + 1 = 27 byte
Cobalah online! (Tautan ini berisi tajuk yang keluar dari program setelah sejumlah iterasi (sehingga TIO tidak kehabisan waktu), dan untuk mencetak keadaan internal setiap iterasi (sehingga ia melakukan sesuatu yang dapat diamati).)
Jalankan dengan
-a
(penalti 1 byte, karena Anda dapat memasangnya sebelum-M5.010
untuk menghasilkan-aM5.010
).Secara khusus, ini mengimplementasikan Three Star Programmer di mana perintah dipisahkan oleh spasi dan tidak ada komentar yang diizinkan dalam file, tanpa ekstensi I / O. (Perubahan-perubahan ini tidak ada bedanya dengan kelengkapan Turing bahasa, jelas.) Tidak ada bukti kelengkapan Turing untuk Programmer Bintang Tiga daring, tetapi Turing-lengkap (saya telah membagikan bukti sketsa Turing-nya) -completeness dengan esoprogrammer lain, tetapi berhenti bekerja pada bahasa ketika saya menemukan bahwa itu sebenarnya cukup mudah untuk diprogram begitu Anda sudah mendapatkan kejutan asli).
Program ini tidak terlalu membutuhkan penjelasan; Programmer Tiga Bintang memiliki spesifikasi yang sangat sederhana, dan ini adalah terjemahan langsungnya. Satu-satunya titik halus:
@F
adalah input ke program dalam bentuk array (ini merupakan konsekuensi dari-a
); danredo
akan mengulangi seluruh program karena berada dalam loop implisit (juga konsekuensi dari-a
).sumber
perakitan x86 (Intel sintaks / MASM) -Brainfuck 2127 byte.
Masih bisa bermain golf
sumber
Pip menginterpretasikan sistem tag siklik , 16 byte
Mengambil produksi sistem tag sebagai argumen baris perintah dan string data awal dari stdin.
Kode di atas agak sulit untuk diverifikasi karena tidak menghasilkan output apa pun (sehingga perilaku yang hanya dapat diamati adalah "mengakhiri" vs. "tidak mengakhiri"). Oleh karena itu, inilah versi yang tidak diklik yang mengeluarkan string data setelah setiap langkah, dan juga berakhir setelah 20 langkah sehingga TIO tidak harus berurusan dengan banyak output dari loop tak terbatas: Coba online!
Sistem tag siklik
Sistem tag Cyclic adalah model komputasi Turing-complete yang sangat sederhana namun lengkap . Mereka terdiri dari daftar produksi yang menentukan operasi pada string data . Produksi dan string data terdiri dari 1 dan 0.
Pada setiap langkah, karakter paling kiri dari string data dihapus.
Dalam kedua kasus, produksi saat ini bergerak ke produksi berikutnya dalam daftar, secara siklis: jika kita berada di produksi terakhir, kita berputar ke yang pertama. Eksekusi berlanjut hingga string data kosong.
Penjelasan
sumber
1
sumber: esolangs link ke ini arxiv.org/abs/1312.6700 . Saya akan mengedit jawaban saya segera, dan jika ini membantu jawaban Anda Anda harus (tbh masukan Anda tampaknya cukup golf sebenarnya)Fungsi Iterated Generalized Collatz -> Python 2, 46 byte
Sebut fungsi ini dengan daftar m-1 a dan b, nilai awal x, dan pembagi m, yang secara kolektif merupakan "program" untuk IGCF. Alih-alih mengambil array ketiga untuk menunjukkan moduli mana yang akan berhenti, ini hanya berhenti setiap kali modulus m-1. Penyederhanaan ini berarti mungkin diperlukan usaha ekstra untuk mengubah program Fractran yang diberikan menjadi varian ini, tetapi ini menghemat beberapa byte dalam interpreter.
Cobalah online! TIO ini menunjukkan cara menambahkan 5 + 5 dengan bahasa ini. Program a = [3], b = [0], m = 2 melakukan penambahan, dan dimulai dengan 7776 = 2 ^ 5 * 3 ^ 5 akhirnya menghasilkan 59049 = 3 ^ 10.
sumber
Varian RESPlicate -> Python 2, 47 byte
Fungsi ini menafsirkan varian ResPlicate
Perubahan terakhir berarti bahwa beberapa program ResPlicate (yang memenuhi syarat pertama) tidak akan berperilaku sama dalam varian ini, tetapi untungnya, penerjemah BCT tidak memerlukan fungsionalitas yang dihapus, dan bahasa tetap TC.
Cobalah online! TIO ini memiliki cetakan yang terjepit di dalamnya untuk menunjukkan bahwa ia berfungsi dan tajuk yang membunuh program setelah 1 detik dan contoh yang mengelola untuk menghasilkan lebih banyak keluaran daripada yang dapat ditangani TIO dalam satu detik itu.
sumber
l=input()
? Akan lebih pendek satu byte.Perl
-a
→ mesin I / D , 24 byteCobalah online! (berisi tajuk yang mencetak keadaan internal dan berhenti setelah 10 iterasi, sehingga perilaku dapat diamati)
Tentang bahasanya
Saya telah menghabiskan beberapa hari terakhir bekerja pada mesin I / D , salah satu ide terbaru saya untuk bahasa pemrograman yang sangat sederhana. Ini berfungsi sebagai berikut: penyimpanan data terdiri dari RAM yang tidak terikat, awalnya semua nol. Setiap elemen dapat menyimpan integer yang tidak terikat (meskipun dalam praktiknya, sebagian besar program mesin I / D hanya akan menyimpan integer kecil di sebagian besar dari mereka, dan memanfaatkan integer yang tidak terikat hanya sebagai cara menangani sel dengan alamat yang besar). Ada juga penunjuk data, yang menunjuk ke sel (mis. Menyimpan alamat sebagai sel); awalnya juga nol.
Hanya ada dua perintah:
I
: Menambahkan sel yang ditunjuk oleh pointer data. (Penunjuk data itu sendiri tetap tidak berubah.)D
: Dereferensi pointer data, yaitu membaca nilai sel yang menunjuk pointer data. Kemudian simpan nilai yang dihasilkan yang Anda baca kembali ke penunjuk data.Eksekusi hanya menjalankan program berulang kali, selamanya.
Cukup mengejutkan bahwa bahasa yang sederhana ini adalah Turing-complete, jadi saya telah berusaha membuktikannya. Inilah buktinya . Ini sangat mirip dengan (tetapi lebih sederhana dari) bukti untuk Program Tiga Bintang, bahasa yang sangat mirip (dan pada kenyataannya, pengajuan ini menggunakan "shell" OISC dasar yang sama di sekitar program, berbeda hanya dalam instruksi aktual yang diterapkan).
Tentang program ini
Pemakaian
Input harus diberikan pada input standar, dan merupakan program mesin I / D tanpa komentar, dan menggunakan sintaks RLE / OISC. (Mesin I / D memiliki dua sintaks yang sama dan ekuivalen, tetapi untuk golfiness program ini hanya mendukung salah satunya). Dalam sintaksis ini, suatu program adalah urutan angka dalam desimal, yang mewakili lamanya menjalankan
I
perintah di antaraD
perintah. (Anda dapat menentukan dua atau lebihD
perintah berturut-turut dengan menempatkan "I
perintah 0 dijalankan " di antaranya, sehingga sintaksnya sepenuhnya umum.)Penjelasan
Seperti yang dapat dilihat dari program, ini tidak mengimplementasikan
I
danD
memerintahkan secara individual. Bahkan, itu adalah penerjemah yang mengoptimalkan (sangat sedikit) (murni karena lebih pendek untuk menulis dengan cara ini). Kuncinya adalah untuk melihat bahwa menjalankan n perintah kenaikan increment target pointer data n kali, yaitu menambahkan n untuk itu; dan menjalankan 0 perintah kenaikan juga dapat diimplementasikan dengan cara ini, karena menambahkan 0 ke memori tidak berpengaruh. Jadi operasi yang sebenarnya kita implementasikan adalah bergantian antara mengimplementasikan run-of-I
dan aD
. Atau dengan kata lain, "tambah nke nilai yang ditunjuk oleh penunjuk data (menyimpannya kembali dalam nilai yang ditunjuk oleh penunjuk data), kemudian membaca nilai yang ditunjuk oleh penunjuk data dan menyimpannya di penunjuk data ". Itu jelas lebih bertele-tele daripada yang dibutuhkan menjadi, dan kita lebih lanjut dapat menyederhanakan ini untuk "menambahkan n ke nilai yang ditunjuk oleh pointer data, kemudian menyimpan nilai itu baik dalam target pointer data dan pointer data itu sendiri".Sehingga menjadikan inti dari program kami. Kami menggunakan array
$a
untuk menyimpan RAM, dan$p
sebagai penunjuk data (mengindeks ke dalam array):Dengan mudah, Perl mengartikan elemen array yang tidak diinisialisasi sebagai 0 ketika mereka diperlakukan seperti angka, sehingga array akan malas diinisialisasi ke nol untuk kita tanpa kode eksplisit untuk itu yang diperlukan. (Salah satu masalah potensial adalah akurasi numerik ketika angka menjadi besar; namun, itu hanya akan terjadi jika jumlah array yang digunakan melebihi ruang alamat mesin (bilangan bulat Perl cukup besar untuk menampung pointer), sesuatu yang tidak bisa terjadi pada mesin yang diidealkan.)
Akhirnya, yang perlu kita lakukan adalah menempatkan program ini ke dalam beberapa loop. The
for@F
Loop, dikombinasikan dengan-a
opsi baris perintah, akan loop atas bidang input standar (definisi default "lapangan" di sini akan dibagi pada spasi). Theredo
Loop akan menempatkan seluruh program dalam loop implisit (selain, nyaman, pembacaan input standar), yang akan menyebabkan program untuk berjalan dalam lingkaran berulang-ulang, seperti yang dipersyaratkan oleh semantik mesin I / D.sumber
-a
'. codegolf.meta.stackexchange.com/a/14339/9365Jelly → sistem 2-Tag , 8 byte
Cobalah online!
Saya memiliki karunia yang disukai bahasa praktis, tetapi saya pikir saya mungkin juga mencoba untuk memenangkan tugas asli ketika saya berada di sana (karena saya tidak bisa memenangkan hadiah saya sendiri).
Menerapkan varian sistem tag tanpa status penghentian, karena tidak diperlukan untuk kelengkapan Turing. Negara-negara diberi nomor dari 1, berturut-turut, dan string awal datang sebelum program.
Sebagai contoh, Wikipedia memberi contoh sistem tag {
a
,b
,c
}, {a
→bc
,b
→a
,c
→aaa
} dengan string awalaaa
; dalam format masukan ini, itu[1,1,1]
,[[2,3],[1],[1,1,1]]
. (Sistem tag tidak memiliki sintaks tetap, dan ini sepertinya cara yang masuk akal untuk melakukannya.)TIO memiliki tautan yang ditambahkan
Ṅ
("tulis status internal dan baris baru ke stdout") untuk menunjukkan bahwa program tersebut ternyata berfungsi.Penjelasan
sumber
BF / P "diimplementasikan dalam Mesin Turing, 842 byte
Tabel transisi (ditautkan karena panjangnya)
Tabel transisi, versi kurang golf
Simulator Turing Machine yang saya gunakan
Ini jelas tidak akan memenangkan penghargaan lama, tapi itu adalah sesuatu yang selalu ingin saya lakukan, karena BF sangat mirip dengan Mesin Turing. Setiap sel menyimpan nilai dari
0x0
-0xF
. Namun lebarnya sejauh ini situs web Turing Machine dapat berjalan tanpa merusak browser Anda. Fungsi,
dan.
(input dan output) tidak didefinisikan, jadi sedikit lebih seperti P "daripada BF yang sebenarnya.Untuk menjalankannya, tempel tabel transisi ke dalam simulator Turing Machine, atur input ke beberapa kode BF, dan tekan run.
Rekaman TM menyimpan kode BF dan data BF, dengan satu spasi di tengah. Itu melacak posisinya dalam kode dengan memodifikasi karakter yang sedang berjalan (
[
->(
, dll) dan posisinya dalam data dengan^
di depan sel. Setelah membaca karakter perintah, itu bergerak sampai menyentuh tanda sisipan, memindahkan satu sel ke kanan, dan melakukan fungsi yang sesuai. Kemudian kembali, mencari salah satu karakter perintah "dimodifikasi" dalam kode BF, dan pindah ke yang berikutnya, mengulangi seluruh proses. Setelah kehabisan kode, itu terhenti.Cara terbaik untuk memahami cara kerjanya adalah dengan menjalankan versi yang tidak diserang, menempatkannya pada mode langkah, dan menonton garis mana yang mengarah ke yang lain dan apa yang dilakukan setiap negara bagian / blok garis.
Versi golf dan ungolfed persis sama dalam hal cara kerjanya, tetapi versi ungolfed memiliki lebih banyak nama yang ramah manusia dan dipecah menjadi beberapa bagian.
sumber
C mengimplementasikan (2,3) Mesin Turing ,
236205 byte (4631 lebih sedikit jika Anda tidak peduli dengan input yang canggung)Terima kasih kepada Appleshell untuk -11 byte, VisualMelon untuk -12 byte, dan Johan du Toit untuk -7 byte.
CeilingCat membuat versi yang hanya menggunakan 144 byte, lihat di sini .
(Saya telah menambahkan beberapa jeda baris di sini sehingga Anda tidak perlu menggulir, tetapi biasanya sebagian besar akan dihapus)
Cobalah online!
Untuk menggunakan: Masukkan string hingga 256 yang, nol, dan dua untuk menginisialisasi rekaman itu. Nilai yang tidak diinisialisasi akan menjadi nol. (Nilai selain 0, 1, dan 2 dapat menyebabkan perilaku tidak terdefinisi.) Program akan mengulangi lebih dari 256 langkah. Jumlah langkah yang diulanginya dapat ditingkatkan dengan memodifikasi kode, tetapi jelas itu membutuhkan lebih banyak karakter.
Ini entri yang cukup panjang, tetapi ini adalah pertama kalinya saya melakukan salah satu dari ini dan saya tidak menggunakan bahasa golf khusus. Saya bersenang-senang, meskipun ternyata lebih lama dari yang saya harapkan.
Banyak byte dari berurusan dengan input dan output, dan saya kehilangan seluruh 42 byte dengan membuatnya menerima 0, 1, dan 2 bukannya NUL, SOH, STX. (Untuk mengubahnya, hapus
k;
dari depan danfor(;k<256&&d[k];)d[k++]-=48;
dari baris kedua.)Tabel transistion, terutama garis
*p=-t*t+(2-s)*t+1+s;
(yang menetapkan nilai-nilai pada rekaman itu) mungkin dapat dikompresi juga.sumber
k,j;c s,d[256];
(int
tersirat dalam C, maka Anda juga dapat pindahi
ke deklarasi global untuk menghemat 3 byte lebih banyak)k++
dan menghapus{}
menyimpan beberapa byte lagi:for(;k<256&d[k];)d[k++]-=-48;
Karenaj
hanya pencatat waktu (nilai tidak pernah digunakan) Anda dapat menggantinya (dani
) dengank
menghitung mundur: Anda tahuk==256
setelah loop pertama, jadi hitung mundur ke nol di detikfor(;k>0;)
, yang tersisak==-1
, sehingga loop terakhir bisa menjadifor(;++k<256;)
. (Penafian: Saya biasanya bermain golfC#
, tetapi ini sepertinya mengkompilasi).k<256&&d[k]
, bukan&
, karenad[k]
sedang dievaluasi padak==256
. Juga, karenak
tidak lagi dijamin256
setelah loop itu, saya harus mengatur ulang setelah itu untuk menjamin 256 langkah. (Jika Anda (yaitu, VisualMelon) memiliki saran lain, kami mungkin harus menempatkan mereka dalam obrolan sehingga kami tidak mendapatkan terlalu banyak komentar)Röda menerapkan Fractran ,
114112106 bytes1 byte disimpan berkat @fergusq dengan mengatur ulang parameter
Cobalah online!
Memanggil fungsi seperti:
f reference_to_input program
. Output akan disimpan di lokasiinput
.sumber
e[1]
adalah mubazir. Anda juga dapat menyimpan satu byte dengan mengubah urutan parameter:f&n,a
.f&n,a
triknya, dan saya baru saja akan menghapus semi-colon itu ketika Anda berkomentar :)Clojure,
8281 byte (Mesin Turing)Pembaruan: menghapus spasi dari
t{} s
.Menerapkan Mesin Turing sebagai loop, mengembalikan kaset saat keadaan terhenti tercapai. Dalam aturan transisi negara ini ditunjukkan dengan mengabaikan keadaan transisi. Ini settins
N
untuknil
dan selanjutnyaif-let
akan batalkan sebagai transisi negara terkait tidak ditemukan dari input hash-peta%
. Sebenarnya nilai apa pun untuk keadaan ini akan dilakukan, seperti:abort
, 0 atau -1.Tidak disatukan dengan contoh berang-berang sibuk 2-simbol 3-negara dari Wikipedia .
Cobalah online .
Pada inti tunggal 6700K, ini menjalankan berang-berang sibuk 2-simbol 5-negara (47,1 juta langkah) dalam waktu sekitar 29 detik, atau 1,6 juta langkah / detik.
sumber
M → Kiat , 4 byte
Cobalah online!
TIO link menambahkan footer untuk memanggil fungsi dengan contoh program Tip yang ditampilkan pada halaman Esolang ("pembungkus otomatis" M untuk memanggil fungsi seolah-olah mereka program tidak dapat menangani angka-angka rasional atau titik tetap, atau setidaknya saya berlindung tidak tahu bagaimana cara mengatakannya, jadi saya perlu membuat fungsi menjadi program lengkap dengan tangan untuk dapat menjalankannya.)
Ini sebenarnya mencetak hasil debug berguna; program tidak dapat ditulis dalam 3 byte dalam M karena program yang terdiri dari tepat tiga diad memicu kasus khusus di parser, jadi saya harus menambahkan perintah tambahan untuk menghindari kasus khusus. Membuatnya
Ṅ
(mencetak dengan baris baru) setidaknya memberinya tujuan yang bermanfaat.ı
Tidak menerapkan I / O (selain berhenti / tidak berhenti). I / O adalah ekstensi untuk Tip (bukan bagian dari bahasa itu sendiri), dan tidak diperlukan untuk kelengkapan Turing.
Penjelasan / latar belakang
[1,2,3]
[1,2,3,1,2,3,1,2,3,…]
ḅ
Jadi saya melihat ke belakang dan mengevaluasi kembali sedikit. Apakah ada operasi yang dapat kita gunakan daripada evaluasi polinomial? Idealnya, yang komutatif, jadi kita tidak perlu khawatir tentang urutan argumen? Segera setelah itu, saya menyadari bahwa fungsi Collatz lebih kompleks daripada yang seharusnya.
Dan tentu saja, tidak seperti konversi basis (
ḅ
), multiplikasi (×
) bersifat komutatif, dan dengan demikian tidak masalah urutan urutan argumen. Jadi yang perlu kita tulis adalah×ị
, dan kemudian menempatkan program ke dalam rekursi tak terbatas denganß
, dan kami memiliki bahasa lengkap Turing. Kanan?¹×ịß
¹
¹
Ṅ
adalah pilihan yang baik karena menghasilkan keluaran debug yang bermanfaat.Apakah tiga byte mungkin? Kecuali saya kehilangan sesuatu, tidak dengan pilihan implementasi dan implementasi bahasa yang spesifik ini, tetapi pada titik ini sepertinya sepertinya mungkin, karena ada begitu banyak cara untuk melakukannya dalam empat dan begitu banyak Turing-complete bahasa yang bisa Anda terapkan.
sumber
ḋ
danṙ
bukannya×
danị
; bahasa yang dihasilkan tidak sama dengan bahasa Tip, tetapi cukup mirip dan hampir pasti Turing-lengkap untuk alasan yang sama. Sayangnya,ḋ
tidak diimplementasikan dalam M, dan saya tidak dapat menemukan cara untuk membuat Jelly melakukan perhitungan presisi arbitrer ketika salah satu input adalah bilangan real non-integer. Namun, jika ada yang tahu bahasa golf lain di mana konstruksi ini bisa berfungsi, silakan mencobanya.C menafsirkan Brainfuck, 187 byte
Cobalah online
sumber
Lua menafsirkan Brainf ***, 467 bytes
Saya tahu masih ada beberapa pelangsingan yang bisa saya lakukan nanti, tetapi disinilah pass pertama saya berakhir. Mengambil kode brainf dari input standar.
sumber
brains
, selalu menyenangkan ketika pegolf menentukan daftar variabel.CJam → ResPlicate Variant,
151413 byte-1 byte terima kasih kepada @ ais523
Variannya sama dengan yang ada di jawaban ini , kecuali bahwa jumlah item yang diambil dari antrian adalah satu kurang dari jumlah teratas pada antrian.
Bagian
l~{ ... }h
hanya mengambil array sebagai input dan mengulangi sampai array kosong.Penjelasan untuk loop utama:
sumber
Chip , 20 + 3 = 23 byte (Aturan 110)
+3 untuk bendera
-z
Cobalah online!
Pengajuan ini tidak sempurna, karena Chip belum (belum) memiliki kemampuan pengulangan, jadi output harus dilewatkan sebagai input untuk mensimulasikan beberapa generasi, dengan sesuatu seperti ini (tentu saja, Anda dapat menjalankan loop itu tanpa batas, dan Chip dapat menangani input panjang yang sewenang-wenang, jadi kombinasi ini Turing Lengkap).
Implementasi ini mengambil input dan memberikan output dalam bentuk ASCII
0
dan1
s. Logikanya di sini adalah sebagai berikut:Sisa elemen adalah untuk housekeeping:
e*f
menyebabkan output angka ASCII, danE~Zt
mengakhiri eksekusi dua byte setelah input habis (karena lebar tumbuh 2 setiap generasi).sumber
Clojure, 75 byte (Sistem tag Cyclic)
Pembaruan 1: diganti
some?
dengannil?
.Pembaruan 2: Memperbaiki yang hilang
S
di cabang lain diif s
.Menerapkan sistem tag siklik , kembali
nil
jika program berhenti, berulang-ulang jika tidak. Clojure benar-benar bersinar di sini dengan urutan malas yang tak terbatas (seperti siklus ) dan perusakan . Yang dan nol ditunjukkan sebagai nilai benar dan salah. Ketika string data habiss
menjadinil
.Tidak Disatukan:
Contoh hasil:
sumber
JavaScript menafsirkan Aturan 110 , 131 byte (99 byte ?, 28 byte?)
Seperti yang Anda lihat, kode ini mendefinisikan 3 fungsi
a
,,b
danc
. Mungkin dimungkinkan untuk menyimpan byte dengan menggabungkannya dalam 1 fungsi (saya tidak melihat caranya), tapi ada baiknya terpisah karena masing-masing sudah memenuhi tantangan ini dalam beberapa hal.Fungsi
a
mengambil 3 angka sebagai input dan menghitung beberapa polinomial aneh dari mereka. Ketika 3 angka ini0
atau1
mereka dapat dilihat sebagai Aturan 110 sel. Paritas outputa
kemudian dapat dilihat sebagai nilai sel tengah pada generasi berikutnya. Jadi dalam arti tertentu, fungsi sederhana ini sudah menjadi 'penerjemah' Aturan 110 (28 byte):Kami kemudian dapat membuat fungsi baru
b
yang mengevaluasia
setiap karakter dari string satu dan nol. Inib
kemudian, dengan cara yang lebih baik daripadaa
, seorang penerjemah Aturan 110. Mengambil mod 2 setelah evaluasi kurung hemat (99 byte):Untuk benar-benar menghitung fungsi dengan Aturan 110, pengguna harus menentukan keadaan awal dan jumlah generasi setelah mana output akan 'muncul'. Kita dapat membuat fungsi ketiga
c
yang mengambil string satu dan nol, dan bilangan bulat positifn
, yang kemudian dievaluasib
pada string,n
kali. Seperti ini kita benar-benar dapat melihat Aturan 110 sebagai bahasa pemrograman, di mana program adalah keadaan awal dan angkan
, dan hasilnya adalah keadaan setelahn
beberapa generasi. Fungsic
sekarang menjadi penerjemah aktual untuk bahasa pemrograman sehingga kode akhir untuk tantangan ini adalah apa yang saya sajikan di atas.sumber
JS -> Newline 854 byte
Super golf berkat Google.
sumber
var
pernyataan:var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1;
var
tyClojure, 87 byte (Aturan 110)
Kredit untuk kode paritas jatuh ke Jens Render! Saya benar-benar berjuang tentang cara mengekspresikan ini dan saya akan pergi dengan mengubah
[p q r]
dari biner ke integer dan menggunakan tabel pencarian.partition
Destrukturisasi di sini dan Clojure membuat aplikasi logika cukup sederhana. Fungsi ini mengembalikan urutan keadaan yang tak terbatas, sehingga pemanggil bertanggung jawab atastake
sebanyak yang mereka butuhkan atau hanyanth
untuk melompat ke keadaan tertentu. Jika bantalan dengan nol adalah dua elemen dan bukan hanya satu maka pita akan terus tumbuh, menghindari masalah batas. Sekarang tetap lebar aslinya.Contoh:
sumber
cycle
akan mampu membangun pola padding tak terbatas, tetapi menjalankan langkah pertama akan memakan waktu tak terbatas: /APL (Dyalog) → Varian fraktran , 15 byte
Cobalah online!
Fungsi mengambil dalam rasional sebagai daftar angka daripada dua daftar yang berisi pembilang dan penyebut, dan output hasilnya jika program berakhir. Ini mengimplementasikan varian Fractran yang memiliki 1/1 rasional (= 1) di akhir program. Angka 1 tidak memiliki efek pada kelengkapan Turing (sejauh yang saya mengerti) karena input ke program hanya mendarat pada 1 ketika tidak ada rasional lainnya bekerja, dan ketika itu terjadi, input tidak berubah. Ini hanya digunakan agar fungsi tahu kapan harus mengakhiri.
TIO link menjalankan fungsi untuk 2 iterasi (sehingga Anda dapat melihat output karena program tidak berakhir) pada input pertama, dan menjalankan input kedua hingga selesai, setelah itu mengembalikan output.
(⊃0~⍨××0=1|×)⍣≡
mengambil daftar rasional sebagai argumen kiri, untuk disebut sebagai ⊣, dan input sebagai argumen yang tepat, disebut sebagai to(⊃0~⍨××0=1|×)
kereta fungsi1|×
dapatkan bagian setelah titik desimal (modulo 1) dari produk×
⊣ dan ⊢0=
apakah ini sama dengan 0?××
kalikan hasil ini dengan ⊣ × ⊢, di mana pun × rasional ⊢ bukan bilangan bulat, itu diganti dengan 00~⍨
hapus semua 0s⊃
dapatkan elemen pertama⍣
loop sampai≡
input tidak berubah, perhatikan bahwa hasil(⊃0~⍨××0=1|×)
digunakan kembali sebagai input, jadi jika itu berhenti berubah (sebagai hasil dari 1 di akhir) program berhentisumber
JavaScript: Kalkulus Lambda (
123114)Diwakili menggunakan Kebijakan Debruijn di Duples.
Combinator S adalah
[0, [0, [0, [[3, 1], [2, 1]]]]]
K adalah
[0, [0, 2]]
Saya adalah
[0, 1]
Edit: Dicukur 9 byte dengan menggantinya
"number"==typeof c
dengan!isNaN(c)
sumber
APL (Dyalog Unicode) , 15 byte SBCS
Program lengkap yang mengimplementasikan pelaksana otomat seluler satu dimensi yang digeneralisasi. Ini termasuk Aturan 110 yang Turing lengkap. Anjurkan stdin untuk keadaan awal, jumlah iterasi (atau
≡
untuk melanjutkan hingga stabil atau{⍵≡⎕←⍺}
untuk menampilkan semua nilai perantara hingga stabil), dan atur aturan.Cobalah online! (4 iterasi Aturan 110)
⎕
meminta status awal dan⊢
menghasilkan itu (memisahkan negara dari jumlah iterasi)⍣⎕
meminta jumlah iterasi dan menerapkan fungsi berikut yang berkali-kali:(
...)
terapkan fungsi diam-diam berikut:⌺3
dapatkan semua lingkungan panjang-3 (dengan info apakah mereka ada di tepi) dan terapkan fungsi diam-diam berikut untuk setiap pasangan:⊂
lampirkan lingkungan∘
dan⊢
menghasilkan itu (membuang info tentang berada di tepi)∘
kemudian∊⍨
periksa apakah mereka anggota⎕
meminta daftar lingkungan yang mengarah pada iterasi berikutnyasumber