Harap dicatat: Sesuai sifatnya, spesifikasi untuk tantangan ini sulit dipahami. Mungkin memerlukan setidaknya kursus baru dalam teori komputasi, atau membaca latar belakang yang setara. Selain itu, tantangannya sendiri agak sulit. Menjawabnya akan membutuhkan penulisan seluruh juru bahasa untuk beberapa bagian dari bahasa pilihan Anda, dan tidak hanya itu tetapi penerjemah harus dalam bentuk sesuatu seperti quine. Jika jawaban Anda tidak melakukan semua ini, hampir pasti tidak akan memenuhi spesifikasi.
Anda tidak perlu menyelesaikan masalah penghentian (bahkan sebagian) untuk menyelesaikan tantangan ini. Namun, Anda hampir pasti lakukan perlu menulis penerjemah (dari bahasa yang Anda gunakan, ditulis dalam bahasa yang sama menafsirkan), meskipun tidak perlu fitur yang lengkap. Inilah yang membuat ini tantangan yang menarik.
Saya berjanji akan memberikan hadiah 500 poin untuk jawaban pertama yang memenuhi spesifikasi, dan ini akan diberikan kepada jawaban BF King BF .
Tantangan
Versi kasar, versi sederhana dari bukti Alan Turing tentang tidak terselesaikannya masalah terhenti adalah seperti ini:
Misalkan saya telah menulis sebuah program F
yang dimaksudkan untuk menyelesaikan program penghentian. Yaitu, F
mengambil kode sumber dari program lain sebagai input, dan F(G)
seharusnya kembali 1
jika G
berhenti, dan 0
sebaliknya.
Tetapi jika saya memberi Anda program saya F
maka Anda dapat membangun program lain H
,, yang menjalankan program saya dengan H
masukannya. Jika F(H)
kembali 0
maka H
kembali 0
, tetapi sebaliknya dengan sengaja masuk ke loop tak terbatas. Ini mengarah ke sebuah paradoks, dan kita harus menyimpulkan bahwa bagaimanapun F
juga tidak dapat menyelesaikan masalah penghentian.
Tugas Anda adalah menulis program H
, tetapi dengan twist: Saya tidak akan memberi Anda program saya. Sebaliknya, program Anda akan menerima kode sumber program saya sebagai input. Itu adalah:
Program Anda akan menerima program saya sebagai input, dalam bentuk kode sumber. (Misalnya sebagai file atau sebagai input baris perintah, detailnya terserah Anda.)
Program saya akan ditulis dalam bahasa yang sama dengan program Anda, dan juga mengambil input dalam bentuk string kode sumber.
Jika program saya kembali
0
ketika diberikan program Anda sebagai input, program Anda harus berhenti (dan kembali0
) ketika diberi program saya sebagai input. (Arti tepat dari "returing0
" terserah Anda.)jika program saya tidak berhenti, atau jika ia mengembalikan apa pun selain
0
ketika diberikan program Anda sebagai input, program Anda harus tetap berjalan tanpa batas.
Kelebihannya adalah, hanya untuk membuatnya sangat jauh lebih sulit, Anda harus mematuhi aturan berikut:
Anda tidak dapat menggunakan fungsi bawaan
exec
ataueval
jenis apa pun.Anda tidak dapat menggunakan metode "curang" apa pun untuk mendapatkan kode sumber program Anda sendiri. (Misalnya Anda tidak bisa mengatakan "simpan ini di file yang disebut 'program'" dan kemudian miliki
open(program)
di program Anda.)
Ini berarti bahwa program Anda harus menjadi semacam super-quine gila yang tidak hanya dapat mereproduksi kode sumbernya sendiri dalam bentuk string, tetapi juga mampu mengurai dan menafsirkan bahasa yang ditulis dengan benar.
Untuk membuatnya sedikit lebih sulit, Anda diperbolehkan menggunakan hanya sebagian (bahasa Turing) dari bahasa pilihan Anda. Jadi jika program Anda ditulis dalam Python dan hanya akan berfungsi jika program saya hanya berisi operasi if
s dan while
loop dan string dasar, maka itu boleh saja selama program Anda hanya menggunakan hal-hal itu juga. (Ini berarti Anda tidak perlu khawatir menerapkan seluruh perpustakaan standar bahasa yang Anda pilih!) Namun, program Anda harus benar-benar berjalan - Anda tidak bisa hanya membuat bahasa Anda sendiri.
Ini adalah kontes popularitas , jadi jawaban dengan suara terbanyak menang. Namun, seperti yang disebutkan di atas, itu adalah tantangan serius hanya untuk memenuhi spesifikasi sama sekali, jadi saya akan memberikan hadiah 500 poin untuk jawaban pertama yang menurut penilaian saya.
harap dicatat: tidak diragukan lagi ada banyak cara Anda dapat "menipu" pada tantangan ini, mengingat kata-kata persis yang saya gunakan. Namun, saya benar-benar berharap jawaban yang masuk ke dalam semangat pertanyaan. Tantangan sebagaimana dimaksud sangat sulit tetapi mungkin, dan saya benar-benar berharap untuk melihat solusi yang tulus untuk itu. Saya tidak akan menghadiahkan hadiah itu untuk jawaban yang terasa curang dalam penilaian saya.
Catatan: tantangan ini awalnya diposting sebagai kontes popularitas , tetapi ditutup pada tahun 2016 karena tidak memiliki "kriteria kemenangan yang objektif", dan saya mengubahnya menjadi golf kode untuk membuatnya dibuka kembali. Namun, saya telah menemukan bahwa, pada Januari 2018, popularitas-kontes sebenarnya tidak dilarang di PPCG (dengan ini menjadi diskusi meta terbaru) sehingga menutupnya di tempat pertama adalah bertentangan dengan kebijakan situs. Saya mengerti bahwa popcons tidak populer akhir-akhir ini, tetapi ini adalah tantangan lama, dan sifatnya membuatnya sangat tidak cocok untuk kode-golfsistem penilaian. Jika ada orang yang masih merasa bahwa itu tidak boleh diizinkan, mari kita bahas meta diskusi sebelum orang-orang dekat mulai dilemparkan. Akhirnya, jika seseorang menghabiskan tahun terakhir mencoba golf solusi mereka, yakinlah bahwa itu akan sama kompetitif dalam tantangan ini, dan sama layaknya dengan karunia, seperti yang akan ada dalam kode-golf versi.
sumber
F
ke dalam file danimport
ing itu? ; 3Jawaban:
brainfuck ,
601348774376 byteEdit: -1136 byte. Beralih ke cara yang lebih baik untuk menghasilkan data untuk quine
Sunting2: -501 byte. Tinjau kembali penerjemah mandiri saya dan kurangi beberapa ratus byte
Cobalah online! Input di sini adalah program kucing sederhana (
,[.,]
) yang akan mencetak program itu sendiri."Return 0" didefinisikan dengan mengakhiri program pada sel dengan nilai 0.
Kombinasi yang tidak suci dari dua program yang telah saya tulis sebelumnya, quine dan interpreter mandiri. Bagian pertama adalah bagian quine, yang mengambil data dan mengisi rekaman dengan generasi data yang diikuti oleh kode sumber. Berikutnya adalah self-interpreter, yang mengambil program Anda dan menjalankannya. Ini adalah salinan yang tidak berubah dari self interpreter normal, kecuali bahwa alih-alih mengambil input secara langsung, itu mendapat input dari awal bagian data, mengatur sel ke 0 jika tidak ada lagi input. Akhirnya, akhiri di sel saat ini dari program Anda dan jalankan
[]
. Jika nilai yang dikembalikan adalah 0, program saya akan berakhir pada nol. Jika ada hal lain, itu akan menjalankan loop tak terbatas. Jika program Anda berjalan selamanya,program saya akan berjalan selamanya.Bagaimana itu bekerja:
Bagian 1: Pembuatan Data
Bagian ini merupakan bagian data quine, dan sejauh ini merupakan mayoritas kode pada 3270 byte. Awal
-
adalah penanda untuk awal data. Masing-masing>+++
mewakili karakter kode setelah bagian ini.Bagian 2: Hasilkan bagian data menggunakan data
Ini menggunakan data dari bagian satu untuk menambahkan karakter yang digunakan untuk menghasilkan data ke bagian kode. Ini menambahkan
>
bagian akhir kode dan nilai banyak nilai sel itu.Bagian 3: Hasilkan sisa kode menggunakan data
Hancurkan bagian data dan tambahkan sisa kode sumber ke bagian kode
Bagian 4: Dapatkan program yang dimasukkan
Mendapat program yang dimasukkan. Menghapus karakter non-brainfuck dan mewakili setiap karakter dengan angka:
Merupakan akhir dari program dengan
255
.Bagian 5: Menafsirkan input
Menafsirkan program. Satu-satunya perbedaan dari yang normal adalah bahwa input diambil dari awal bagian kode daripada input.
Bagian 6: Hentikan jika pengembalian bukan 0
Arahkan ke sel akhir dari program Anda dan jalankan infinite loop jika pengembaliannya tidak 0. Jika 0, keluar dari loop dan akhiri pada 0 yang sama.
Input Tes:
Selalu mengembalikan 0 (berhenti dan kembali 0)
Selalu mengembalikan 1 (berjalan selamanya)
Mengembalikan semua input yang ditambahkan bersama-sama, mod 256 (mengembalikan 211, sehingga berjalan selamanya)
Mengembalikan 0 jika dua karakter terakhir dari sebuah kode adalah infinite loop (
[]
) ( program Anda mengembalikan 0 ketika diberi program saya , karena itu program saya berhenti)Fakta Menarik bagi mereka yang masih membaca
Jika input untuk program ini adalah kode sumber program ini, maka program itu akan mulai berulang, berulang kali membuat self-interpreter yang menjalankan program ini dan kemudian memberikannya program yang sama lagi. Ini memberi saya beberapa ide menarik untuk membuat program rekursif aktual di brainfuck. Alih-alih memeriksa nilai kembali dan memulai infinite loop seperti dalam pertanyaan ini, nilai kembali dapat disimpan dan ditindaklanjuti. Contoh sederhana akan menjadi program faktorial yang berjalan
Tentu saja, ini adalah cara pengodean brainfuck yang benar-benar gila, mengingat bahwa menjalankan self-interpreter yang berulang akan meningkatkan runtime secara eksponensial.
sumber
.
. Meskipun karena ini bukan lagi pertanyaan kode-golf, mendukung seluruh bahasa mungkin lebih mengesankan.