x86のmov命令はチューリング完全

世の中には様々なチューリング完全なシステムがある。

x86のMMUはチューリング完全である。

BGP(Border Gateway Protocol)はチューリング完全である。

http://vanbever.eu/pdfs/vanbever_turing_icnp_2013.pdf

さて、x86の命令セットは極めて複雑で冗長であることが知られている。なんと、mov命令はチューリング完全であるそうだ。

http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

もちろん、mov命令でメモリ上に任意のコードを書いて実行させればチューリング完全になるが、論文ではそのようなコード生成や自己書き換えによるイカサマは行っていない。また、アドレスモードもたいていのRISCにあるようなものしか使っていないという。

x86のmov命令だけを使った後、無条件jumpで先頭に戻るループを実行することで、チューリング完全になるそうだ。

レジスターに入っている2つのアドレスA, Bが正しいかどうかは、アドレスAにある値をストアして、その後にアドレスBに別の値をストアして、そしてアドレスAの値をみると、AとBが等しいかどうかがわかる。レジスターRiの値にアドレスA入っていて、レジスターRjの値にアドレスBが入っている場合、レジスターRiとレジスターRjが等しいかどうかは、以下のようにしてわかる。

mov [Ri], 0
mov [Rj], 1
mov Rk , [Ri]

このコードはアドレスの指し示すメモリ内容を破壊するが、このアドレスはシンボル用に確保しているものなので問題はない。

比較の結果を0か1で得ることによって、Rkを使って2要素が入ったテーブルを参照することによって、2つのアドレスから選択をすることができる。レジスターNにアドレスNが入っていて、レジスターRi, Rjに選択される2つのアドレスが入っていて、Rkに比較の結果が0か1で入っている場合、以下のようにしてRi, Rjのどちらかのアドレスを選択してRlに入れることができる。

mov [N], Ri
mov [N+1], Rj
mov Rl , [N + Rk ]

この論文を元にした、MOV命令のみを使うコードを生成するコンパイラー、xoreaxeaxeax/movfuscatorがGitHubで公開されている。これはBrainfuckコンパイラーだが、BFBASICを併用することで、BASICからBrainfuckに変換できるので、BASICからmov命令(と末尾の銭湯に戻る無条件jump)のみのコードを生成するとしている。

なお、将来的にはCコンパイラーを実装するとしている。