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

43 questions
Filter by
Sorted by
Tagged with
3k views

### Live a longer 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 ...
• 48.4k
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 ...
• 92.1k
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, ...
• 92.1k
527 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 ...
• 92.1k
187 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 ...
• 513
239 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 ...
• 16.1k
704 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 ...
• 743
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 ...
• 6,785
404 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. ...
• 1,623
892 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 ...
• 48.4k
513 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 ...
• 339
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....
• 92.1k
342 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 ...
• 3,667
1k 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 ...
• 2,549
5k 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, ...
• 7,129
218 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 ...
• 917
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 ...
• 325
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 ...
• 1,274
598 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 ...
• 409
1 vote
652 views

### Solve the busy beaver

Given a number n, calculates BB(n) (the maximum number of 1s finally on the tape, among all ...
• 16.1k
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 ...
• 2,409
11k 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 ...
• 7,129
3k 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 ...
• 7,129
704 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 ...
• 3,439
765 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 ...
• 359
1 vote
240 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 ...
• 1,580
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 ...
• 7,182
237 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 ...
• 2,703
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 ...
• 2,381
145k 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 ...
• 8,371
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 ...
• 29.1k
460 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 ...
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 ...
• 208k
595 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:...
• 1,485
3k 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 ...
• 88.6k
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 ...
• 1,037
17k 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. ...
• 10.8k
29k 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 ...
• 4,373
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 ...
• 34.3k
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 ...
• 20.7k
4k 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), ...
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 ...
• 3,042