Brainfuck: Difference between revisions
No edit summary |
seat warming |
||
| Line 1: | Line 1: | ||
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. | 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. | ||
== Language Overview == | == Language Overview == | ||
| Line 37: | Line 37: | ||
|} | |} | ||
== | == Brainfuck Busy Beaver == | ||
''' | '''BB<sub>brainf</sub>(n)''' returns the maximum cell value a program with n instructions can have when halting, using a version of brainfuck with unbounded arrays and integer cell values. The commands <code>.</code> and <code>,</code> are ignored. | ||
{| class="wikitable" | {| class="wikitable" | ||
!n | !n | ||
! | !BB<sub>brainf</sub>(n) | ||
!Champion | !Champion | ||
|- | |||
|0 | |||
|0 | |||
| | |||
|- | |- | ||
|1 | |1 | ||
| Line 105: | Line 109: | ||
|- | |- | ||
|16 | |16 | ||
|≥ | |≥ 176<ref name=":0">https://codegolf.stackexchange.com/questions/282018/maximize-the-number-of-steps-a-brainfuck-program-of-length-13-takes-to-terminate/</ref> | ||
|<code> | |<code>++[>+++++[-<]>>]</code> | ||
|- | |- | ||
|17 | |17 | ||
|≥ | |≥ 3,125<ref name=":0" /> | ||
|<code> | |<code>++[>++++++[-<]>>]</code> | ||
|- | |- | ||
|18 | |18 | ||
| | | | ||
| | | | ||
|- | |- | ||
|19 | |19 | ||
| | | | ||
| | | | ||
|- | |- | ||
|20 | |20 | ||
|≥ | |≥ 4,212<ref name=":0" /> | ||
|<code>++++ | |<code>+[->++++++++++[-<]>]</code> | ||
|- | |- | ||
|21 | |21 | ||
|≥ | |≥ 6,234<ref name=":0" /> | ||
|<code> | |<code>+++[>+++++++++[-<]>>]</code> | ||
|- | |- | ||
|22 | |22 | ||
|≥ | |≥ 90,963<ref name=":0" /> | ||
|<code>+++++ | |<code>+++[>++++++++++[-<]>>]</code> | ||
|- | |- | ||
|23 | |23 | ||
|≥ | |≥ 7,467,842<ref name=":0" /> | ||
|<code>+++++ | |<code>+++[>+++++++++++[-<]>>]</code> | ||
|- | |- | ||
|24 | |24 | ||
|≥ | |≥ 239,071,921<ref name=":0" /> | ||
|<code>+++++ | |<code>+++[>++++++++++++[-<]>>]</code> | ||
|- | |- | ||
|25 | |25 | ||
| | | | ||
| | | | ||
|- | |- | ||
|26 | |26 | ||
| | | | ||
| | | | ||
|} | |} | ||
| Line 152: | Line 156: | ||
[page under construction] | [page under construction] | ||
== References == | |||
<references /> | |||
[[Category:Functions]] | [[Category:Functions]] | ||
Latest revision as of 07:44, 8 November 2026
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.
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 brainfuck 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 |
-
|
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 |
Brainfuck Busy Beaver
BBbrainf(n) returns the maximum cell value a program with n instructions can have when halting, using a version of brainfuck with unbounded arrays and integer cell values. The commands . and , are ignored.
| n | BBbrainf(n) | Champion |
|---|---|---|
| 0 | 0 | |
| 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 | ≥ 176[1] | ++[>+++++[-<]>>]
|
| 17 | ≥ 3,125[1] | ++[>++++++[-<]>>]
|
| 18 | ||
| 19 | ||
| 20 | ≥ 4,212[1] | +[->++++++++++[-<]>]
|
| 21 | ≥ 6,234[1] | +++[>+++++++++[-<]>>]
|
| 22 | ≥ 90,963[1] | +++[>++++++++++[-<]>>]
|
| 23 | ≥ 7,467,842[1] | +++[>+++++++++++[-<]>>]
|
| 24 | ≥ 239,071,921[1] | +++[>++++++++++++[-<]>>]
|
| 25 | ||
| 26 |
[page under construction]