2015-06-21

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コンパイラーを実装するとしている。

2 comments:

  1. チューリング完全にするには無限ループが1つあればいい(そして1つは必要)なので、これを「mov命令はチューリング完全」と呼ぶのはかなりズルいと思う。

    ReplyDelete
  2. 無限ループ一つでチューリング完全にする方法あるいはそれを書いている文献を教えてください。

    ReplyDelete

You can use some HTML elements, such as <b>, <i>, <a>, also, some characters need to be entity referenced such as <, > and & Your comment may need to be confirmed by blog author. Your comment will be published under GFDL 1.3 or later license with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.