コンベアで計算する『Infinite Turtle』でBrainfuckインタプリタを実装した

作成日: 2022-08-09
ベルトコンベアで計算するゲームで、Brainfuckインタプリタを実装しました。
上からBrainfuckのプログラムを入力し、左からプログラムの入力を与えます。しばらくすると、左に計算結果が出力されます。
Video preview
Brainfuckのプログラムは、00-07に置換されています。
メモリ表現はZipパターンなので、理論的には容量は無限です。しかし、途中のベルトコンベアの長さがバッファとなり、実際にはメモリの大きさとプログラム長に制限があります。
苦労したことは2点あります。1点目はコンベアのモジュールのポートが入出力合わせて4つしかないことです。プログラムの解釈器はプログラムとメモリと入力と出力を扱います。これで4ポートを使い果たします。そこに、入力を受け取る信号をトップに送信するコンベアをうまくねじ込みました。
苦労したもう1点は、フォールバックコンベアです。infinite turtleには再帰モジュールという表現力の源があります。モジュール内に自己を置くことが可能です。しかし、この機能を使いすぎると、コンベアが大量に展開されて1ステップあたりの計算時間が現実的でなくなります。そのため、計算に必要な回路がプログラム長で抑えられるように、すでに計算に使った回路を再利用するようになっています。
Infinite Turtleのチューリング完全性を示せたので、満足しました。