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.
42
questions
24
votes
20
answers
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 ...
- 50.1k
14
votes
12
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 ...
- 99k
24
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, ...
- 99k
13
votes
1
answer
597
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 ...
- 99k
7
votes
1
answer
352
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 ...
- 25k
18
votes
1
answer
807
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 ...
- 753
28
votes
12
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 ...
- 7,898
4
votes
1
answer
461
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,659
17
votes
5
answers
1k
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 ...
- 50.1k
4
votes
5
answers
649
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
17
votes
7
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....
- 99k
0
votes
7
answers
389
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,849
17
votes
3
answers
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,599
27
votes
6
answers
6k
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,245
-3
votes
3
answers
229
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 ...
- 943