Brainfuck: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
Polygon (talk | contribs)
→BB_brainf: v removed
Patcail (talk | contribs)
 
(7 intermediate revisions by 4 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. 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 ==
== 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.
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 (mod 256 or arbitrary integer)
|Increment current cell
|-
|-
|<code>-</code>
|<code>-</code>
Line 39: Line 37:
|}
|}


== BB_brainf ==
== Brainfuck Busy Beaver ==
'''BB_brain(n)''' returns the maximum cell value a program with n instructions can have when halting.
'''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_brainf(n)
!BB<sub>brainf</sub>(n)
!Champion
!Champion
|-
|0
|0
|
|-
|-
|1
|1
Line 63: Line 69:
|-
|-
|5
|5
|≥ 5
|5
|<code>+++++</code>
|<code>+++++</code>
|-
|-
Line 95: Line 101:
|-
|-
|13
|13
|≥ 16
|≥ 13
|<code>++++[->++++<]</code>
|<code>+++++++++++++</code>
|-
|-
|14
|14
|≥ 20
|≥ 16
|<code>+++++[->++++<]</code>
|<code>++++[->++++<]></code>
|-
|-
|15
|15
|≥ 25
|≥ 20
|<code>+++++[->+++++<]</code>
|<code>+++++[->++++<]></code>
|-
|-
|16
|16
|≥ 30
|≥ 25
|<code>++++++[->+++++<]</code>
|<code>+++++[->+++++<]></code>
|-
|-
|17
|17
|≥ 36
|≥ 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>++[>+++++[-<]>>]></code>
|-
|-
|18
|18
|≥ 42
|≥ 3,175<ref name=":0"></ref>
|<code>+++++++[->++++++<]</code>
|<code>++[>++++++[-<]>>]></code>
|-
|-
|19
|19
|≥ 49
|≥ 3,176
|<code>+++++++[->+++++++<]</code>
|<code>++[>++++++[-<]>>]>+</code>
|-
|-
|20
|20
|≥ 56
|≥ 3,177
|<code>++++++++[->+++++++<]</code>
|<code>++[>++++++[-<]>>]>++</code>
|-
|-
|21
|21
|≥ 64
|≥ 4,212<ref name=":0"></ref>
|<code>++++++++[->++++++++<]</code>
|<code>+[->++++++++++[-<]>]></code>
|-
|-
|22
|22
|≥ 72
|≥ 6,234<ref name=":0"></ref>
|<code>+++++++++[->++++++++<]</code>
|<code>+++[>+++++++++[-<]>>]<</code>
|-
|-
|23
|23
|≥ 81
|≥ 90,963<ref name=":0" />
|<code>+++++++++[->+++++++++<]</code>
|<code>+++[>++++++++++[-<]>>]></code>
|-
|-
|24
|24
|≥ 90
|≥ 7,467,842<ref name=":0" />
|<code>+++++++++[->++++++++++<]</code>
|<code>+++[>+++++++++++[-<]>>]<</code>
|-
|-
|25
|25
|≥ 340
|≥ 239,071,921<ref name=":0" />
|<code>++++[>+[->++<]>[-<++>]<<]</code>
|<code>+++[>++++++++++++[-<]>>]<</code>
|-
|-
|26
|26
|≥ 1364
|
|<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

References