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

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

» 2019年07月12日 12時30分 公開
[ねとらぼ]


 「マリオメーカー学会」というものをご存じでしょうか。自作ステージを作って遊べるゲーム「スーパーマリオメーカー」に斜め上過ぎる楽しみ方を見いだした“研究者”の集まりで、これまでには「クリアに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.

昨日の総合アクセスTOP10
先週の総合アクセスTOP10
  1. 「泣いても泣いても涙が」 北斗晶、“家族の死”を報告 「別れの日がこんなに急に来るなんて」
  2. 「驚愕の修理代」の金額明かす お見送り芸人しんいち、約2000万円の愛車が故障で「終わった」「お金がないです」
  3. プロ警鐘「エアコン、夏が終わったらコレやらないと……」が530万再生 水漏れや“内部のスライム化”を防ぐコツが目からウロコ
  4. “医療ミス”で両頬に大きな火傷 「鏡見るたび涙が止まらない」フォロワー24万人のモデルが悲痛の声 「周りの目が怖い」
  5. スーパーで買ったニンニクを土に植えると…… ぼこぼこ増える驚きの簡単栽培に「たくさん出来て最高」「植えてみよう」
  6. 「これは合格出せない」 リンガーハットがジョブチューン挑戦→“まさかの不合格メニュー2品”に騒然
  7. 「全く動けません」清水良太郎がフェスで救急搬送 事故動画で原因が明らかに「独りパイルドライバー」「これは本当に危ない!!」
  8. 「本当に56歳…?」 “王騎”大沢たかお、“腕と足の太さがほぼ同じ”の圧倒的肉体を披露 「かっこよすぎる」
  9. モグラに似てる“ヤベぇ虫”を、2カ月育ててみたら…… 感動の展開に「これはマジで凄い」「学術発表レベル」
  10. カインズの「撒くだけで防草できる砂」本当かどうか検証してみたら…… 驚きの結果に「魔法のような砂、買いに行きます!」「これさえあれば」
先月の総合アクセスTOP10
  1. “緑の枝付きどんぐり”をうっかり持ち帰ると、ある日…… とんでもない目にあう前に注意「危ないところだった」
  2. 「しまむら」に行った58歳父→買ってきたTシャツが“まさかのデザイン”で3万いいね! 「同じ年だから気持ちわかる」「欲しい!」
  3. 友人に「100円でもいらない」と酷評されたビーズ作家、再会して言われたのは…… 批判を糧にした作品が「もはや芸術品」と490万再生
  4. 高校3年生で出会った2人が、15年後…… 世界中が感動した姿に「泣いてしまった」「幸せを分けてくださりありがとう」【タイ】
  5. 「ま、まじか!!」 68歳島田紳助、驚きの最新姿 上地雄輔が2ショット公開 「確実に若返ってる」とネット衝撃
  6. 荒れ放題の庭を、3年間ひたすら草刈りし続けたら…… 感動のビフォーアフターに「劇的に変わってる」「素晴らしい」
  7. 食べた桃の種を土に植え、4年育てたら…… 想像を超える成長→果実を大収穫する様子に「感動しました」「素晴らしい記録」
  8. 「天才!」 人気料理研究家による“目玉焼きの作り方”が目からウロコ 今すぐ試したいライフハックに「初めて知りました!」
  9. 「エグいもん売られてた」 ホビーオフに1万1000円で売られていた“まさかの商品”に「めちゃくちゃ欲しい」
  10. 義母「お米を送りました」→思わず二度見な“手紙”に11万いいね 「憧れる」「こういう大人になりたい」と感嘆の声