はじめに
前に「フォルダ&ファイル構成を活用する自作の難解プログラミング言語「DigFiles」を作ってみた」という記事を書いたのですが、前回は言語仕様などしか書いていなかったので、今回は少し踏み込んでこの言語がチューリング完全1であることを証明してみたいと思います。
方法
チューリング完全の証明方法は難解プログラミング言語のまとめWikiにいくつか書いてあります。
その中で今回は以下の方法を使いたいと思います。2
Say you have a language K whose computational class is known. (A common value for K is Brainfuck, which is known to be Turing-complete.) You also have a language Q whose computational class is in question, and you want to show that it is computationally equivalent to K.
...
Simulation
If an interpreter for K can be implemented in Q, then Q can solve at least as many problems as K can.
「計算量が既に知られている言語Kがあるとする。(Kの一般的な値はBrainfuckで、これはチューリング完全であることが知られている。) また、計算クラスが疑問な言語Qがあり、これがKと計算上等価であることを示したいとする。
...
シミュレーション
KのインタプリタがQに実装できれば、Qは少なくともKと同数の問題を解くことができる。3」
ということで、DigFilesでBrainfuckのインタプリタを実装してみます。
実装方針
実装の考え方としては、Brainfuckにて入力されたコードを各文字で分岐させてあげて、それぞれの命令と同等の処理を実行させれば良いことになります。
分岐の実装
DigFilesには分岐自体の命令はありませんが、loopコマンドを使用することで分岐の動作を行わせることが可能です。
ただし、本来繰り返し処理用の命令であるため、色々工夫する必要があります。
例えば、このloopコマンドは「2つの変数が同値でない間」に処理を行うため、そのままの状態でBrainfuckの文字と値を比較してもノットイコールでの判定しか出来ません。
従って構成としては、条件が不成立時にセットされるフラグを準備しておき、そのフラグにて再度判定をかける形で実装していきたいと思います。
その他にも、ループから抜け出すための値管理など色々丁寧に実装していく必要があります。
[]の実装
基本的には、入力されたBrainfuckコードの実行箇所を表す変数の値を適宜書き換えることで実装できます。
ただし、Brainfuckの命令である[]はコード上でネストされている可能性が考えられるため、移動先は注意する必要があります。
今回はDigFilesの記憶領域に変数名を連番で扱うことで擬似的なスタック領域として扱い、[の出現位置を管理していけば良さそうです。
><+-.,の実装
これはわりと単純な命令ですので、そのままDigFilesの操作とある程度対応付けられそうなので、愚直に実装できそうです。
| Brainfuck | DigFiles |
|---|---|
| > | addコマンドにて「ポインタ変数」を+1する4 |
| < | addコマンドにて「ポインタ変数」を-1する4 |
| + | addコマンドにて「*ポインタ変数」を+1する5 |
| - | addコマンドにて「*ポインタ変数」を+1する5 |
| . | outコマンドにて「*ポインタ変数」にセットされている文字を出力する6 |
| , | inコマンドにて「*ポインタ変数」に入力された文字をセットする6 |
※実際には変数idは数値の形ですが、ここではわかりやすく日本語で記述します。
実装
上記を踏まえて実装した結果が以下のコードになります。7
Githubのページ
正直、わりとクソコードだと思います。
単純にファイル名とかフォルダ名でコーディングしようとすると、名前の変数を割り当てるのがめちゃくちゃめんどくさくて、行き当たりばったりの命名になってしまっている部分があります。
（とはいえ、DigFilesの言語方針通り、細かくメソッド分けはされているので予定通りとも言えるのかもしれませんが…）
また、今回盲点だったのがフォルダ構成のネストが深くなっていったせいで、途中フォルダ名の文字数に制限がかかってしまいました。
Windowsはパスの長さに細かい制限があるの忘れていました…8
最後に
このコードを実行してもらうと分かるのですが、処理速度激遅です。
Brainfuckのインタプリタを、DigFilesのインタプリタで動かしている関係上ある程度仕方のないことではありますが、ネット上のオンラインコンパイラで1秒もかからない処理が2分30秒位かかったりします。
デバッグ時に無限ループ入っているのか処理に時間がかかっているのかの判断に困ったりしました。
まぁ、兎にも角にもとりあえず当初の目的である、チューリング完全の証明ができたのでひとまず安心しました。
あぁ、よかった よかった。
-
チューリング完全の詳しい意味については省略しますが、ざっくり「高級言語と同等の計算能力を持っていること」と捉えてもらって大丈夫です。 ↩
-
ReductionやTranslationでも証明できそうですが、今回は最終的に成果物として形が残せるという理由でSimulationを選定しました。 ↩
-
この形式の証明には潜在的な問題ℒがあると示されていますが、今回は当てはまらなそうでしたので無視します。 ↩
-
一応文字コードは異なりますが、DigFilesで使用されているUTF-8はその歴史的経緯からASCIIに互換性があるため問題ありません。 ↩ ↩2
-
入力値はBrainfuckコードの終わりを認識するため、コードの末尾に「/」を付けています。 ↩
-
今よく考えたら「subst」使えばもうちょっとフォルダ名粘れたっちゃあ粘れたな… ↩