Напишите брейкфук-программу длиной не более 256 символов, которая делает столько шагов, сколько возможно, но не зацикливается бесконечно. Программа может не принимать никаких входных данных.
Более конкретно:
- Предположим, бесконечное количество клеток справа.
- А
<когда в самой левой ячейке ничего не происходит. -Значение , когда клетка является нуль - множества клеток , чтобы255.- Все инструкции
+-<>.учитываются как один шаг при выполнении. - Когда встречается
[или], это считается одним шагом. Однако, если условие истинно и поток управления скачет, соответствующий]или[больше не засчитывается как шаг. - Решение, которое принимает большинство шагов, побеждает.
- Если в вашем решении есть какой-то шаблон, предоставление функции для определения количества шагов, которые
nдолжна выполнить подобная программа длины , приветствуется, но не является обязательным. - Для подсчета инструкций вы можете использовать этот модифицированный интерпретатор :
Пример:
++[-]
Появились инструкции ++[-]-], и программа запустилась за 7 шагов.
code-challenge
brainfuck
busy-beaver
Антон Голов
источник
источник
floatилиdoubleпримитивы, используемые для обычных повседневных вычислений. (В этот момент компьютер в основном просто манипулирует строками, представляющими уравнение)Ответы:
Вот 41-символьная программа, которая в итоге останавливается, оставляя более 10 ↑ (10 ↑ 28) смежных ячеек равными 1 (таким образом, количество выполняемых инструкций намного больше, чем это):
Если я не ошибаюсь, это правильный перевод следующей программы на языке BF-варианта, который использует один бит для каждой ячейки памяти (т. Е. Содержимое ячейки 0..1 вместо 0..255, поэтому '+' действует просто чтобы перевернуть битовое значение):
Точное значение (количество смежных 1-бит), полученное последней программой, равно
Вышеприведенная программа инициализирует и вычисляет функцию, которая растет как 2 x (в нотации Кнута со стрелкой вверх ). Аналогичное преобразование программы варианта BF, которая инициализирует и вычисляет функцию, которая растет как 2 × 23 x, обеспечивает следующую программу из 256 символов:
который в конечном итоге останавливается, оставляя более 2 23 6 соседних ячеек, установленных равными 1 (таким образом, количество шагов значительно больше).
NB-1 : 2 23 6 - «невероятно большое» число; например, даже 2 4 6 = 2 6 уже превосходит первый член (3 3) в последовательности, используемой для вычисления числа Грэма .
NB-2 : Я думаю, что для BF-программы достаточно 256 символов, чтобы инициализировать и вычислить функцию с выходом, намного превышающим число Грэма - если я найду время, возможно, я попытаюсь написать один.
NB-3 : В случае, если кто-то заинтересован в происхождении вышеперечисленных программ, вот некоторые ресурсы по программированию для "Brainf * ck F" , с различными программами, написанными на Python. («Brainf * ck F», или просто «F», это то, что я назвал полным по Тьюрингу вариантом Smallol * ck esolanguage.) Я только сейчас загрузил эти файлы, которые были отключены в течение нескольких лет, и на данный момент связанная веб-страница представляет собой просто «картотеку» - подробное обсуждение соответствующих программ приведено в файле Busy_Beavers.txt.
источник
Вот хороший 39 символов один:
Это в основном делает 3 саней шириной, что движется вправо и уменьшается на единицу. Выполнено 31 919 535 558 инструкций, причем самый внутренний цикл выполняется 256 ^ 3 раза. У меня все еще есть достаточно места, чтобы расширить это довольно далеко со скоростью 14 символов до другого порядка во время выполнения.
Работает на любом интерпретаторе с неограниченной памятью или с упаковочной памятью.
Я оставляю читателю упражнение, чтобы определить, когда закончится улучшенная версия с 2 циклами:
Это теперь бежало быстро, и это - больше чем 3 000 000 000 шагов. До сих пор не прошел ни одной итерации внешнего цикла. Только сделал это через 15% второго цикла.
источник
Эта программа работает в бесконечном количестве клеток. Два значения инициализируются в начале значениями ascii 255. Первое значение при первом повороте основного цикла разделяется на ячейку 255, и они инициализируются с 255 каждым, при втором повороте основного цикла каждое значение в 255 ячейках снова разделяется до 255 * 255 ячеек, таким же образом для вращения 255 основного цикла общее число инициализированных ячеек будет 255 ^ 255. Второе значение определяет, сколько раз должен повторяться основной цикл.
источник
Эта программа почти такая же, как и в моей предыдущей программе, отличие состоит в том, что значение, определяющее внешний цикл, остается фиксированным в конкретной ячейке, поэтому можно увеличить как количество инициализированных ячеек, так и общее количество шагов в конце программы.
ячейки инициализируются в конце программы 255 ^ 255
ячейки инициализируются в конце программы 255 ^ 255 ^ 3
Кроме того, я изменил его, чтобы запустить еще большее количество шагов.
он инициализирует 255 ^ 255 ячеек во время первого вращения основных 255 ^ (255 ^ 255 * 255) ячеек во время второго вращения основного цикла 255 ^ {255 ^ (255 ^ 255 * 255) * 255} ячеек во время третьего вращения основного цикла в этот цикл повторяется 255 раз
источник