Traceless Busy Beaver

20

Все эти занятые бобры устроили беспорядок. Они написали по всей ленте. В таком случае наш сосед перестанет одалживать нам неограниченные ленты.

Нам нужен новый способ играть в игру занятого бобра, который не разрушает каждую используемую нами ленту.

Правила

Только Brainfuck. Лента памяти неограничена в обоих направлениях. Инструкция ввода всегда будет читать , поэтому ее можно использовать для очистки значения.0

Ограничение в 50 байтов.

В конце выполнения память должна быть все с.0

Оценка - это расстояние между начальным положением указателя памяти и конечным положением - если для перемещения между ними требуется инструкций перемещения, ваш результат равен . Чем выше, тем лучше. Укажите точное значение, если можете, в противном случае предоставьте оценку.нnn

пример

32 байта,22551

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

объяснение

-                                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.

Начнем со списка . На каждой итерации мы используем значение слева от списка, а если , мы добавляем справа. Числа, добавленные , ниже, чем исходные , поэтому они будут уменьшаться до тех пор, пока не станут , после чего они расходуются без расширения. Таким образом, процесс заканчивается в конце концов, все с в памяти. Однако на каждом шаге количество копий этого номера удваивается. Оценка этой программы, инициализированной списком составляет .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

Этот пример предназначен для демонстрации некоторых методов, используемых при создании представления. Это не конкурентоспособно для его размера.

EPICI
источник
3
@ Ок, нет проблем - это не было задумано как критика. Если есть другой способ подсчитать это, что позволяет использовать произвольную длину кода, сейчас самое время найти ее до того, как придут ответы. Я собираюсь пометить это, так как в настоящее время тег гольфа кода вводит в заблуждение
trichoplax
3
Должен быть некоторый предел, так как большее количество байтов позволяет определить более быстро растущую функцию. Нет особой причины для 50, он выглядит достаточно высоким для некоторого приличного роста (определенно лучше, чем экспоненциальный мой пример) и творческих решений, но все еще слишком мал для червя Беклемишева или другого чрезвычайно быстрого роста. // Кстати, спасибо за исправление моих тегов, я немного поторопился с этим.
EPICI
2
Просто для справки: мы стараемся избегать минимальных оценок для кода гольфа , но эта задача не является кодом гольфа, а количество байтов не является результатом, поэтому я не вижу абсолютно никаких проблем с ограничением в 50 байтов в этом случае.
Трихоплакс
1
Информация: я думаю, что могу «тривиально перенести» этот ответ из другого вызова и получить аналогичный результат.
user202729
1
@EPICI Мой предыдущий занятый бобер уже был бесследным, поэтому я пытался его адаптировать.
Джо Кинг,

Ответы:

10

Оценка:A(255,2)1=(22535)4

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

A ( м , н ) A ( м , н )A вот формулировка Петера-Аккермана для функции Аккермана , в то время как в другом выражении оценки используется нотация со стрелкой вверх Кнута. 35-байтовый основной цикл [-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<]можно использовать для вычисления , поместив на ленту значения и войдя в цикл с указателем на ячейку. После завершения цикла ненулевое содержимое ленты - это , начиная сразу справа от указателя.A(m,n)1 - m, m, 1 <n times>mA(m,n)

Я использовал следующую программу на Python для моделирования поведения программы:

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
источник
1
Вы можете увеличить свой счет, добавив трейлинг >.
Джонатан Фрех
вау, очень впечатляет
alan2 здесь