FANDOM


「brainfuckでn文字のコードでメモリ上に残すことができる最大の自然数」を\(BF(n)\)とする(メモリの個数も大きさも無限大とする)。brainfuckはチューリング完全(いかなる計算可能関数も表現できる)なので、\(BF(n)\)は計算不可能関数であり、\(f_{{\omega}_1^{CK}}(n)\)程度の強さである。

n BF(n)の下限 コード
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 85 +>+>+>+<[>[-<++++>]<<]
23 156 +>+>+>+<[>[-<+++++>]<<]
24 341 +>+>+>+>+<[>[-<++++>]<<]
25 781 +>+>+>+>+<[>[-<+++++>]<<]
26 1555 +>+>+>+>+<[>[-<++++++>]<<]
27 3906 +>+>+>+>+>+<[>[-<+++++>]>>]
28 9331 +>+>+>+>+>+<[>[-<++++++>]>>]
29 19608 +>+>+>+>+>+<[>[-<+++++++>]>>]
30 55987 +>+>+>+>+>+>+<[>[-<++++++>]>>]
31 137257 +>+>+>+>+>+>+<[>[-<+++++++>]>>]
32 335923 +>+>+>+>+>+>+>+<[>[-<++++++>]>>]
44 113037178808 ++++++++++++++[[>]+[<]>-]>>[<[->+++++++<]>>]
47 \(2^{127}-1\) +++[->+>>+<<<]>[->>[[->+<]+>-]<<[>[-<++>]<<]<]


​乗法

以下のコードは、自然数a,bに対してabを計算する。


a{+}[->b{+}<]

ここで、a{文字列}はa個の文字列(今回はa個の+)を表す。

\(BF(13)≥16\)


++++[->++++<]

\(BF(14)≥20\)


+++++[->++++<]

または

++++[->+++++<]

\(BF(15)≥25\)


+++++[->+++++<]

\(BF(16)≥30\)


+++++[->++++++<]

または

++++++[->+++++<]

​べき乗

以下のコードは\(\frac{b^{a+1}-1}{b-1}\)を計算する。


a{+>}+<[>[-<b{+}>]<<]

①1をa+1個並べる

②右端×bを左に足す(変数が1個になるまで繰り返し)

\(BF(22)≥\frac{{4^4}-1}{3}=85\)

+>+>+>+<[>[-<++++>]<<]

\(BF(23)≥\frac{{5^4}-1}{4}=156\)

+>+>+>+<[>[-<+++++>]<<]

\(BF(24)≥\frac{{4^5}-1}{3}=341\)

+>+>+>+>+<[>[-<++++>]<<]

\(BF(25)≥\frac{{5^5}-1}{4}=781\)

+>+>+>+>+<[>[-<+++++>]<<]

\(BF(26)≥\frac{{6^5}-1}{5}=1555\)

+>+>+>+>+<[>[-<++++++>]<<]

\(BF(27)≥\frac{{5^6}-1}{4}=3906\)

+>+>+>+>+>+<[>[-<+++++>]>>]


1を並べる操作を自動化するとこうなる。

a{+}[[>]+[<]>-]>>[<[->b{+}<]>>]

n=44からはこっちのほうが大きい。

\(BF(44)≥\frac{7^{14}-1}{6}=113037178808\)

++++++++++++++[[>]+[<]>-]>>[<[->+++++++<]>>]

​再帰

\(f(n)\)に対し、\(f^n(n)\)は以下のコードで計算できる。

n{+}[->+>+<<]>[->F<]

ここで、Fはポインタがさしている値nをf(n)に書き換える操作を表す。これを使うと急増化関数はこのように計算できる。

\(f_0(n)\)=

n{+}+


\(f_1(n)\)=

n{+}[->+>+<<]>[->+<]


\(f_2(n)\)=

n{+}[->+>+<<]>[->[->+>+<<]>[->+<]>[-<<+>>]<<<]


\(f_3(n)\)=

n{+}[->+>+<<]>[->[->+>+<<]>[->[->+>+<<]>[->+<]>[-<<+>>]<<<]>[-<<+>>]<<<]


ちなみに短くしようとすれば\(f_3(n)\)はここまで短くなる。

n{+}[->+>+>+<<<]>[->[->[->++<]>[-<+>]<<]>[-<+>]<<]

また、テトレーションレベルならべき乗コードを使ったほうが短くなる。

a{+}[->+>>+<<<]>[->>[[->+<]+>-]<<[>[-<b{+}>]<<]<]

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki