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

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

[ねとらぼ] PC用表示関連情報

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

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

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

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

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

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

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

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

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

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

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

　　　　　　 | 次のページへ