Tujuan dari tantangan ini adalah (pada akhirnya) mengeluarkan setiap program penghentian yang mungkin dalam bahasa pilihan Anda. Pada awalnya ini mungkin terdengar mustahil, tetapi Anda dapat melakukannya dengan pilihan perintah eksekusi yang sangat hati-hati.
Di bawah ini adalah diagram ASCII untuk menggambarkan hal ini. Biarkan kolom mewakili penomoran dari setiap program yang mungkin (setiap program adalah jumlah simbol hingga dari alfabet terbatas). Biarkan setiap baris mewakili langkah tunggal dalam pelaksanaan program itu. Sebuah X
mewakili eksekusi yang dilakukan oleh program itu pada langkah-waktu itu.
step# p1 p2 p3 p4 p5 p6
1 X X X X X X
2 X X X X X
3 X X X X
4 X X X X
5 X X X
6 X X
7 X X
8 X X
9 X X
∞ X X
Seperti yang Anda tahu, program 2 dan 4 tidak berhenti. Jika Anda menjalankannya satu per satu, controller Anda akan terjebak dalam infinite loop yaitu program 2 dan tidak pernah menghasilkan program 3 dan seterusnya.
Sebagai gantinya, Anda menggunakan pendekatan dovetailing . Surat-surat tersebut mewakili kemungkinan urutan eksekusi untuk 26 langkah pertama. Ini *
adalah tempat di mana program itu terhenti dan dikeluarkan. Ini .
adalah langkah-langkah yang belum dijalankan.
step# p1 p2 p3 p4 p5 p6
1 A C F J N R V
2 B E I M Q * Z
3 D H * P U
4 G L T Y
5 K O X
6 * S .
7 W .
8 . .
9 . .
∞ . .
Persyaratan untuk bahasa target
Bahasa target (yang ditafsirkan paralel) harus Turing-complete. Selain itu, itu bisa bahasa apa pun yang Turing-lengkap, termasuk himpunan bagian Turing dari bahasa yang jauh lebih besar. Anda juga bebas menafsirkan hal-hal seperti aturan sistem tag siklik. Anda juga diizinkan membuat bahasa untuk diuji, selama Anda dapat menunjukkan mengapa bahasa Turing-lengkap.
Sebagai contoh, jika Anda memilih untuk menguji brainfuck, maka yang terbaik adalah hanya menguji []-+<>
subset, karena input tidak didukung dan output dibuang begitu saja (lihat di bawah).
Ketika datang ke program "controller" (yang Anda main golf), tidak ada persyaratan khusus. Pembatasan bahasa normal berlaku.
Cara membuat daftar program tanpa batas
Mayoritas bahasa pemrograman dapat direpresentasikan sebagai serangkaian simbol dari alfabet hingga. Dalam hal ini, relatif mudah untuk menyebutkan daftar setiap program yang mungkin dalam urutan bertambah panjang. Alfabet yang Anda gunakan harus mewakili persyaratan bahasa target. Dalam kebanyakan kasus, ini adalah ASCII yang dapat dicetak. Jika bahasa Anda mendukung Unicode sebagai fitur tambahan, Anda tidak boleh menguji setiap kemungkinan kombinasi karakter Unicode, cukup ASCII. Jika bahasa Anda hanya menggunakan []-+<>
maka jangan menguji berbagai kombinasi karakter "komentar" ASCII. Bahasa seperti APL akan memiliki huruf khusus mereka sendiri.
Jika bahasa Anda dijelaskan dengan cara non-alfabet, seperti Fractran atau Turing Machines, maka ada metode lain yang sama-sama valid untuk membuat daftar semua program yang mungkin valid.
Menafsirkan daftar program yang terus berkembang
Bagian penting dari tantangan ini adalah menulis penerjemah paralel untuk daftar program yang terus bertambah. Ada beberapa langkah dasar untuk ini:
- Tambahkan sejumlah program ke dalam daftar
- Menafsirkan setiap program dalam daftar secara individual untuk periode waktu yang terbatas. Ini dapat dicapai dengan melakukan satu langkah instruksi untuk masing-masing. Simpan semua status.
- Hapus semua program terminating / melempar kesalahan dari daftar
- Keluarkan program * yang terhenti dengan bersih
- Tambahkan beberapa program lagi ke daftar
- Simulasikan setiap program secara bergantian, ambil eksekusi dari program yang lebih lama di mana ia tinggalkan
- Hapus semua program terminating / melempar kesalahan dari daftar
- Keluarkan program * yang terhenti dengan bersih
- ulangi
* Anda seharusnya hanya mengeluarkan program yang berhenti dengan bersih. Ini berarti bahwa tidak ada kesalahan sintaksis atau pengecualian yang tidak tertangkap selama eksekusi. Program yang meminta input juga harus dihentikan tanpa mengeluarkannya. Jika suatu program menghasilkan keluaran, Anda tidak harus menghentikannya, buang saja hasilnya.
Lebih banyak aturan
- Anda tidak boleh menelurkan utas baru untuk memuat program yang telah diuji, karena ini melepaskan kerja paralelisasi ke OS host / perangkat lunak lain.
- Sunting: Untuk menutup celah potensial di masa depan, Anda tidak diizinkan untuk
eval
(atau fungsi terkait lainnya) menjadi bagian dari kode program yang diuji . Anda dapateval
membuka kunci kode dari kode juru bahasa. (Jawaban BF-in-Python masih valid berdasarkan aturan ini.) - Ini adalah kode-golf
- Bahasa tempat Anda menulis kiriman tidak harus sama dengan bahasa yang Anda uji / hasilkan.
- Anda harus mengasumsikan bahwa memori yang tersedia tidak terikat.
- Saat membuktikan kelengkapan Turing, Anda dapat mengasumsikan bahwa input di-hardcode ke dalam program, dan hasilnya dapat dibaca dari kondisi internal program.
- Jika program Anda menghasilkan sendiri, itu mungkin salah atau polyglot.
sumber
"If your program outputs itself, it is probably wrong or a polyglot."
Jawaban:
subleq OISC dengan Python,
317269 bytehttps://esolangs.org/wiki/Subleq
Program subleq adalah daftar bilangan bulat yang dapat diperluas (p) dan penunjuk instruksi (i). Varian subleq ini menggunakan pengalamatan relatif, yang disarankan oleh halaman pembicaraan wiki untuk memastikan kelengkapan dengan nilai yang dibatasi. Setiap centang, operasi
p[i+p[i+1]]-=p[i+p[i]]
dilakukan, dan kemudiani+=p[i+2]
jika hasil operasi adalah <= 0, jika tidaki+=3
. Jika saya pernah negatif, program berhenti.Implementasi ini menguji setiap program yang status awalnya terdiri dari bilangan bulat non-negatif satu digit (0-9) dengan penunjuk instruksi awal 0.
Outputnya terbalik, karena alasan golf. Spesifikasi di atas dapat disajikan kembali secara terbalik, tetapi kemudian tidak akan cocok dengan kode yang digunakan dalam implementasi, jadi saya tidak menggambarkannya seperti itu.
EDIT: Program pertama yang menunjukkan pertumbuhan tanpa batas sederhana adalah 14283, yang menurunkan nilai pada lokasi memori 6 dan menulis 0 secara eksplisit (sebagai lawan dari 0 implisit dalam setiap sel) ke sel negatif berikutnya, setiap tiga kutu.
sumber
Tag Bitwise Cyclic dalam CJam,
98878477 byteKarena ini adalah infinite loop, Anda tidak dapat langsung menguji ini dalam juru bahasa online. Namun, berikut ini adalah versi alternatif yang membaca jumlah iterasi dari STDIN untuk Anda mainkan. Untuk menguji program lengkapnya, Anda memerlukan penerjemah Java .
BCT adalah varian minimalis dari Cyclic Tag Systems . Suatu program didefinisikan oleh dua string biner: daftar instruksi (cyclic) dan status awal. Untuk membuat hidup saya lebih mudah saat mencetak program, saya telah menetapkan notasi saya sendiri: masing-masing string diberikan sebagai array integer gaya CJam, dan seluruh program dikelilingi
[[...]]
, misalnyaSaya juga tidak mengizinkan status awal kosong atau daftar instruksi kosong.
Instruksi dalam BCT ditafsirkan sebagai berikut:
0
, hapus bit terkemuka dari keadaan saat ini.1
, baca bit lain dari daftar instruksi, panggil ituX
. Jika bit terkemuka dari kondisi saat ini adalah1
, tambahkanX
ke kondisi saat ini, jika tidak lakukan apa-apa.Jika keadaan saat ini menjadi kosong, program terhenti.
Beberapa program penghentian pertama adalah
Jika Anda ingin melihat lebih banyak, lihat versi di penerjemah online yang saya tautkan di atas.
Penjelasan
Berikut adalah cara kerjanya. Untuk melacak dovetailing kami akan selalu memiliki array pada stack yang berisi semua program. Setiap program adalah pasangan representasi internal dari kode program (seperti
[[0 1 0] [1 0]]
) serta keadaan program saat ini. Kami hanya akan menggunakan yang terakhir untuk melakukan perhitungan, tetapi kami harus mengingat yang pertama untuk mencetak program setelah terhenti. Daftar program ini hanya diinisialisasi ke array kosong denganL
.Sisa kode adalah loop tak terbatas
{...1}g
yang pertama kali menambahkan satu atau lebih program ke daftar ini dan menghitung satu langkah pada setiap program. Program yang berhenti dicetak dan dihapus dari daftar.Saya menghitung program dengan menghitung angka biner. Digit terkemuka dibuka untuk memastikan bahwa kita bisa mendapatkan semua program dengan 0s juga. Untuk setiap representasi biner terpotong seperti itu, saya mendorong satu program untuk setiap kemungkinan pemisahan antara instruksi dan keadaan awal. Misalnya jika penghitung saat ini di
42
, representasi binernya adalah101010
. Kami menyingkirkan yang terdepan1
dan mendorong semua benda yang tidak kosong:Karena kami tidak ingin instruksi atau status kosong, kami memulai penghitung di 4, yang memberi
[[[0] [0]]]
. Penghitungan ini dilakukan dengan kode berikut:Sisa kode memetakan blok ke daftar program, yang melakukan satu langkah perhitungan BCT pada bagian kedua dari pasangan ini dan menghapus program jika terhenti:
sumber
Brainfuck dengan Python, 567 byte
Solusi yang relatif sederhana, karena Brainfuck bukanlah bahasa yang paling sulit untuk dituliskan seorang penerjemah.
Implementasi Brainfuck ini memiliki penunjuk data mulai dari 0, hanya diizinkan untuk mengambil nilai positif (dianggap sebagai kesalahan jika mencoba untuk pergi ke kiri 0). Sel-sel data dapat mengambil nilai dari 0 hingga 255 dan membungkus. 5 instruksi yang valid adalah
><+[]
(-
tidak perlu karena pembungkusnya).Saya pikir hasilnya sudah benar sekarang, tetapi sulit untuk memastikan bahwa itu mencetak setiap solusi yang mungkin jadi saya mungkin kehilangan beberapa.
Beberapa ouputs pertama:
Dan daftar 2000 pertama: http://pastebin.com/KQG8PVJn
Dan akhirnya daftar 2000 output pertama dengan
[]
mereka: http://pastebin.com/iHWwJprs(semua sisanya sepele selama mereka valid)
Perhatikan bahwa output tidak dalam urutan, meskipun mungkin terlihat seperti itu bagi banyak dari mereka, karena program yang membutuhkan waktu lebih lama akan dicetak nanti.
sumber
[-]
dan[+]
pasti akan muncul karena isi dari loop hanya dilewati (tidak ada pembungkus yang terlibat).[-]
dan[+]
merupakan bug yang sekarang harus diperbaiki dan saya telah memperbarui dengan pengaturan.
? Ini tidak perlu untuk subset Turing-complete dari BF dan output harus diabaikan. Juga, karena Anda membungkus nilai sel sekitar, saya pikir Anda hanya perlu satu-
dan+
.garis miring dalam Python,
640498 bytehttps://esolangs.org/wiki////
Program garis miring adalah string, dalam interpreter ini terbatas pada karakter '/' dan '\'. Dalam implementasi ini, / adalah '1' dan \ adalah '0' untuk memungkinkan bermain golf dengan menggunakan bin python (x). Ketika interpreter menemukan a \, karakter berikutnya adalah output dan kedua karakter dihapus. Ketika bertemu a /, ia mencari dan mengganti pola sebagai / search / replace / termasuk karakter yang lolos dalam pola (\\ mewakili \ dan \ / mewakili /). Operasi penggantian itu kemudian dilakukan pada string berulang kali hingga string pencarian tidak lagi ada, kemudian interpretasi berlanjut dari awal lagi. Program berhenti ketika kosong. Suatu program akan terbunuh jika ada set / pola yang tidak tertutup atau \ tanpa karakter setelahnya.
sumber
Treehugger di Jawa,
1.2991.2571.2511.2071.2031.2011.1931.189 bytesumber
Brachylog → Posting masalah korespondensi , 10 byte
Cobalah online!
Fungsi yang merupakan generator yang menghasilkan semua masalah korespondensi Post yang mungkin dimana solusi brute-force akhirnya berhenti. (Solusi brute-forcing untuk masalah korespondensi Post dikenal sebagai operasi Turing-complete.) TIO link berisi header yang mengubah generator ke program penuh, dan mencetak setiap output segera seperti yang dihasilkan (dengan demikian, ketika TIO membunuh program karena memakan lebih dari 60 detik waktu eksekusi, output yang dihasilkan sejauh ini terlihat).
Ini menggunakan perumusan masalah di mana string diberikan sebagai string digit, nol terkemuka tidak diizinkan kecuali untuk
0
dirinya sendiri, solusi untuk masalah yang melibatkan nol terkemuka tidak diterima, dan serangkaian digit dapat diwakili sebagai salah satu nomor , atau minus angkanya. Jelas, tidak ada yang memiliki dampak pada kelengkapan Turing bahasa (karena tidak perlu masalah korespondensi Post untuk menggunakan angka nol sama sekali).Program ini bekerja melalui menghasilkan semua solusi yang mungkin untuk masalah, kemudian bekerja mundur untuk menemukan program asli yang diselesaikan oleh mereka. Dengan demikian, sebuah program individual dapat di-output berkali-kali. Tidak jelas apakah ini membatalkan jawaban atau tidak; Perhatikan bahwa semua program penghentian pada akhirnya akan menghasilkan setidaknya satu kali (pada kenyataannya, berkali-kali tak terhingga, karena setiap program yang memiliki solusi memiliki banyak solusi tak terhingga), dan program yang tidak berhenti akan pernah menjadi keluaran.
Penjelasan
sumber
"Ungu tanpa I / O" di Ceylon, 662
Ungu adalah bahasa satu instruksi yang memodifikasi sendiri yang diminta untuk menerjemahkan di sini . Sebagai input dan output tidak relevan untuk tugas ini, saya dihapus
o
arti simbol itu dari penafsir, sehingga (berpotensi) simbol berlaku hanyaa
,b
,A
,B
,i
dan1
(yang terakhir hanya untuk membaca, bukan untuk menulis).Tetapi karena Ungu memodifikasi sendiri (dan menggunakan kode sumbernya sebagai data), berpotensi juga program-program yang mengandung selain karakter-karakter itu berguna, jadi saya memilih untuk mengizinkan semua karakter ASCII yang dapat dicetak (bukan spasi) dalam kode (yang lain mungkin berguna juga, tetapi tidak mudah dicetak).
(Anda dapat memodifikasi penerjemah untuk alih-alih mengambil string karakter yang diizinkan sebagai argumen baris perintah - alihkan baris komentar yang dijelaskan di
a
bawah. Kemudian panjangnya menjadi 686 byte.)Dengan demikian, penerjemah "paralel" saya menciptakan semua string hingga dari karakter-karakter tersebut (dengan panjang yang semakin panjang dan urutan leksikografis) dan mencoba masing-masingnya.
Ungu akan berhenti tanpa kesalahan setiap kali perintah untuk dibaca dari rekaman untuk eksekusi tidak valid - sehingga tidak ada program yang tidak valid dan banyak, banyak yang berhenti. (Sebagian besar berhenti bahkan pada langkah pertama, hanya beberapa program dengan panjang 3 datang ke langkah kedua (dan akan berhenti kemudian), yang non-berhenti pertama memiliki panjang 6.
Saya pikir program non-halting pertama dalam urutan yang dicoba oleh penerjemah saya adalah
aaaiaa
, yang pada langkah pertama menetapkana
register ke 0 (yang sudah ada), dan langkah kedua dan setiap langkah berikutnya mengatur penunjuk instruksi kembali ke 0, menyebabkannya dieksekusiiaa
lagi.Saya menggunakan kembali bagian dari kode yang ditulis untuk penerjemah ungu "standar" saya , tetapi karena penghapusan input dan output, penerjemah paralel saya menjadi sedikit lebih pendek dari itu, sementara termasuk logika tambahan untuk menjalankan beberapa program sekaligus.
Ini adalah versi yang diomentari dan diformat:
sumber
Kalkulus kombinator SK di Haskell , 249 byte
Cobalah online!
Bagaimana itu bekerja
Aturan evaluasi panggilan demi nilai untuk kalkulus kombinator SK adalah sebagai berikut:
(a) S xyz ↦ xz ( yz ), untuk x , y , z dalam bentuk normal;
(B) K xy ↦ x , untuk x , y dalam bentuk normal;
(c) xy ↦ x ′ y , jika x ↦ x ′;
(d) xy ↦ xy ′, untuk x dalam bentuk normal, jika y ↦ y ′ .
Karena kami hanya tertarik untuk menghentikan perilaku, kami memperluas bahasa sedikit dengan memperkenalkan simbol H yang tidak dalam bentuk normal, tetapi semua bentuk normal "mengevaluasi":
(a) S xyz ↦ xz ( yz ), untuk x , y , z dalam bentuk normal;
(B ′) K x H ↦ x , untuk x dalam bentuk normal;
(c) xy ↦ x ′ y , jika x ↦ x ′;
(d) xy ↦ xy ′, untuk x dalam bentuk normal, jika y ↦ y ′ ;
(e) S ↦ H;
(f) K ↦ H;
(g) SH ↦ H;
(h) KH ↦ H;
(i) SHH ↦ H.
Kami menganggap setiap aplikasi H x menjadi kesalahan run-time untuk diperlakukan seolah-olah itu loop tak terbatas, dan kami memesan evaluasi sehingga tidak ada H diproduksi oleh (e) - (i) kecuali dalam konteks di mana ia akan diabaikan (tingkat atas, setiap K x ☐, setiap diabaikan K☐, setiap diabaikan S x ☐ untuk x dalam bentuk normal, setiap diabaikan S☐H). Dengan cara ini kami tidak memengaruhi perilaku berhenti dari istilah biasa yang kekurangan H.
Manfaat dari aturan-aturan yang dimodifikasi ini adalah bahwa setiap istilah yang dapat dinormalisasi memiliki jalur evaluasi unik ke H, dan bahwa setiap istilah memiliki jumlah terbatas kemungkinan preimage di bawah under. Jadi, alih-alih menggunakan pendekatan dovetailing, kita dapat melakukan pencarian pertama yang jauh lebih efisien dari semua jalur evaluasi terbalik dari H.
n
memeriksa apakah suatu istilah dalam bentuk normal,f
menemukan semua kemungkinan preimage dari suatu istilah, danl
merupakan daftar malas dari istilah-istilah yang dapat dinormalisasi yang dihasilkan oleh pencarian pertama yang luas dari H.sumber