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

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

「今のコンピュータで計算可能なものは、“理想的なマリオメーカー”なら何でも計算できる」。

[ねとらぼ]


 「マリオメーカー学会」というものをご存じでしょうか。自作ステージを作って遊べるゲーム「スーパーマリオメーカー」に斜め上過ぎる楽しみ方を見いだした“研究者”の集まりで、これまでには「クリアに20万年ほどかかるステージ」「ギミックを巧みに活用した計算機」などが開発されています。

 話がぶっ飛んでいて何が何だか分からないかもしれませんが、きっとそれだけ研究が進んでいるということでしょう。今回は、5分間で数学を語るイベント「日曜数学会」から、同学会のハイレベルさが伝わる発表「スーパーマリオメーカーはチューリング完全」を書き起こしました。

スーパーマリオメーカーはチューリング完全

発売から約2週間で、計算機になったスーパーマリオメーカー



 「スーパーマリオメーカー“上で動く計算機”」というものをご存じない方もいらっしゃるかと思います。今日はまずマリオメーカーで計算するとはどういうことなのか、という話をしたいと思います。

 初期に開発された計算機から順に説明していきます。スーパーマリオメーカー発売(2015年9月10日)の約半月後、同作で論理演算を行う動画がニコニコ動画で公開されました。

 そこから抜粋してきた画像なんですけど、ここ(直線に並んだブロックの途中)に2つブロックがあります。マリオは壊すことも壊さないこともできるんですけど、この2つのブロックが両方残っている場合に限って、ブロックの直線上を甲羅が通過していきます。

 これがAND回路の仕組みです。同様にOR回路、NOT回路も作れます。







 で、論理回路素子ができるということは、2ビットの2進数を計算する加算器を作ることができます。コースがデカくて、マリオは豆粒みたいに見えますね。





 この後、いろいろな人たちが「スーパーマリオメーカー“上で動く計算機”」を作っていって、「加算器の桁数レース」が起こります。計算できる桁数が2ビットから16ビット、32ビット、64ビットと増えていきました。





 34ビットまで行ったところで計算機が一気に小さくなるんですけど、「【34bit】マリオメーカー計算機で171億(略)+171億(略)の結果を表示してみた」という動画で、回路の再利用が可能になる技術が広まったんですね。

 ここまでの流れが、1カ月足らずで起こりました。すごいですね。すごいんですけど、ちょっと課題もありまして。

       1|2 次のページへ

Copyright © ITmedia, Inc. All Rights Reserved.