カットの下では、通常のマルコフアルゴリズムを使用したBrainfuckインタープリターの最も異常な実装が見つかります。 この実装では、すべてのBrainfuckオペレーターとインタープリター自体が通常のマルコフアルゴリズムです。 この投稿の目的は、アルゴリズムの古典的な理論の観点からBrainfuckを検討し、アルゴリズムの概念の古典的な改良を使用してその実装をもたらすことでした。 そのような異常なプログラミングで脳を傷つけることを恐れない人は大歓迎です（多くのテキストの下で、アルゴリズムの理論に精通していないと理解するのが難しい場合がありますが、投稿の最後にこのインタープリターの実装へのリンクがあり、実際に試すことができます）。 明らかな理由で、そのパフォーマンスはそれほど高くありませんが、作業アルゴリズムを理解するという観点からは非常に明確です。
こんなアイデアが生まれた方法
それはすべて、ハブ上のBrainfuckに関する多くの投稿がそれが何であるかを知るために私をノックダウンしたという事実から始まりました。 さらに、私の友人でプログラマでもあるこの投稿に出会い、「大学の学生をこのアルゴリズムの理論で拷問したら、原始的な再帰関数を使用してBrainfuckインタープリターを説明してください」と言った。 このフレーズと悪天候と気分は、何が起こったのかを押し上げました。 ITは数学的なリソースではないため、再帰関数を使用して実装するのではなく、通常のマルコフアルゴリズムを使用して実装する方が正しいように思えました。
発生する基本的な概念を理解するには、以下をお読みください。
Brainfuck;再帰関数;通常のマルコフアルゴリズム。実際に完全なBrainfuck
ご存知のように、Brainfuckは完全な言語であるチューリングであり、理論的にはそれを使用して任意のアルゴリズムを実装できます。 Brainfuckがアルゴリズムの理論の観点から見てみましょう。 チューリングマシンと自然値レジスタを備えたマシンのハイブリッドとして最も正確に説明できます。 Brainfuckはチューリング完全であるため、自然値レジスタを備えたマシンと、チューリングマシン、再帰関数、マルコフアルゴリズム（私が行った）の両方で実装できることを意味します。
そして、実装されているもの：
Brainfuckチーム
| チームの説明
| 実装されましたか？
|
>
| 次のセルに行く
| 実装されています。
|
<
| 前のセルに移動する
| 実装されています。
|
+
| 現在のセルの値を1増やす
| 実装されています。
|
-
| 現在のセルの値を1減らす
| 実装されています。
|
。
| 現在のセルから値を出力
| 実装されています。
|
、
| 外部から値を入力し、現在のセルに保存します
| 実装されていないため、この操作はマルコフアルゴリズムの観点からは特に重要ではありません。
|
[
| 現在のセルの値がゼロの場合、先に進みます
対応するセルに続くセルへのプログラムテキスト]（考慮事項
ネスト）
| 実装されています。
|
]
| 現在のセルの値がゼロでない場合、戻る
プログラムテキストを記号[（ネストを含む）
| 実装されています。
|
通常のマルコフアルゴリズムでのインタープリターの実装に必要なもの：脳波にコードを入力する行（「、」演算子なし）、メモリーテープとして機能する行、バッファー行（結果を表示する）、結果を表示する行
インタープリターが機能し始めると、string-stringは次のようになります。
._ ...
ポイントの数は使用可能なメモリセルの数で、記号_は現在のセルへのポインタです。
マルコフアルゴリズム製品は、同じ長さの文字列の2つの配列として定義されます。最初の製品は製品の左側の部分であり、2番目は製品の右側です。 製品の正しい部分がFINで終わる場合、これはこの製品が最終製品であることを意味します。
そもそも、Markovアルゴリズムを使用してbrainfacの操作を実装する方が簡単です。
Brainfuckチーム
| マルコフアルゴリズムによる実装
|
>
| リボンライン：
string[] left = new string[5] { "|_.", "@_|", "@_.", "_..", "_.|" };
string[] right = new string[5] { "|.@_", "|@_", "_.FIN", "._.FIN", ".@_" };
|
<
| リボンライン：
string[] left = new string[2] { "|_", "._" };
string[] right = new string[2] { "_|", "_.FIN" };
|
+
| リボンライン：
string[] left = new string[1] { "_"};
string[] right = new string[1] { "|_FIN"};
|
-
| リボンライン：
string[] left = new string[1] { "|_" };
string[] right = new string[1] { "_FIN" };
|
。
| バッファー行：
| > .a
a. >.a
.. >.
.aaaaaaaaaa > a,.
,a > a,
.aaaaaaaaa > 9
.aaaaaaaa > 8
.aaaaaaa > 7
.aaaaaa > 6
.aaaaa >5
.aaaa > 4
.aaa > 3
.aa > 2
.a > 1
. > 0
, >
a > .a
OUT
1>0
2>0
3>0
4>0
5>0
6>0
7>0
8>0
9>0
00>0
|
[
| ソース行（ネスト[]を考慮に入れる）
string[] left = new string[10] { "_+", "_-", "_.", "_,", "_<", "_>","_[","_]","**","]*" };
string[] right = new string[10] { "+_", "-_", "._", ",_", "<_", ">_","[__","]*","_","]_FIN" };
|
]
| ソース行（ネスト[]を考慮に入れる）
string[] left = new string[11] { "+_", "-_", "._", ",_", "<_", ">_", "]_", "[_", "*_","[**", "[*" };
string[] right = new string[11] { "_+", "_-", "_.", "_,", "_<", "_>", "__]", "[*","**", "_[", "_[FIN" };
|
さて、今では適切な通常のインタプリタアルゴリズム。 これはソース行で実行され、各生産後にサブアルゴリズムが操作テーブルから呼び出されます（上記を参照）。
| 交換するもの | 交換するもの | サブアルゴリズムと呼ばれる |
| _ + | + _ | + |
| _- | -_ | - |
| _ [ | [_ | [ |
| _> | > _ | > |
| _ < | <_ | < |
| _] | リボンラインで製品を実行できる場合
._。 ._。FINその後
] _
それ以外の場合、サブアルゴリズム呼び出し]
| ] |
| _。 | ._ | 。 |
プログラム全体を一度に実行することも、段階的に実行することもできます。 C＃での実装。したがって、動作させるには、.NET 2.0をインストールする必要があります。
古典的なHello Worldのデモンストレーション作業！ このインタープリターのBrainfuckで。
PS少なくとも誰かにとっては興味深いものだったと思います。 私は可能な限り最小の量のテキストを維持しようとしました。
インタープリターの実装。 このモンスターを職場で試すことができます。