最近、「ビッグフォー
チューリング沼地 」の言語に捧げられた2つの資料がHabrにすぐに登場しました。
マルコフアルゴリズムと
Brainfuckについてです。 完全を期すために、これらの難解なシステムを別の重要なアルゴリズムプリミティブであるポストマシンと比較することは興味深いと思います。
Postマシン（
wiki ;簡単にするために、構文バリアントはそこから取られています）は、有名なTuringマシンに似ていますが、興味深い機能があります。 6個のコマンドのみが含まれ、さらに、メモリセルビットに記録できるのは2文字（バイナリ情報のエンコード）のみです。 「自然」、追加のメモリはありません、それは難解と呼ばれる無駄ではありません！
したがって、Postマシンでプログラミングする場合、Okkamov構文に対処する必要性に加えて、途中で残りの入力データへのリターンパスを失うことなく、すべての中間結果をテープに記録する方法について考える必要があります。 なぜ「残党」なのか？ 多くの場合、追加のメモリがないため、入力を繰り返し処理する必要があります（再帰的に処理することもあります）。 上記がPostマシンでの通常のアルゴリズムの記述が脳にとって良いトレーニングであり、非常に刺激的な活動であることを納得できることを証明することを望みます。
例
2つの自然数の乗算の最短実現の1つを考えます。 数字nとmは、1つの空のセルで区切られた単一の数字システムでテープに書き込まれます。 アルゴリズムの入力/出力は次のとおりです（キャリッジの初期位置がマークされています）。
v
..01110110 ..→..01111110 ..
3 * 2 = 6
アルゴリズムのアイデアは簡単な追加です。 サイクルの各パスで、マシンは左のファクターから1ビットを「食い止め」、使用可能な右端のブロックを「コピー」します（最初に2番目のファクター、次に最後のコピー）。 左の乗数が「終了」すると、mユニットのnブロックがテープに残ります。 それらをマージすると、必要な数n * mが得られます。
コード
0.！ -停止コマンド、実行は1行目から開始
1. 0-メインサイクル
2.→
3.？ 29、4-29：左乗数が終了しました
4.→
5.？ 6、4
6.→
7.？ 8、4
8.←
9.←
10. 0-正しいブロックのコピー
11.→
12.？ 13、11
13.→
14.？ 15、13
15.1
16.←
17.？ 18、16
18.←
19.？ 20、18
20.1
21.←
22.？ 23、10-コピーブロックの終わり
23.←
24.？ 25、23
25.←
26.？ 27、23
27.→
28.→1
29.→-2番目の要因のコピーをマージする
30. 0
31.→
32.？ 33、31
33.1
34.→
35.？ 0、36-プログラムを終了します
36.←
37.？ 29、36
頭の中、紙の上、または
このプログラムを使用して、アルゴリズムの正確性を確認できます。
これは私に知られている乗算の最短実装です。 ただし、コピーを作成し、それらを単一の配列にマージするプロセスを経済的に組み合わせる方法を見つけた場合、さらに強力に圧縮できる可能性があります。
このトピックに興味がある場合は、次のタスクについて検討することを提案します。
- i番目のフィボナッチ数の導出
- 2つの自然数の剰余による除算
- 「ガベージコレクター」。 有限数（n）のマークされたセルが、テープ上に未知の方法で分布しています。 それらを1つの山に「レーキ」する必要があります。つまり、マシンは、nマークのブロックだけを連続してテープに残す必要があります。
PS「ビッグフォー」チューリングマシン、レント、マルコフシステム、およびBrainfuckと呼ばれる-最も研究されているチューリング沼地。