チューリング完全

まず、あらゆる計算が実現できるということを定めます。

ここでは、計算とは、入力から定められた規則を定められた手続きに従って適用することで出力を構成することを言います。規則というのは、例えば、C言語、BASIC、Fortran、LISP、Haskell、Java、Python、Ruby といったプログラム言語であり、手続きとはそれらの言語で書かれたプログラムのことです。

今、規則Rによってあらゆる計算が実現できるということを、上に挙げたいずれか一つの言語について、その言語で書かれたプログラム（ただし入力を受け取って出力を返すもの。停止しなくてもよい。）のすべてを、規則Rを用いた手続きで同じことができるように書き換えられることと定めます。もし上のいずれか一つについて書き換えができるならば、すべてについてもできることが知られています。というのも上の言語は相互に書き換えが可能だからです。その意味であらゆる計算が実現できると言うのです。

逆に、規則Rを用いて書かれた手続きのすべてを上のどの言語にも書き換えられることも言えるはずです。なぜなら、規則Rを適用するプログラム（ここでいう gnuplot）は何らかのプログラム言語で書かれているからです。

そのような意味であらゆる計算が実現できるような規則Rは、普遍的なプログラム言語のクラスに属していると考えられます。そのクラスに属するすべての言語は、他の言語と相互に書き換えが可能であり、また、C言語と相互に書き換えが可能です。このクラスに属する規則はチューリング完全（Turing complete）であると言われます。

今回のテーマをこの言葉で書き換えるならば、gnuplot のバッチファイルはチューリング完全であるということになります。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

それでは作ってみよう

というわけで作りました。プログラムは以下の3つのファイルから成り立っています。

bfi.plt: 大本で読み込むファイル

load "bfi_init.plt"
load "bfi_run.plt"

bfi_init.plt: 関数の定義および変数の初期化

stoi(s, l) = l == 0 ? 0 : 2 * stoi(s, l - 1) + (s[l:l] eq "0" ? 0 : 1)
itos(i, l) = l == 0 ? "" : itos(i / 2, l - 1) . ((i & 1) == 0 ? "0" : "1")
repstr(s, i, j, r) = s[:i - 1] . r . s[j + 1:]
cset = " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ" .\
"[\\]^_'abcdefghijklmnopqrstuvwxyz{|}‾"
itoc(i) = (i >= 32 && i <= 126) ? cset[i - 31: i - 31] : ""
cmem(k) = k == 0 ? "00000000" : cmem(k - 1) . cmem(k - 1)
mget(m, l, i) = stoi(m[l * i + 1:l * (i + 1)], l)
mset(m, l, i, v) = repstr(m, l * i + 1, l * (i + 1), itos(v, l))
pptr = 0
ins = program[1:1]
pstc = cmem(10)
psptr = 0
mem = cmem(10)
mptr = 0
iptr = 0
ostr = ""

bfi_run.plt: インタープリタの本体部

if (ins eq ">") mptr = mptr + 1
if (ins eq "<") mptr = mptr - 1
if (ins eq "+") mem = mset(mem, 8, mptr, mget(mem, 8, mptr) + 1)
if (ins eq "-") mem = mset(mem, 8, mptr, mget(mem, 8, mptr) - 1)
if (ins eq ".") ostr = ostr . itoc(mget(mem, 8, mptr))
if (ins eq ",") mem = mset(mem, 8, mptr, mget(input, 8, iptr)); \
iptr = iptr + 1
if (ins eq "[") pstc = mset(pstc, 16, psptr, pptr); psptr = psptr + 1
if (ins eq "]") pptr = mget(mem, 8, mptr) == 0 ? pptr : \
mget(pstc, 16, psptr - 1) - 1; psptr = psptr - 1
pptr = pptr + 1
ins = program[pptr + 1:pptr + 1]
if (ins ne "") reread
print ostr

このバッチファイルは、変数 program に brainfuck のプログラムを、input に入力のビット列を指定し、bfi.plt をロードすることで動作します。入力を読まない場合は input は不要です。

それでは先に出した Hello world プログラムを実行してみましょう。

コマンド：

> program = "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..++\
+.>-.------------.<++++++++.--------.+++.------.--------.>+."
> load "bfi.plt"
Hello, world!

出た！

厳密に言うとこのバッチファイルは停止しない限り出力を画面に出さないのですが、出力文字列 ostr を出力と同一視すれば、 brainfuck のあらゆるプログラムを実行できることになる、はず。

まとめ

今回は gnuplot のバッチファイルであらゆる計算が実現できることを示しました。そのために brainfuck というプログラム言語（？）のインタープリタを gnuplot のバッチファイルで作りました。実は次の記事で他の人が gnuplot のバッチファイルで brainfuck のインタープリタを作っていたのですが、

gnuplotで遊ぼう 〜 階乗, フィボナッチ数, Brainfuck処理系まで - プログラムモグモグ

それに書かれていたものは外部プログラムに頼っていて、求めていたものではないと思いました。そこで自分でインタープリタを書いてみたという話でした。