Brain Beaver yang sibuk

13

Tulis program brainfuck yang tidak lebih dari 256 karakter yang mengambil langkah sebanyak mungkin, tetapi tidak berulang tanpa henti. Program tidak boleh mengambil input apa pun.

Lebih spesifik:

  • Asumsikan jumlah sel tak terbatas di sebelah kanan.
  • Suatu <ketika di sel paling kiri tidak melakukan apa-apa.
  • A -saat nilai sel nol setel menjadi 255.
  • Instruksi +-<>.semua dihitung sebagai satu langkah saat dijalankan.
  • Ketika a [atau ]ditemui, itu dihitung sebagai satu langkah. Namun, jika kondisi benar dan kontrol aliran melompat, yang sesuai ]atau [tidak tidak lagi dihitung sebagai langkah.
  • Solusi yang mengambil langkah terbanyak akan menang.
  • Jika ada semacam pola dalam solusi Anda, memberikan fungsi untuk berapa langkah langkah yang sama dengan program panjang nakan dihargai tetapi tidak wajib.
  • Untuk menghitung instruksi, Anda dapat menggunakan penerjemah yang dimodifikasi ini :

Contoh:

++[-]

Instruksi yang ditemui adalah ++[-]-], dan program berjalan selama 7 langkah.

Anton Golov
sumber
6
Saya akan terkejut jika pemenangnya berakhir tanpa membanjiri jumlah penerjemah. Ingatlah bahwa berang-berang TM sibuk 6-negara mengambil setidaknya 10 ** 36534 langkah.
Peter Taylor
Saya setuju. Tampaknya sangat mungkin Anda bisa menulis program <50 char BF yang dapat berjalan selama bertahun-tahun. Saya akan mulai.
captncraig
Tertanda. Halaman penelitian Busy Beaver di drb.insel.de/~heiner/BB sangat menarik, terutama kenyataan bahwa program rekaman berjalan sangat lama dan mereka masih memiliki hasil yang tepat (lihat drb.insel.de/~heiner/BB/bb -xlist.txt ) - simulasi mengingat status, buat "makro" untuk menyimpan langkah simulasi, dll.
schnaader
4
@AntonGolov: sayangnya, di alam semesta ini, RAM dan HD tidak dikonversi ke perangkat penyimpanan tanpa batas ketika Anda mencoba untuk menyimpan bignum yang lebih besar dari 256 ^ ukuran dalam byte pada mereka ...
berhenti mengubah counterclockwis
1
@ boothby Sangat mungkin untuk melakukan perhitungan tepat yang melibatkan transendental pada komputer saat ini. Komponen nilai hanya harus disimpan dalam representasi yang lebih abstrak daripada yang normal floatatau doubleprimitif yang digunakan untuk komputasi sehari-hari umum. (Pada saat itu komputer sebagian besar hanya memanipulasi string yang mewakili persamaan)
AJMansfield

Jawaban:

15

Berikut adalah program 41 karakter yang pada akhirnya berhenti, menyisakan lebih dari 10 ↑ (10) 28) sel-sel yang berdekatan ditetapkan sama dengan 1 (sehingga jumlah instruksi yang dieksekusi jauh lebih besar dari itu):

>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

Jika saya tidak salah, itu adalah terjemahan yang benar dari program berikut dalam bahasa BF-varian yang menggunakan bit tunggal untuk setiap sel memori (yaitu, konten sel 0..1 bukannya 0..255, jadi '+' bertindak untuk membalik nilai bit):

>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

Nilai persisnya (jumlah 1-bit yang berdekatan) yang dihasilkan oleh program yang terakhir adalah

3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.


Program di atas menginisialisasi & menghitung fungsi yang tumbuh seperti 2 ↑↑ x (dalam notasi panah atas Knuth ). Konversi serupa dari program varian-BF yang menginisialisasi & menghitung fungsi yang tumbuh seperti 2 ↑ 23 x menyediakan program 256-karakter berikut:

>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

yang akhirnya berhenti, meninggalkan lebih dari 2 ↑ 23 6 sel yang berdekatan ditetapkan sama dengan 1 (sehingga jumlah langkah jauh lebih dari itu).

NB-1 : 2 ↑ 23 6 adalah angka "sangat besar"; misalnya, bahkan 2 ↑ 4 6 = 2 ↑↑↑↑ 6 sudah melampaui suku pertama (3 ↑↑↑↑ 3) dalam urutan yang digunakan untuk menghitung nomor Graham .

NB-2 : Saya pikir kemungkinan 256 karakter sudah cukup untuk program BF untuk menginisialisasi & menghitung fungsi dengan output yang jauh lebih besar dari angka Graham - jika saya punya waktu, mungkin saya akan mencoba menulis satu.

NB-3 : Jika ada yang tertarik dengan asal-usul program di atas, berikut adalah beberapa sumber daya pemrograman untuk "Brainf * ck F" , dengan berbagai program yang ditulis dengan Python. ("Brainf * ck F", atau hanya "F", adalah apa yang saya sebut varian Turing-complete dari Smallf * ck esolanguage.) Saya baru saja mengunggah file-file ini, yang telah offline selama beberapa tahun, dan untuk saat ini halaman web yang ditautkan hanyalah "lemari arsip" - lihat file Busy_Beavers.txt untuk diskusi terperinci yang relevan dengan program-program di atas.

res
sumber
Ini adalah pemenang yang jelas saat ini (kecuali saya hanya meremehkan yang lain). Lebih banyak saran sangat diterima, tetapi saya akan menandainya sebagai diterima untuk saat ini. Jika ada yang tidak setuju, silakan lakukan komentar.
Anton Golov
Ketika Anda mencapai level ini, menjadi tidak realistis untuk menganggap Anda memiliki juru bahasa dengan memori tak terbatas. Saya mulai berpikir ini akan menjadi tantangan yang lebih baik dengan memori yang terbatas, sehingga kami benar-benar dapat menjalankan jawabannya.
captncraig
9

Ini adalah karakter 39 yang bagus:

-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

Ini pada dasarnya membuat 'kereta luncur' selebar 3 ruang yang bergerak ke kanan dan menurun satu per satu. Diselesaikan dalam 31.919.535.558 instruksi, dengan loop terdalam mengeksekusi 256 ^ 3 kali. Saya masih punya banyak ruang untuk memperpanjang ini cukup jauh dengan laju 14 karakter ke urutan besarnya hingga run time.

Bekerja pada penerjemah apa pun dengan memori tidak terbatas, atau dengan memori pembungkus.

Saya membiarkannya sebagai latihan bagi pembaca untuk menentukan kapan versi 2 loop yang ditingkatkan akan selesai:

-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

Sekarang telah berjalan semalam, dan ini lebih dari 3.000.000.000 langkah. Masih belum melewati satu iterasi dari loop luar. Baru berhasil melewati 15% dari putaran kedua.

captncraig
sumber
2

Program ini bekerja dalam jumlah sel yang sangat sedikit. Dua nilai diinisialisasi pada awal dengan nilai ascii 255. Nilai pertama pada rotasi pertama loop utama dibagi menjadi 255 sel dan mereka diinisialisasi dengan 255 masing-masing, pada rotasi kedua loop utama, setiap nilai dalam 255 sel lagi terbagi hingga 255 * 255 sel, dengan cara yang sama untuk 255 putaran loop utama total sel yang diinisialisasi akan 255 ^ 255. Nilai kedua menentukan berapa kali loop utama harus diulang.

>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]
Albert
sumber
2

Program ini hampir sama dengan program saya sebelumnya, perbedaannya adalah bahwa nilai menentukan loop luar tetap dalam sel tertentu sehingga jumlah sel yang diinisialisasi dan langkah-langkah total pada akhir program dapat ditingkatkan

->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

sel diinisialisasi pada akhir program 255 ^ 255

-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

sel diinisialisasi pada akhir program 255 ^ 255 ^ 3

Saya lebih lanjut memodifikasinya untuk menjalankan lebih banyak langkah.

->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

itu menginisialisasi 255 ^ 255 sel selama rotasi pertama sel 255 ^ (255 ^ 255 * 255) utama selama rotasi kedua loop utama 255 ^ {255 ^ (255 ^ 255 * 255) * 255} sel selama rotasi ketiga loop utama di loop cara ini berulang 255 kali

Albert
sumber
Tampak hebat! Maaf karena belum menerima jawaban - saya harus meluangkan waktu untuk melihat ini dan mencari tahu urutan pertumbuhan. Ketika Anda mengatakan "255 ^ 255 * 255", maksud Anda "255 ^ (255 * 255)"? (Saya harapkan "255 ^ 256" sebaliknya.)
Anton Golov