コラム
» 2019年07月12日 12時30分 公開

これが現代の科学力……! 「スーパーマリオメーカーはチューリング完全」はなぜたった1年半で証明されたのか (2/2)

[ねとらぼ]
前のページへ 1|2       

そして、チューリング完全へ……

 さっきの64ビット加算器の動画なのですが、入力はマリオがブロックを頭突して行っているんですね。一方、出力は2種類のオブジェクトで表現しているんですね(「ファイアフラワー」を0、「Pスイッチ」を1とする2進数)。

 これだと加算の結果を使って次の計算をしようと思っても、マリオを操作して変換する必要があります。すごく面倒くさい。



 ですから、入力も出力も「POWブロック」が0、「ブラックパックン」が1ということにして、フォーマットを統一しようと。



 この2つのオブジェクトには、マリオの世界では物理的な性質に違いがあるんですね。POWブロックが跳ねるブロックに当たってもブラックパックンは跳ねないとか、両方跳ねるときも跳ね方が違うとか。この物理的な性質を生かすことで、コンパクトなギミックで2進数の計算ができる、と。





 このやり方の一番良いのは、入力と出力のフォーマットが一致しているので、この計算結果をまた入力して、いろいろできることです。そういうことをやっていくと引き算、割り算、掛け算の回路が作れるようになって。



 私は2017年2月5日に「マリオメーカーはチューリング完全だった【万能計算機】」をアップしました。今のコンピュータで計算可能なものは、“理想的なマリオメーカー”なら何でも計算できるんですよ」と数学的に証明するような動画です。



 ここまで紹介してきた動画は全て、ニコニコ動画で「マリオメーカー学会」で検索できます。このタグが付けられた動画にはスコアアタック、最速クリアなどのジャンルもあって、めちゃくちゃ面白いです。

 つい先日、続編の「スーパーマリオメーカー 2」が発売されて、物理法則が変わった部分もあって、参入障壁が下がっていますし、皆さんにもマリオメーカー学会で研究成果を発表していただけると、とてもうれしいです。





質疑応答

―― チューリングマシンはメモリが無限に扱えると思うのですが、スーパーマリオメーカーの計算機では?

 そもそも、どこかに無限大は発生しなくてはいけなくて。チューリング完全を証明した動画では「理想的なマリオメーカー」としていますが、「縦方向は無限にコースが組めるとした場合」「無限にオブジェクトが設置できる場合」などを想定しています。

―― 「チューリング完全なマリオメーカー計算機」の計算速度を、実在するコンピュータと比較すると?

 計算スピードは、ENIAC(エニアック)よりも遅いと思いますよ。

 今のスピード感は、5ビット数同士の掛け算だったら、3〜4分あればできるくらい。スーパーマリオメーカー 2の登場で、多少高速化される可能性もあります。

※ENIAC:1946年、米国で開発された世界初の真空管式コンピュータ

―― いろいろ工夫したところはあると思いますが、お気に入りのアイデアは?

 1つ挙げるなら、「マリオエンディアン方式」と呼ばれるものです。

 以前はギミックを作動させるために、計算中にマリオを手動で動かし、カメラを移動させる必要があったんですけど……まあ、自動化したいじゃないですか。そこで、回路の中にマリオも入れ、ビットの後ろをついていくようにして操作不要にしたのがこの方式です。


マリオエンディアン方式は、いわゆる「全自動マリオ」で計算を行うような仕組み


あまりの斬新さに殺到したコメントで、解説が読めない

※本記事の文章は読みやすさなどに配慮し、発表内容を一部補足・修正しています

※制作協力:日曜数学会

※2019年7月22日 追記:発表のもようを撮影された動画が公開されたため、記事冒頭に追加しました



前のページへ 1|2       

Copyright © ITmedia, Inc. All Rights Reserved.