Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [busy-beaver]

A busy beaver maximises some property of the computation model (e.g. execution time, memory usage, output length) subject to the constraint that it must halt.

Filter by
Sorted by
Tagged with
12 votes
11 answers
2k views

Output two numbers (Robbers' thread)

This is the robbers' thread to a cops-and-robbers challenge. Click the link to find the cops' thread. In the cops' thread of this challenge, answerers will be writing programs which output two ...
user avatar
  • 85k
23 votes
20 answers
2k views

Output two numbers (Cops' thread)

This is the cops' thread to a cops-and-robbers challenge. Click the link to find the robbers' thread. The challenge here is very simple. Create two programs of the same size, in the same language, ...
user avatar
  • 85k
11 votes
1 answer
456 views

Longest infinite loop in 5 states

Challenge Statement The goal of this challenge is to build the 5 state Infinite Time Turing Machine that takes the longest to halt. Since Infinite Time Turing Machines can run for infinite time your ...
user avatar
  • 85k
0 votes
0 answers
139 views

Infinite-Time Busy Beaver

An infinite time Turing machine is a generalization of a Turing machine to infinite computation lengths. It has three tapes: two of them are blank initially, and the other one contains the input to ...
user avatar
  • 491
7 votes
1 answer
211 views

Busy beaver in a coin

\$BB\$ is the busy beaver function, an uncomputable function. Write a program which when given an integer \$n\$ as input, will output \$BB(n)\$, with at least \$\frac 2 3\$ probability. You can do ...
user avatar
  • 12.7k
18 votes
1 answer
645 views

Largest SKI output in less than 200 combinators

The Challenge Create an terminating expression in SKI Combinator Calculus in less than 200 combinators (S, K, I) that reduces to the expression with the most combinators. There will be no limit on how ...
user avatar
  • 703
-1 votes
2 answers
201 views

Challenge: create a large number using an esoteric programming language [duplicate]

I enjoy large numbers and esoteric programming language, so I decided to combine them into a programming challenge. Your goal is to push the limits of esoteric languages like BF or Pyth and return the ...
user avatar
  • 491
28 votes
11 answers
2k views

Infinite ordinals from a well-ordering

Your task is to write a short program that represents a large (infinite) ordinal, using a well-ordering of the set of positive integers. Your program will take two different positive integers and ...
user avatar
  • 6,645
3 votes
0 answers
306 views

Write a fast-growing assembly function

Synopsis Your goal is to implement the (asymptotically) fastest growing function within bounded code on a fictional CPU utilizing a quite limited, yet (probably) turing-complete instruction set. ...
user avatar
  • 1,593
16 votes
5 answers
737 views

Keep PPCG running in Game of Life

Conways' Game of Life is a well known cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves ...
user avatar
3 votes
5 answers
458 views

Largest Error Message in 100 bytes [duplicate]

The goal is to raise the error message with the most bytes! The error message may not be generated by the program itself, such as Python's raise. errors that do not ...
user avatar
  • 319
12 votes
6 answers
1k views

As close to flat as possible

Write a program or function that fulfills the following Scores less than 101 bytes under normal code-golf rules Takes no input1 and always outputs a single integer. Every integer is a possible output....
user avatar
  • 85k
-3 votes
7 answers
321 views

Busy beaver of sorts [duplicate]

I'm surprised this hasn't been done yet, but here we go. Create a program which prints some number of 1s (ideally as large as possible) before halting. The rules are simple: Your program is bounded ...
user avatar
17 votes
3 answers
992 views

Plight of the Concorde

Background The traveling salesman problem (TSP) asks for the shortest circuit that visits a given collection of cities. For the purposes of this question, the cities will be points in the plane and ...
user avatar
  • 2,509
26 votes
6 answers
4k views

Golf a number bigger than Loader's number

As a follow up to Shortest terminating program whose output size exceeds Graham's number and Golf a number bigger than TREE(3), I present a new challenge. Loader's number is a very large number, ...
user avatar
  • 7,069
-2 votes
3 answers
211 views

Golf some ones, and a program too [closed]

Introduction Busy Beavers are programs (specifically Turing Machine programs) that aim to output the most ones as possible, while having the least states as possible and halting. Challenge Your ...
user avatar
  • 897
7 votes
3 answers
1k views

Largest Number in Brainfuck BigInt for each program length up to 50 instructions

This challenge is for the largest finite number you can get BrainFuck programs of given lengths to contain in memory. We must use one of the BF versions that uses big integers for the cells rather ...
user avatar
  • 275
91 votes
11 answers
12k views

Build a Markdown bomb [closed]

I'm sure most of us have heard of zip bombs and similar decompression bomb tricks, where a maliciously crafted input creates a massively disproportionate output. We even had a question on here to do ...
user avatar
22 votes
1 answer
574 views

Traceless Busy Beaver

All those busy beavers made quite a mess. They wrote all over the tape. At this rate, our neighbour will stop lending us unbounded tapes. We need a new way to play the busy beaver game, one that ...
user avatar
  • 409
1 vote
1 answer
616 views

Solve the busy beaver

Given a number n, calculates BB(n) (the maximum number of 1s finally on the tape, among all ...
user avatar
  • 12.7k
16 votes
13 answers
3k views

BigNum Bakeoff Reboot

Some of you may be familiar with the BigNum Bakeoff, which ended up quite interestingly. The goal can more or less be summarized as writing a C program who's output would be the largest, under some ...
user avatar
55 votes
9 answers
10k views

Golf a number bigger than TREE(3)

The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti has at most i vertices, and no tree is a minor of ...
user avatar
  • 7,069
30 votes
15 answers
2k views

Create the slowest growing function you can in under 100 bytes

Your job is to create the slowest growing function you can in no more than 100 bytes. Your program will take as input a nonnegative integer, and output a nonnegative integer. Let's call your program ...
user avatar
  • 7,069
6 votes
1 answer
665 views

Large Numbers in BF

Background The language BrainF*** (or simply BF), is an extremely minimal programming language. We're going to strip it back even further by eliminating IO operations; only the sub-langage defined by ...
user avatar
  • 3,007
6 votes
4 answers
748 views

Busy Brain Beaver reboot [duplicate]

Introduction I found a really interesting puzzle it was called Busy Brain Beaver. But it has been 3 years since the latest activity and there are some things I didn't like about it. So I decided to ...
user avatar
  • 359
1 vote
0 answers
236 views

The Almost-Eternity Code [closed]

Write a program that outputs as many characters as possible, with two conditions: The program must be 256 bytes or shorter The program must almost surely eventually halt. In other words, the only ...
user avatar
12 votes
9 answers
1k views

The longest period iterating quine

As we know, a quine is a program that outputs its own source code. However, it's also possible to write a program that outputs another, different program, that outputs the first program again. For ...
user avatar
  • 7,102
-1 votes
1 answer
233 views

Ponderous primality testing [closed]

One of my favorite algorithms was posted on Stack Overflow as an answer to What is the fastest way to generate prime number recursively?. In pseudocode: Nathan's algorithm ...
user avatar
  • 2,663
24 votes
12 answers
2k views

Make a long type signature

Challenge Find an expression, at most 100 bytes long, with the longest type signature. Rules Any statically typed language with type inference is allowed The type must be non-ambiguous, but otherwise ...
user avatar
422 votes
21 answers
143k views

Build a Compiler Bomb

Introduction You're probably familiar with zip bombs, XML bombs, etc. Put simply, they are (relatively) small files which produce enormous output when interpreted by naïve software. The challenge ...
user avatar
  • 8,321
17 votes
32 answers
1k views

Maximizing output from minimal input

Obviously, code golfing is all about making the most of the least code. Who really cares what the actual output is? While we have had a challenge for highest input-to-output ratio, this is a call for ...
user avatar
  • 27.2k
4 votes
3 answers
454 views

Make a valid error maker! [duplicate]

We've been twice challenged to make 'error quines' (see Make an error quine! and Make a slow error quine maker!), so why don't we try the opposite? Instructions Write a "program" that, when ...
user avatar
41 votes
9 answers
2k views

Make a slow error quine maker!

As part of his answer to Make an Error Quine!, @Falko proposed the following algorithm: How to create your own solution in 2 minutes? Open a new file in an IDE of your choice. Bang your ...
user avatar
  • 206k
12 votes
2 answers
545 views

Combinator quines

Background You have just learned what combinatory logic is. Intrigued by the various combinators you spend quite a bit of time learning about them. You finally stumble upon this particular expression:...
user avatar
  • 1,485
23 votes
8 answers
2k views

Prolific Perfect Pangram Programs Pertaining to Printable ASCII

Updates: Time limit removed. You must be able to describe output - see new rule. A pangram is a sentence that uses every letter in the alphabet at least once, such as: The quick brown fox jumps over ...
user avatar
106 votes
32 answers
16k views

If a program terminates and there is no one to see it, does it halt?

It's time to face the truth: We will not be here forever, but at least we can write a program that will outlive the human race even if it struggles till the end of time. Your task is to write a ...
user avatar
  • 1,037
86 votes
75 answers
16k views

Largest number in ten bytes of code [closed]

Your goal is to print (to the standard output) the largest number possible, using just ten characters of code. You may use any features of your language, except built-in exponentiation functions. ...
user avatar
  • 10.8k
138 votes
91 answers
28k views

Largest Number Printable

Your goal is to write a program that prints a number. The bigger the number, the more points you'll get. But be careful! Code length is both limited and heavily weighted in the scoring function. Your ...
user avatar
  • 4,353
9 votes
2 answers
1k views

Build the busiest beaver in x86 machine code in 32 bytes or less

Your task is to write a program in x86 machine language (any version you like) that will run through as many instructions as possible and then halt, using a maximum of 32 bytes of code and starting ...
user avatar
  • 33.7k
18 votes
3 answers
1k views

Manufactoria: generate the slowest possible accepting program

Write a Manufactoria program that will accept the empty input tape. But don't do it quickly! I mean, write the program quickly, but don't let it run quickly. The slower the program, the better, as ...
user avatar
17 votes
3 answers
3k views

Longest non-repeating Game-of-Life sequence

Given a positive integer N, determine the starting pattern on a N x N-grid that yield the longest non-repeating sequence under Game of Life-rules, and ends with a fixed pattern (cycle of length 1), ...
user avatar
40 votes
14 answers
5k views

Shortest terminating program whose output size exceeds Graham's number

Write the shortest possible program (length measured in bytes) satisfying the following requirements: no input output is to stdout execution eventually terminates total number of output bytes exceeds ...
user avatar
  • 3,022
14 votes
4 answers
2k views

Busy Brain Beaver

Write a brainfuck program of no more than 256 characters that takes as many steps as possible, but does not loop infinitely. The program may not take any input. More specifically: Assume an ...
user avatar