Brainfuck: Difference between revisions
→Language Overview: fixed typo |
|||
| (5 intermediate revisions by 3 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 == | ||
| 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>brainfuck</sub>(n)''' returns the maximum value a pointer can be pointing at in program with n instructions when halting, using a version of brainfuck with unbounded arrays and integer cell values. The commands <code>.</code> and <code>,</code> are ignored. | ||
[under construction, reference] | |||
https://docs.google.com/spreadsheets/d/1fMavLTvRFnMe-PZ6NfVIDHlPgjcywVLLs1VkuaApi6k/edit?gid=101696978#gid=101696978 | |||
{| class="wikitable" | {| class="wikitable" | ||
!n | !n | ||
! | !BB<sub>brainf</sub>(n) | ||
!Champion | !Champion | ||
|- | |||
|0 | |||
|0 | |||
| | |||
|- | |- | ||
|1 | |1 | ||
| Line 63: | Line 69: | ||
|- | |- | ||
|5 | |5 | ||
| | |5 | ||
|<code>+++++</code> | |<code>+++++</code> | ||
|- | |- | ||
| Line 95: | Line 101: | ||
|- | |- | ||
|13 | |13 | ||
|≥ | |≥ 13 | ||
|<code>++++ | |<code>+++++++++++++</code> | ||
|- | |- | ||
|14 | |14 | ||
|≥ | |≥ 16 | ||
|<code> | |<code>++++[->++++<]></code> | ||
|- | |- | ||
|15 | |15 | ||
|≥ | |≥ 20 | ||
|<code>+++++[-> | |<code>+++++[->++++<]></code> | ||
|- | |- | ||
|16 | |16 | ||
|≥ | |≥ 25 | ||
|<code> | |<code>+++++[->+++++<]></code> | ||
|- | |- | ||
|17 | |17 | ||
|≥ | |≥ 176<ref name=":0">https://codegolf.stackexchange.com/questions/176013/largest-number-in-brainfuck-bigint-for-each-program-length-up-to-50-instructions</ref> | ||
|<code> | |<code>++[>+++++[-<]>>]></code> | ||
|- | |- | ||
|18 | |18 | ||
|≥ | |≥ 3,175<ref name=":0"></ref> | ||
|<code> | |<code>++[>++++++[-<]>>]></code> | ||
|- | |- | ||
|19 | |19 | ||
|≥ | |≥ 3,176 | ||
|<code> | |<code>++[>++++++[-<]>>]>+</code> | ||
|- | |- | ||
|20 | |20 | ||
|≥ | |≥ 3,177 | ||
|<code>++++++++[->++ | |<code>++[>++++++[-<]>>]>++</code> | ||
|- | |- | ||
|21 | |21 | ||
|≥ | |≥ 4,212<ref name=":0"></ref> | ||
|<code> | |<code>+[->++++++++++[-<]>]></code> | ||
|- | |- | ||
|22 | |22 | ||
|≥ | |≥ 6,234<ref name=":0"></ref> | ||
|<code> | |<code>+++[>+++++++++[-<]>>]<</code> | ||
|- | |- | ||
|23 | |23 | ||
|≥ | |≥ 90,963<ref name=":0" /> | ||
|<code> | |<code>+++[>++++++++++[-<]>>]></code> | ||
|- | |- | ||
|24 | |24 | ||
|≥ | |≥ 7,467,842<ref name=":0" /> | ||
|<code> | |<code>+++[>+++++++++++[-<]>>]<</code> | ||
|- | |- | ||
|25 | |25 | ||
|≥ | |≥ 239,071,921<ref name=":0" /> | ||
|<code> | |<code>+++[>++++++++++++[-<]>>]<</code> | ||
|- | |- | ||
|26 | |26 | ||
|≥ | | | ||
|<code>+++++[>+[->++<]>[-<++>]<<]</code> | | | ||
|- | |||
|27 | |||
| | |||
| | |||
|- | |||
|28 | |||
| | |||
| | |||
|- | |||
|29 | |||
| | |||
| | |||
|- | |||
|30 | |||
|≥ 220,283,786,963,581<ref name=":0" /> | |||
|<code>++++[>>+++++[-<++++>]<[-<]>>]></code> | |||
|- | |||
|31 | |||
|≥ 9<sup>9<sup>9<sup>33215</sup></sup></sup> | |||
|<code>+[->+[->+++<]>[-<+++>]<<[-<]>]></code> | |||
|- | |||
|32 | |||
| | |||
| | |||
|- | |||
|33 | |||
| | |||
| | |||
|- | |||
|34 | |||
| | |||
| | |||
|- | |||
|35 | |||
| | |||
| | |||
|- | |||
} | |||
=== '''Brainfuck Busy Beaver (original specifications + bi-infinite tape)''' === | |||
==== '''Brainfuck Busy Beaver (original specifications + bi-infinite tape)''' ==== | |||
{| class="wikitable" | |||
!n | |||
!Maximum steps<ref>https://codegolf.stackexchange.com/questions/282018/maximize-the-number-of-steps-a-brainfuck-program-of-length-13-takes-to-terminate</ref> | |||
!Champion | |||
|- | |||
|0 | |||
|0 | |||
| | |||
|- | |||
|1 | |||
|1 | |||
|<code>+</code> | |||
|- | |||
|2 | |||
|2 | |||
|<code>++</code> | |||
|- | |||
|3 | |||
|3 | |||
|<code>+++</code> | |||
|- | |||
|4 | |||
|512 | |||
|<code>+[+]</code> | |||
|- | |||
|5 | |||
|767 | |||
|<code>+[.+]</code> | |||
|- | |||
|6 | |||
|1,022 | |||
|<code>+[..+]</code> | |||
|- | |||
|7 | |||
|1,277 | |||
|<code>+[...+]</code> | |||
|- | |||
|8 | |||
|1,532 | |||
|<code>+[....+]</code> | |||
|- | |||
|9 | |||
|226,702 | |||
|<code>+[+[>]-<]</code> | |||
|- | |||
|10 | |||
|650,258 | |||
|<code>+[>+[<]->]</code> | |||
|- | |||
|11 | |||
|1,269,654 | |||
|<code>+[>+[<]->>]</code> | |||
|- | |||
|12 | |||
|8,734,764 | |||
|<code>+[>--[<]+>+]</code> | |||
|- | |||
|13 | |||
|47,244,577,523 | |||
|<code>+[>+[[<]<]>-]</code> | |||
|} | |} | ||
| Line 154: | Line 263: | ||
[page under construction] | [page under construction] | ||
== References == | |||
<references /> | |||
[[Category:Functions]] | |||
== References == | |||
<references /> | |||
[[Category:Functions]] | [[Category:Functions]] | ||
Latest revision as of 19:40, 19 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
BBbrainfuck(n) returns the maximum value a pointer can be pointing at in program with n instructions when halting, using a version of brainfuck with unbounded arrays and integer cell values. The commands . and , are ignored.
[under construction, reference] https://docs.google.com/spreadsheets/d/1fMavLTvRFnMe-PZ6NfVIDHlPgjcywVLLs1VkuaApi6k/edit?gid=101696978#gid=101696978
}Brainfuck Busy Beaver (original specifications + bi-infinite tape)
Brainfuck Busy Beaver (original specifications + bi-infinite tape)
| 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 | ≥ 13 | +++++++++++++
|
| 14 | ≥ 16 | ++++[->++++<]>
|
| 15 | ≥ 20 | +++++[->++++<]>
|
| 16 | ≥ 25 | +++++[->+++++<]>
|
| 17 | ≥ 176[1] | ++[>+++++[-<]>>]>
|
| 18 | ≥ 3,175[1] | ++[>++++++[-<]>>]>
|
| 19 | ≥ 3,176 | ++[>++++++[-<]>>]>+
|
| 20 | ≥ 3,177 | ++[>++++++[-<]>>]>++
|
| 21 | ≥ 4,212[1] | +[->++++++++++[-<]>]>
|
| 22 | ≥ 6,234[1] | +++[>+++++++++[-<]>>]<
|
| 23 | ≥ 90,963[1] | +++[>++++++++++[-<]>>]>
|
| 24 | ≥ 7,467,842[1] | +++[>+++++++++++[-<]>>]<
|
| 25 | ≥ 239,071,921[1] | +++[>++++++++++++[-<]>>]<
|
| 26 | ||
| 27 | ||
| 28 | ||
| 29 | ||
| 30 | ≥ 220,283,786,963,581[1] | ++++[>>+++++[-<++++>]<[-<]>>]>
|
| 31 | ≥ 99933215 | +[->+[->+++<]>[-<+++>]<<[-<]>]>
|
| 32 | ||
| 33 | ||
| 34 | ||
| 35 |
| n | Maximum steps[2] | Champion |
|---|---|---|
| 0 | 0 | |
| 1 | 1 | +
|
| 2 | 2 | ++
|
| 3 | 3 | +++
|
| 4 | 512 | +[+]
|
| 5 | 767 | +[.+]
|
| 6 | 1,022 | +[..+]
|
| 7 | 1,277 | +[...+]
|
| 8 | 1,532 | +[....+]
|
| 9 | 226,702 | +[+[>]-<]
|
| 10 | 650,258 | +[>+[<]->]
|
| 11 | 1,269,654 | +[>+[<]->>]
|
| 12 | 8,734,764 | +[>--[<]+>+]
|
| 13 | 47,244,577,523 | +[>+[[<]<]>-]
|
[page under construction]
References
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 https://codegolf.stackexchange.com/questions/176013/largest-number-in-brainfuck-bigint-for-each-program-length-up-to-50-instructions
- ↑ https://codegolf.stackexchange.com/questions/282018/maximize-the-number-of-steps-a-brainfuck-program-of-length-13-takes-to-terminate