Traceless Busy Beaver

20

Wszystkie te zajęte bobry zrobiły niezły bałagan. Pisali po całej taśmie. Przy takim tempie nasz sąsiad przestanie pożyczać nam nieograniczone taśmy.

Potrzebujemy nowego sposobu gry w zajęty bóbr, który nie rujnuje każdej używanej taśmy.

Zasady

Tylko Brainfuck. Taśma pamięci jest nieograniczona na dwa sposoby. Instrukcja wejściowa zawsze będzie miała wartość , więc można jej użyć do skasowania wartości.0

Limit 50 bajtów źródła.

Pod koniec wykonywania pamięć musi wynosić s.0

Wynik to odległość między początkową lokalizacją wskaźnika pamięci a końcową lokalizacją - jeśli potrzeba instrukcji ruchu, aby przejść między nimi, twój wynik to . Wyżej jest lepiej. Podaj dokładną wartość, jeśli możesz, w przeciwnym razie podaj oszacowanie.nnn

Przykład

32 bajty,22551

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

Wyjaśnienie

-                                Initialize the list to [255].
 [                             ] Repeat as long as the list is not empty.
 [-                            ] Decrement the left end. We need to shrink the numbers so it ends eventually.
 [ [                         ] ] Skip if 0 already.
 [ [[>]                      ] ] Move to the cell past the right end.
 [ [   +                     ] ] Make this cell 1.
 [ [    >                    ] ] Go right again.
 [ [     +                   ] ] Make this cell 1. We've now appended [1, 1].
 [ [      [<]>               ] ] Go back to the first nonzero cell on the left.
 [ [          -              ] ] And decrement it.
 [ [           [            ]] ] We will need to transfer the rest of the number from the left to the right, so keep looping.
 [ [           [[>]<        ]] ] Go to the last nonzero cell on the right.
 [ [           [    +<+     ]] ] Increment this and the one on the left. These are the cells we appended earlier. We transfer to them.
 [ [           [       [<]> ]] ] Go back to the first nonzero cell on the left, which we are transferring from.
 [ [           [           -]] ] Decrement here on the left to balance out the incrementing on the right.
 [                            >] We end the iteration on a now empty cell. Move right, the new left end is there.

Zaczynamy od listy . Przy każdej iteracji konsumujemy wartość po lewej stronie listy, a jeśli , dodajemy po prawej stronie. Dołączone liczby są niższe niż oryginalne , więc będą się zmniejszać, dopóki nie osiągną , w którym to momencie są konsumowane bez rozwijania. Tak więc proces ostatecznie się kończy, a wszystkie s są w pamięci. Jednak na każdym kroku liczba kopii tej liczby podwaja się. Wynik tego programu zainicjowanego listą wynosi .n n > 1 [ n - 1 , n - 1 ] ( n - 1 ) ( n ) 1 0 [ n ] 2 n - 1[255]nn>1[n1,n1](n1)(n)10[n]2n1

Ten przykład ma na celu pokazanie niektórych technik używanych przy tworzeniu zgłoszenia. Nie jest konkurencyjny ze względu na swój rozmiar.

EPICI
źródło
3
@Okx nie ma problemu - to nie było zamierzone jako krytyka. Jeśli istnieje inny sposób na ocenę tego, który pozwala na dowolną długość kodu, nadszedł czas, aby go znaleźć, zanim pojawią się odpowiedzi. Zamienię to ponownie, ponieważ obecnie kod golfowy wprowadza w błąd
trichoplax
3
Musi istnieć pewien limit, ponieważ więcej bajtów pozwala zdefiniować szybciej rosnącą funkcję. Nie ma żadnego powodu, dla którego 50, wygląda wystarczająco wysoko, aby uzyskać przyzwoity wzrost (zdecydowanie lepszy niż wykładniczy mój przykład) i kreatywne rozwiązania, ale wciąż zbyt mały dla robaka Beklemisheva lub innego niezwykle szybkiego wzrostu. // Dzięki za naprawienie moich tagów, przyśpieszyłem to trochę.
EPICI,
2
Na przykład: staramy się unikać minimalnych wyników dla golfa kodowego , ale to wyzwanie nie jest golfem kodowym, a liczba bajtów nie jest wynikiem, więc nie widzę absolutnie żadnego problemu z limitem 50 bajtów w tym przypadku.
trichoplax
1
Informacje: Myślę, że mogę „trywialnie przenieść” tę odpowiedź z innego wyzwania i uzyskać podobny wynik.
user202729,
1
@EPICI Mój poprzedni zajęty bóbr był już bez śladu, dlatego starałem się go dostosować.
Jo King,

Odpowiedzi:

10

A(255,2)1=(22535)4

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

A ( m , n ) A ( m , n )A tutaj jest sformułowanie Pétera-Ackermanna funkcji Ackermanna , podczas gdy inne wyrażenie partytury używa notacji Knutha w górę. 35-bajtową główną pętlę [-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<]można wykorzystać do obliczenia poprzez umieszczenie na taśmie wartości i wprowadzenie pętli ze wskaźnikiem na komórce. Po zakończeniu pętli niezerową zawartością taśmy są zaczynające się bezpośrednio po prawej stronie wskaźnika.A(m,n)1 - m, m, 1 <n times>mA(m,n)

Użyłem następującego programu Python do modelowania zachowania programu:

def a(M, N):
    assert M > 0
    m = [-M + 1, M]
    n = N
    while m[-1]:
        while m[-1] > 1:
            m[-1] -= 1
            m[-2] += 1
            while n:
                m.insert(-1, 1)
                n -= 1
            n = 1
        n += 2
        m.pop()
    return n
feersum
źródło
1
Możesz zwiększyć swój wynik, dodając końcowy >.
Jonathan Frech,
wow, bardzo imponujące
alan2here