万能チューリングマシンを巡る論争

ここ一週間くらいの万能チューリングマシンを巡る論争が面白い。

ことの発端は、Stephen WolframがNew Kind of Science 709ぺージにあるセルオートマトンが最も簡単な万能チューリングマシンだと証明されたと彼のブログで発表したことだ。Wolframはこの証明に2万5千ドルの懸賞金を掛けていたのだが、見事証明したのがバーミンガム大学の20歳の学生Alex Smithだった。Alex君の証明はここにある。

これに対して、Alex君の証明は初期条件の設定に欠陥があり万能チューリングマシンの証明とはなりえないと、FOM(Foundation of Mathematics)メイリングリストで主張したのが、スタンフォード大学の看板教授であるVaughan Ronald Prattである。ちなみにPrott氏はSun MicrosystemsのあのUが互い違いになっているロゴをデザインしたことでも有名である。最後のフレーズはAlex君の証明を通したWolfram Researchの人間を揶揄している。

そして、この反論に対して再反論がWorlfram Researchから出たのだ。Alex君の初期条件設定は証明全体としてはあまり問題にはならないと。

まだ両者共に牽制しあっている状態で、Alex論文の特定箇所を具体的に指摘して主張を述べているわけではない。でも次にPrott氏から反論があるとすれば、Alex論文の欠陥を具体的に指摘し、誤っていることを証明しなければいけないので、どうなるかワクワクなのだ。

ちなみにこのページは万能チューリングマシンのとてもよい解説になっている。