Zajęty bóbr mózgu

Napisz program do pieprzenia mózgu o długości nie większej niż 256 znaków, który wykonuje tyle kroków, ile to możliwe, ale nie zapętla się w nieskończoność. Program nie może przyjmować żadnych danych wejściowych.

Dokładniej:

• Załóż nieskończoną liczbę komórek po prawej stronie.
• A <kiedy komórka po lewej stronie nic nie robi.
• -Gdy wartość komórki wynosi zero zestawy do komórek 255.
• Wszystkie instrukcje +-<>.liczone są jako jeden krok po ich wykonaniu.
• Gdy napotkasz a [lub ], liczy się to jako jeden krok. Jeśli jednak warunek jest spełniony, a przepływ sterowania przeskakuje, odpowiadający ]lub [nie jest ponownie liczony jako krok.
• Rozwiązanie, które wykonuje najwięcej kroków, wygrywa.
• Jeśli w twoim rozwiązaniu jest jakiś wzorzec, podanie funkcji określającej liczbę kroków podobnego programu długości njest mile widziane, ale nie jest obowiązkowe.
• Aby policzyć instrukcje, możesz użyć tego zmodyfikowanego interpretera :

Przykład:

++[-]

Napotkano instrukcje ++[-]-], a program działał przez 7 kroków.

Oto 41-znakowy program, który ostatecznie zatrzymuje się, pozostawiając więcej niż 10 ↑ (10 ↑ 28) ciągłych komórek ustawionych na 1 (więc liczba wykonanych instrukcji jest znacznie większa):

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

Jeśli się nie mylę, jest to poprawne tłumaczenie następującego programu w języku BF, który używa jednego bitu dla każdej komórki pamięci (tj. Zawartości komórki 0..1 zamiast 0..255, więc „+” działa po prostu odwracając wartość bitową):

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

Dokładna wartość (liczba sąsiadujących 1-bitów) wygenerowana przez ten ostatni program to

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

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

co ostatecznie zatrzymuje się, pozostawiając więcej niż 2 ↑ ²³ 6 sąsiednich komórek ustawionych na 1 (więc liczba kroków jest znacznie większa).

NB-1 : 2 ↑ ²³ 6 jest „niewyobrażalnie dużą” liczbą; np. nawet 2 ↑ ⁴ 6 = 2 ↑↑↑↑ 6 już przekracza pierwszy wyraz (3 ↑↑↑↑ 3) w sekwencji użytej do obliczenia liczby Grahama .

NB-2 : Myślę, że prawdopodobnie 256 znaków wystarcza, aby program BF zainicjował i obliczył funkcję o wyjściu znacznie większym niż liczba Grahama - jeśli znajdę czas, może spróbuję napisać jeden.

NB-3 : Jeśli ktoś jest zainteresowany pochodzeniem powyższych programów, oto niektóre zasoby programistyczne dla „Brainf * ck F” , z różnymi programami napisanymi w Pythonie. („Brainf * ck F” lub po prostu „F” to tak zwany kompletny wariant Turinga esolanguage Smallf * ck .) Właśnie przesłałem te pliki, które były nieaktywne od kilku lat, a na razie połączona strona internetowa to tylko „szafka na pliki” - szczegółowe informacje dotyczące powyższych programów można znaleźć w pliku Busy_Beavers.txt.

Oto ładny 39 postaci:

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

Zasadniczo tworzy 3-przestrzeniowy „sanie”, które porusza się w prawo i zmniejsza o jeden. Ukończono 31 919 535 558 instrukcji, przy czym wewnętrzna pętla wykonała 256 ^ 3 razy. Wciąż mam dużo miejsca, aby rozszerzyć to dość daleko w tempie 14 znaków do innego rzędu wielkości w stosunku do czasu działania.

Działa na dowolnym tłumaczu z niepowiązaną pamięcią lub z opakowaniem pamięci.

Zostawiam to ćwiczenie czytelnikowi, aby ustalić, kiedy zakończy się ulepszona wersja z 2 pętlami:

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

Teraz działa przez noc i ma ponad 3 miliony milionów kroków. Nadal nie przeszedł ani jednej iteracji zewnętrznej pętli. Zaledwie przeszedł przez 15% drugiej pętli.

Ten program działa w nieskończonej liczbie komórek. Początkowo dwie wartości są inicjalizowane wartościami ascii 255. Pierwsza wartość przy pierwszym obrocie głównej pętli jest podzielona na 255 komórek i są one inicjalizowane po 255 każda, przy drugim obrocie głównej pętli każda wartość w 255 komórkach ponownie się dzieli do 255 * 255 komórek, w ten sam sposób dla 255 obrotów głównej pętli całkowita zainicjowana liczba komórek będzie wynosić 255 ^ 255. Druga wartość określa, ile razy główna pętla ma być powtarzana.

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

Ten program jest prawie taki sam jak mój poprzedni program, różnica polega na tym, że wartość określająca pętlę zewnętrzną pozostaje stała w określonej komórce, dzięki czemu można zwiększyć zarówno liczbę zainicjowanych komórek, jak i całkowitą liczbę kroków na końcu programu

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

komórki zainicjowane na końcu programu 255 ^ 255

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

komórki zainicjowane na końcu programu 255 ^ 255 ^ 3

Następnie zmodyfikowałem go, aby działał jeszcze z większą liczbą kroków.

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

inicjuje 255 ^ 255 komórek podczas pierwszego obrotu głównej 255 ^ (255 ^ 255 * 255) komórek podczas drugiego obrotu głównej pętli 255 ^ {255 ^ (255 ^ 255 * 255) * 255} komórek podczas trzeciego obrotu głównej pętli w ten sposób pętla powtarza się 255 razy