2010-08-20 (金)
*プログラミンはチューリング完全である(書きかけ)
ここのところ自分の中で一番気になっていたことが解決した．
命令セットから証明するのはなんだか難しそうですが，チューリング完全な処理系をエミュレートできれば，その言語もチューリング完全であることが保障されるので，brainfuckを実装しました．
作りかけのbrainfuck： http://bit.ly/cpn2FL
これによって，一般的なコンピュータで処理できる問題ならばプログラミンでも処理が可能であることが分かりました．
今は最低限の実装です．あと，入出力を電卓と同じように実装したり，オーバーフロー処理も必要ですね．
最低限必要な命令は
- 上下左右への移動
- 無限ループ
- 特定の絵がぶつかるまで待つ
- 自身を指定した別の絵に変化させる
- 指定したラベルにジャンプ(ラベルは12個のみ)
- 複数の命令を並列に実行
くらいか．他はなくてもどうにかなることは分かっています．
他のプログラミング言語にはあって，プログラミンに欠けているのは，自由な条件分岐と記憶領域なので，それらは電卓を作ってみた時点でどうにかなると確証を持っていたのだけど，本当にチューリング完全であるというために念のため．