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