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.
46 questions
6
votes
3
answers
287
views
Outgrow all computable functions
Almost all challenges on this site deal with computable programs and computable functions. In general, a computable function is one that can be implemented in a Turing-complete programming language. ...
- 831
7
votes
1
answer
378
views
Brainfuck braggy busy beaver
Challenge
Write a brainfuck program that takes as many steps to halt. Non-halting program brainfuck programs are not allowed.
Not only does it have to be busy but it should also brag by printing the ...
- 69
12
votes
3
answers
1k
views
Maximize the number of steps a brainfuck program of length 13 takes to terminate
The objective
Find a program among all programs of length 13, that takes a great number of steps to terminate. The more steps, the better. The ideal solution is a 13-th busy beaver. Why 'a'? Because ...
- 383
3
votes
1
answer
338
views
Long running section 11.4 Minsky machine
Challenge
We define a Minsky machine as a program made of the following two instructions:
+X which increments the register X and continues to the next instruction
-Xn which simply continues if X is ...
26
votes
20
answers
4k
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 ...
- 51.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 ...
- 104k
24
votes
21
answers
3k
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, ...
- 104k
13
votes
1
answer
679
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 ...
- 104k
7
votes
1
answer
431
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 ...
- 32.9k
19
votes
2
answers
2k
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 ...
- 773
30
votes
13
answers
3k
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 ...
- 8,078
4
votes
1
answer
555
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,669
18
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 ...
- 51.1k
4
votes
5
answers
855
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
19
votes
8
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.
...
- 104k