- Zahlangabeheft
- 5155
- 1
- 3
- 5
テトリスのゲーム履歴パターンを数える
@ytb_at_twt @shinimai @at_akada @iklog テトリスのゲームの履歴のパターンは「永遠に終わらない」パターンも含めた場合可算無限個?非可算?
2011-10-03 18:47:24@tiseda テトリスの盤面1つ1つに数字を対応させることができ、盤面の履歴も無限につづきうるとすれば、どのような実数に対しても、対応するテトリスの履歴を構成できるので、非可算無限個になるのではないでしょうか。 @ytb_at_twt @shinimai @iklog
2011-10-03 18:52:25@at_akada @tiseda @shinimai @iklog そうか、これが正解だ。テトリスは計算機で生成するから、テトリスで生成できるのは再帰的に定義できる自然数の無限列全体のはずです。(続)
2011-10-03 19:01:59@at_akada @tiseda @shinimai @iklog つまり、一つの実数は、それを生成する万能チューリングマシンのプログラム(自然数でコードできる)に対応するので、全部で可算個じゃないでしょうか。
2011-10-03 19:02:31@ytb_at_twt @at_akada @tiseda @iklog ゲームの履歴が何を指すのかあまりはっきりしないです
2011-10-03 19:02:30@shinimai @at_akada @tiseda @iklog とりあえず「テトリスの上の所から出てくるブロックの履歴」と受け取りました。全てのゲームの量を考える文脈では、この定義で十分では。
2011-10-03 19:04:37@ytb_at_twt あ、わたしは人間が操作する履歴も入れた状態空間を考えてました。その場合は人間の計算能力をどう考えるかにもよりますが、チューリングマシンで生成できる列にかぎる必要はないような... @shinimai @tiseda @iklog
2011-10-03 20:25:28@ytb_at_twt @at_akada @shinimai @iklog しかし、どんなピースが落ちてきても少なくとも一つは積み上がらない置き方があると仮定すると、七進数で書いた無限小数すべての集合と対応するゲーム展開が存在するはず。
2011-10-03 21:20:47@ytb_at_twt @at_akada @shinimai @iklog もしかすると、テトリスのルール上は可能だけれどもチューリングマシン上では実現できないゲーム展開が存在するということでしょうか。
2011-10-03 21:29:02@tiseda 例えばテトリス棒がω回続いたあと、別のブロックが落ちてくるというのがそうした(ルール上はありえるがチューリングマシンで生成できない)パターンのひとつでしょう。 @ytb_at_twt @shinimai @iklog
2011-10-03 21:45:41@at_akada @tiseda @shinimai @iklog 「テトリス棒がω回続いたあとに別のブロックが落ちてくる」のは、もはや超限帰納法による構成じゃないでしょうか。ですから、対応する実数(帰納的構成)は存在しないのではないかと思います。
2011-10-03 22:02:52@at_akada @shinimai @tiseda @iklog 人間の操作にはチューリングマシンで再現(シミュレート)できないようなものも含まれると仮定すると、そこに大きな差が出来そうですね。で、どうなんでしょうか。意見が分かれそうですね。
2011-10-03 22:05:45@tiseda @at_akada @shinimai @iklog ここで「無限小数全て」とはなにか、という数学の哲学でおなじみの大問題にぶち当たるわけです。この場合は計算機で再現できるゲームの履歴、という条件が入っているので、余計に条件がきつくなります。
2011-10-03 22:07:39@tiseda @at_akada @shinimai @iklog チューリングマシンでシミュレートできるゲーム履歴全体は、計算機で計算可能な実数全体の部分集合となるはずなので、可算無限となるでしょう。(続)
2011-10-03 22:10:20@tiseda @at_akada @shinimai @iklog 万能チューリングマシンのプログラムを並べます。そして、n番目のプログラムが停止する場合は1、停止しなければ0を返す関数を考えると、これは計算機で計算可能ではありません。で、テトリスのゲームで、(続)
2011-10-03 22:12:25@tiseda @at_akada @shinimai @iklog n個目のブロックとして F(n)=0 の時は棒、1のとき2×2のブロックを出すものを考えれば、このゲームは計算機が出力できず、コンピューターゲームとしては存在しないはずです。
2011-10-03 22:14:01@ytb_at_twt すいませんωを出したのが余計でした。加算無限回にすればよかったです。 @tiseda @shinimai @iklog
2011-10-03 22:07:55@ytb_at_twt あれ、十進数で0が加算無限個続いたあと1がくるような小数とかって表現できないんでしたっけ。いずれにしても、ytbさんの議論の方がスマートですが
2011-10-03 22:27:38@at_akada あらっぽい言い方をすると、無限小数は長さωで、ωは最小の可算無限順序数なので、可算無限個(≧ω)0が続いた後に1がくる無限列の長さはωより真に長くなり、もはや小数ではなくなるのではないかと思います。
2011-10-03 22:35:44@at_akada @ytb_at_twt @tiseda @iklog まあ正直言うと哲学者にゲームの話ふった結果がこの有様だよっ!っていうのが今持つべき感想ですねw
2011-10-03 22:11:42