パスワードを忘れた? アカウント作成
13958910 story
数学

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

ストーリー by hylom
ゲームを計算機化させる人達 部門より

任天堂のアクションゲーム「スーパーマリオ」シリーズのステージを作って遊んだり、オンラインで共有できるゲーム「スーパーマリオメーカー」はチューリング完全であり、「コンピュータで計算可能なものなら何でも計算できる」そうだ(吉田雄紀氏による発表スライドITmedia)。

発表ではスーパーマリオメーカー内で実装した論理演算回路や加算器の例も紹介されている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by Anonymous Coward on 2019年07月16日 14時10分 (#3652228)

    で既にやってませんでしたっけ?

    • by nim (10479) on 2019年07月16日 15時47分 (#3652284)

      minecraftは意図的に論理回路が作れるようブロックが用意されていて、
      チューリング完全になるべくしてなっている。

      ついうっかりチューリング完全になってしまった他のアレやコレやとは違う。

      親コメント
    • by Anonymous Coward on 2019年07月16日 14時20分 (#3652233)

      minecraftとスーパーマリオメーカーが同じソフトウェアに見えるんですか?

      親コメント
      • by Anonymous Coward

        クリエイト系ゲームで同様な試みは今までにもあったのに
        わざわざ「スーパーマリオメーカー」として取り上げる理由が見当たらなかったので
        今までの試みを超える何かが有るなら是非知りたいです

        • by Anonymous Coward

          クリエイト系ゲームで同様な試みは今までにもあったなら
          わざわざ「スーパーマリオメーカー」だけ無視する理由も無いし
          別に取り上げたっていいのでは?

          • by Anonymous Coward

            ソニータイトルのリトルビッグプラネットを取り上げないのは差別だ!特定メーカーへの肩入れだ!
            と思ったら計算機ネタで取り上げられてたわ。失敬。

        • by Anonymous Coward

          新しいフィールドで計算万能性を示せれば、まあ一応結果だよ
          未知なパズルの解法がNP完全だってだけでも一応発表の価値ありな結果なのと同じように

      • by Anonymous Coward

        チューリング等価ではあるな

    • by Anonymous Coward

      1次元セルオートマトンとか、ライフゲームとかでも既出です。

      倉庫番とかテトリスとかぷよぷよはチューリング完全じゃなくNP困難だったかな…。

    • by Anonymous Coward

      リトルビッグプラネットでも同じネタがありましたね
      頑張って探せば動画も出てくるはず

  • by Anonymous Coward on 2019年07月16日 14時28分 (#3652241)

    動画でくれ…と思ったけどスライドは紹介みたいなもんで、実際はニコニコ動画で競争みたいなのが起きてるみたいね。
    まぁできるだろうな、という感想。
    でもよくやるわ。いろんなゲームであるね。
    自分が最初にこの手のを見たのはリトルビッグプラネットだけど多分そのはるか前からあるんだろう。

    この手のチューリング完全って入力をステージ内で表現しないと行けなかったりするのがちょっと違和感あるが、実際計算できてる上に計算機の定義からすればこっちのが正しいんだろうな。

    • by Anonymous Coward

      2年前からあるね。
      http://embed.nicovideo.jp/watch/sm30573682 [nicovideo.jp]

      • by Anonymous Coward

        ていうかこのスライドを発表した当人だね。
        なぜ今ごろになってもう一度発表したかというと、マリオメーカー2が発売されて再び盛り上がったタイミングに合わせたってことかな。

        • by Anonymous Coward

          身も蓋もない言い方をすれば販促、宣伝、ステマ

      • by Anonymous Coward

        この手の本来の用途じゃないチューリング完全は、
        プラットフォームとしてはライフゲームが最古争いしてるくらいだと思う。

  • by Anonymous Coward on 2019年07月16日 15時16分 (#3652262)

    チューリング完全にしない工夫をしなければ勝手にチューリング完全になる
    みたいな定理ありそう

    • by Anonymous Coward

      そりゃチューリング完全になる字母の組み合わせは無数にあるわけだし、ルールを追加するとそのうち踏むわな。

    • by Anonymous Coward

      複雑系科学の分野よな。
      研究が進めば、
      「〇〇係数がxxを超えたから、うーん、これはチューリング完全!」
      とか何か、そういう量子化の手法が見つかったり
      「この系はまだチューリング完全ではないが、あと一つ、〇〇みたいなルールを設けたら完全になる」
      みたいな事も計算で求まったりするのかな。

  • by Anonymous Coward on 2019年07月16日 15時38分 (#3652276)

    変数を扱えて、条件判断とループができればOKだっけ?

    • 何らかのプログラミング言語を作成できればチューリング完全だと思ってた
      言われてみればifとforだけあれば十分ですね
      初代ポケモン黄もチューリング完全らしい
      親コメント
    • by Anonymous Coward

      「無限にメモリが増やせれば…」というのが絶対条件。現実世界の事物について「〇〇はチューリング完全」という場合、よく見ると「××が無限ならば」みたいな条件が必ずついている。C言語は安易にメモリを無限にすると言語仕様に違反してしまうので、工夫しないとチューリング完全にならないとかある。

      • by Anonymous Coward

        元ネタはパンチカード(穿孔テープ)なんだから、別にメモリである必要はないだろ。C言語でパンチカードに入出力できたらそれで充分。

        • by Anonymous Coward

          シリコン上のRAMである必要はないけど、無限に容量があって(シーケンシャルアクセスでもいいから)必要とあればどこまでも読みに戻れるという条件は必要。
          C言語の規格上、シーク可能なファイルのサイズは有限でなければならないのでそんな簡単じゃないんだな

        • by Anonymous Coward

          C言語の仕様にパンチカード操作は用意されていないので、C言語に「無限に長いテープを操作できる仕組み」という条件を加えたらチューリング完全、という風に話を持って行かざるを得ないんじゃないかな。

          で、それを加えるのは「無限メモリ」の但し書きを加えるのよりマシなのか? と言う話になる。

          まあ、「標準入出力が無限テープエミュレータに繋いである環境」を想定すれば、C言語の仕様そのものは汚さずに済むからマシなのかな。

          無限テープエミュレータは、"r"を渡すと現在位置の値がを返し、"w(値)"を渡すと現在位置を"値"に書き換え、"b"と"f"で進んだり戻ったり、というような想定で。どこまで進んだり戻ったりしても、何かしら上手いことやってくれるマジカルなプログラム。

          • by Anonymous Coward

            テープはrでwでbなシーク可能のファイルハンドルで良いじゃん。
            まぁぶっちゃけ適当な配列とポインタないしインデックスで十分だけどね。
            実際問題無限のテープを現実に用意することは物理的にできないから、
            「物理的制約によりテープ長はNまでとする」てのは絶対に生じる。
            であればそのNに大した意味はなくテキトーな定数で良い。

            実際問題ゲームワールド内でやる奴もエリアサイズやオブジェクト数の上限があるしね。

    • by Anonymous Coward

      数学的には、任意のチューリングマシンをエミュレート出来れば、チューリング完全。
      チューリングマシンの仕様をデータ列の形で与えることで任意のチューリングマシンをエミュレート出来る、ユニバーサルチューリングマシンというのが有るので、それを実装できればチューリング完全、というのが話が早い。

  • by Anonymous Coward on 2019年07月16日 19時49分 (#3652440)

    論理演算ブロックみたいなのを作るより、
    いっそマクロブロックとか作って、
    javascript風マクロを実行できるようにすればいい

    • by Anonymous Coward

      実際にスペースエンジニアって言うゲームでC#を使えた記憶があります。

      • by Anonymous Coward

        実際に開発に使っている様な言語だと、何か有った時に怖くないか?

        • by Anonymous Coward

          実用的な言語である事と、その標準ライブラリの機能がフルに使えることは話が別。ライブラリ中の許可されていない無い機能を呼び出そうとすると例外になるようなサンドボックス化しておけば問題ない。

          C#とかJavaとかはまさにその辺りをアピールポイントの1つにしていて、最初期の頃に安全だとアピールするためのプログラミングコンテストが開かれてた。確か、その言語で書いた仮想生物とかロボのプログラムを投稿しろ、そのプログラムをサーバで動かして最強を決めてやるから、というような。ファイルを何か書き換えて最強化とか、ネットに繋いで遠隔操作とか

  • by Anonymous Coward on 2019年07月16日 20時26分 (#3652454)

    スーパーマリオメーカーでエニグマ暗号を解読したらすごい

    # 新50ポンド札にアラン・チューリング コンピューターやAIの先駆者
    https://www.bbc.com/japanese/48991921 [bbc.com]

typodupeerror

にわかな奴ほど語りたがる -- あるハッカー

読み込み中...