「ウルフラム氏のチューリングマシン」の万能性を20歳の学生が証明 39
二十歳を過ぎた、ただの人 部門より
あるAnonymous Coward 曰く、
WIRED VISIONの記事のよれば、Wolfram氏が提案したもっとも簡単なチューリングマシンが万能チューリングマシンであることを20歳のイギリスの学生が証明して見せたのこと。Wolfram氏は、この証明に2万5000ドルの賞金をかけており、見事47日後に証明して見せた。
ちなみに、Wolfram氏は、複雑系理論の権威でもあり、Wolfram Mathematicaの設立者でもある。社名の通り、Mathematicaを開発している会社だ。
提案されたチューリングマシンは、2つの状態と3つの色を持つ装置であり、証明の内容(PDF)も公開されているので、興味のある方は追ってみてはいかがでしょうか?