Brainfuck: Difference between revisions
Jump to navigation
Jump to search
→BB_brainf: v removed |
seat warming |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
Brainfuck is a Turing complete language created in 1993 by Urban Muller. | 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. | ||
The language was designed to have an extremely tiny compiler (on the order of 200 bytes), while remaining Turing-complete | |||
== Language Overview == | == 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 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. | Like in a [[Turing machine]], there is a pointer, initially pointing to the first memory cell. | ||
| Line 21: | Line 19: | ||
|- | |- | ||
|<code>+</code> | |<code>+</code> | ||
|Increment current cell | |Increment current cell | ||
|- | |- | ||
|<code>-</code> | |<code>-</code> | ||
| Line 39: | 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 63: | Line 65: | ||
|- | |- | ||
|5 | |5 | ||
| | |5 | ||
|<code>+++++</code> | |<code>+++++</code> | ||
|- | |- | ||
| Line 107: | 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 154: | 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]