Brainfuck

Brainfuck is a Turing complete language created in 1993 by Urban Muller.

The language was designed to have an extremely tiny compiler (on the order of 200 bytes), while remaining Turing-complete. For Busy Beaver and small Turing machine research, Brainfuck provides an interesting minimal model of computation distinct from the standard 2-symbol Turing machine formalism.

Language Overview

Brainfuck operates on an array of memory cells, each initially set to zero. In the original implementation, the array was 30,000 cells long and each cell values would be limited to numbers from 0 to 255, but this may not be part of the language specification. A braincuk program can work with different, and sometimes unbounded, array length and cells size.

Like in a Turing machine, there is a pointer, initially pointing to the first memory cell.

Programs are composed of commands, represented with symbols:

Command	Operation
>	Move pointer right
<	Move pointer left
+	Increment current cell (mod 256 or arbitrary integer)
-	Decrement current cell
[	Jump forward past matching ] if current cell is zero
]	Jump back to matching [ if current cell is non-zero
.	Output current cell as a character (often ASCII)
,	Input a character and store in current cell

BB_brainf

BB_brain(n) returns the maximum cell value a program with n instructions can have when halting.

n	BB_brainf(n)	Champion
1	1	+
2	2	++
3	3	+++
4	4	++++
5	≥5	+++++
6	≥6	++++++
7	≥7	+++++++
8	≥8	++++++++
9	≥9	+++++++++
10	≥10	++++++++++
11	≥11	+++++++++++
12	≥12	++++++++++++
13	≥16	++++[->++++<]
14	≥20	+++++[->++++<]
15	≥25	+++++[->+++++<]
16	≥30	++++++[->+++++<]
17	≥36	++++++[->++++++<]
18	≥42	+++++++[->++++++<]
19	≥49	+++++++[->+++++++<]
20	≥56	++++++++[->+++++++<]
21	≥64	++++++++[->++++++++<]
22	≥72	+++++++++[->++++++++<]
23	≥81	+++++++++[->+++++++++<]
24	≥90	+++++++++[->++++++++++<]
25	≥340	++++[>+[->++<]>[-<++>]<<]
26	≥1364	+++++[>+[->++<]>[-<++>]<<]

[page under construction]