スーパーマリオメーカーはチューリング完全 31
ストーリー by hylom
ゲームを計算機化させる人達 部門より
ゲームを計算機化させる人達 部門より
任天堂のアクションゲーム「スーパーマリオ」シリーズのステージを作って遊んだり、オンラインで共有できるゲーム「スーパーマリオメーカー」はチューリング完全であり、「コンピュータで計算可能なものなら何でも計算できる」そうだ(吉田雄紀氏による発表スライド、ITmedia)。
発表ではスーパーマリオメーカー内で実装した論理演算回路や加算器の例も紹介されている。
minecraft (スコア:0)
で既にやってませんでしたっけ?
Re:minecraft (スコア:2)
minecraftは意図的に論理回路が作れるようブロックが用意されていて、
チューリング完全になるべくしてなっている。
ついうっかりチューリング完全になってしまった他のアレやコレやとは違う。
Re:minecraft (スコア:1)
minecraftとスーパーマリオメーカーが同じソフトウェアに見えるんですか?
Re: (スコア:0)
クリエイト系ゲームで同様な試みは今までにもあったのに
わざわざ「スーパーマリオメーカー」として取り上げる理由が見当たらなかったので
今までの試みを超える何かが有るなら是非知りたいです
Re: (スコア:0)
クリエイト系ゲームで同様な試みは今までにもあったなら
わざわざ「スーパーマリオメーカー」だけ無視する理由も無いし
別に取り上げたっていいのでは?
Re: (スコア:0)
ソニータイトルのリトルビッグプラネットを取り上げないのは差別だ!特定メーカーへの肩入れだ!
と思ったら計算機ネタで取り上げられてたわ。失敬。
Re: (スコア:0)
新しいフィールドで計算万能性を示せれば、まあ一応結果だよ
未知なパズルの解法がNP完全だってだけでも一応発表の価値ありな結果なのと同じように
Re: (スコア:0)
チューリング等価ではあるな
Re: (スコア:0)
1次元セルオートマトンとか、ライフゲームとかでも既出です。
倉庫番とかテトリスとかぷよぷよはチューリング完全じゃなくNP困難だったかな…。
Re: (スコア:0)
リトルビッグプラネットでも同じネタがありましたね
頑張って探せば動画も出てくるはず
動画でくれ (スコア:0)
動画でくれ…と思ったけどスライドは紹介みたいなもんで、実際はニコニコ動画で競争みたいなのが起きてるみたいね。
まぁできるだろうな、という感想。
でもよくやるわ。いろんなゲームであるね。
自分が最初にこの手のを見たのはリトルビッグプラネットだけど多分そのはるか前からあるんだろう。
この手のチューリング完全って入力をステージ内で表現しないと行けなかったりするのがちょっと違和感あるが、実際計算できてる上に計算機の定義からすればこっちのが正しいんだろうな。
Re: (スコア:0)
2年前からあるね。
http://embed.nicovideo.jp/watch/sm30573682 [nicovideo.jp]
Re: (スコア:0)
ていうかこのスライドを発表した当人だね。
なぜ今ごろになってもう一度発表したかというと、マリオメーカー2が発売されて再び盛り上がったタイミングに合わせたってことかな。
Re: (スコア:0)
身も蓋もない言い方をすれば販促、宣伝、ステマ
Re: (スコア:0)
この手の本来の用途じゃないチューリング完全は、
プラットフォームとしてはライフゲームが最古争いしてるくらいだと思う。
十分に複雑なルールは (スコア:0)
チューリング完全にしない工夫をしなければ勝手にチューリング完全になる
みたいな定理ありそう
Re: (スコア:0)
そりゃチューリング完全になる字母の組み合わせは無数にあるわけだし、ルールを追加するとそのうち踏むわな。
Re: (スコア:0)
複雑系科学の分野よな。
研究が進めば、
「〇〇係数がxxを超えたから、うーん、これはチューリング完全!」
とか何か、そういう量子化の手法が見つかったり
「この系はまだチューリング完全ではないが、あと一つ、〇〇みたいなルールを設けたら完全になる」
みたいな事も計算で求まったりするのかな。
チューリング完全の条件って (スコア:0)
変数を扱えて、条件判断とループができればOKだっけ?
Re:チューリング完全の条件って (スコア:1)
言われてみればifとforだけあれば十分ですね
初代ポケモン黄もチューリング完全らしい
Re: (スコア:0)
「無限にメモリが増やせれば…」というのが絶対条件。現実世界の事物について「〇〇はチューリング完全」という場合、よく見ると「××が無限ならば」みたいな条件が必ずついている。C言語は安易にメモリを無限にすると言語仕様に違反してしまうので、工夫しないとチューリング完全にならないとかある。
Re: (スコア:0)
元ネタはパンチカード(穿孔テープ)なんだから、別にメモリである必要はないだろ。C言語でパンチカードに入出力できたらそれで充分。
Re: (スコア:0)
シリコン上のRAMである必要はないけど、無限に容量があって(シーケンシャルアクセスでもいいから)必要とあればどこまでも読みに戻れるという条件は必要。
C言語の規格上、シーク可能なファイルのサイズは有限でなければならないのでそんな簡単じゃないんだな
Re: (スコア:0)
C言語の仕様にパンチカード操作は用意されていないので、C言語に「無限に長いテープを操作できる仕組み」という条件を加えたらチューリング完全、という風に話を持って行かざるを得ないんじゃないかな。
で、それを加えるのは「無限メモリ」の但し書きを加えるのよりマシなのか? と言う話になる。
まあ、「標準入出力が無限テープエミュレータに繋いである環境」を想定すれば、C言語の仕様そのものは汚さずに済むからマシなのかな。
無限テープエミュレータは、"r"を渡すと現在位置の値がを返し、"w(値)"を渡すと現在位置を"値"に書き換え、"b"と"f"で進んだり戻ったり、というような想定で。どこまで進んだり戻ったりしても、何かしら上手いことやってくれるマジカルなプログラム。
Re: (スコア:0)
テープはrでwでbなシーク可能のファイルハンドルで良いじゃん。
まぁぶっちゃけ適当な配列とポインタないしインデックスで十分だけどね。
実際問題無限のテープを現実に用意することは物理的にできないから、
「物理的制約によりテープ長はNまでとする」てのは絶対に生じる。
であればそのNに大した意味はなくテキトーな定数で良い。
実際問題ゲームワールド内でやる奴もエリアサイズやオブジェクト数の上限があるしね。
Re: (スコア:0)
数学的には、任意のチューリングマシンをエミュレート出来れば、チューリング完全。
チューリングマシンの仕様をデータ列の形で与えることで任意のチューリングマシンをエミュレート出来る、ユニバーサルチューリングマシンというのが有るので、それを実装できればチューリング完全、というのが話が早い。
クリエイト系ゲームにもマクロ導入すればいいのに (スコア:0)
論理演算ブロックみたいなのを作るより、
いっそマクロブロックとか作って、
javascript風マクロを実行できるようにすればいい
Re: (スコア:0)
実際にスペースエンジニアって言うゲームでC#を使えた記憶があります。
Re: (スコア:0)
実際に開発に使っている様な言語だと、何か有った時に怖くないか?
Re: (スコア:0)
実用的な言語である事と、その標準ライブラリの機能がフルに使えることは話が別。ライブラリ中の許可されていない無い機能を呼び出そうとすると例外になるようなサンドボックス化しておけば問題ない。
C#とかJavaとかはまさにその辺りをアピールポイントの1つにしていて、最初期の頃に安全だとアピールするためのプログラミングコンテストが開かれてた。確か、その言語で書いた仮想生物とかロボのプログラムを投稿しろ、そのプログラムをサーバで動かして最強を決めてやるから、というような。ファイルを何か書き換えて最強化とか、ネットに繋いで遠隔操作とか
チューリングに敬意を評して (スコア:0)
スーパーマリオメーカーでエニグマ暗号を解読したらすごい
# 新50ポンド札にアラン・チューリング コンピューターやAIの先駆者
https://www.bbc.com/japanese/48991921 [bbc.com]