タイムトラベル可能な宇宙を多項式時間内に作るには非決定性チューリングマシンが必要なのか！？

以前、私はグレッグ・イーガンさんのSF小説『クロックワーク・ロケット』の宇宙をシミュレートしようとしました。
結果出来上がったのは、自分の脳であらかじめ宇宙を作り、結果を再生するだけのプログラムという妥協の産物でした。

タイムトラベル可能な物理法則の宇宙のシミュレーション

このシミュレーションは結果としては正しいのかもしれません。
（まあ厳密に言うと、Orthogonalシリーズ３巻の最後のほうで実は宇宙がトーラスでないことがわかってしまったのでその意味で確実に間違っていますが、まあ、細かいことは抜きにして下さい）
しかし、データを作り出す作業に自分の頭を使ってしまいました。
しかしシミュレーションの精神とは、頭を使わずコンピュータを使ってお手軽簡単に世界を眺めようというものではないでしょうか！？
そういうわけで、かなり不満の残るものです。

それ以来しばらくタイムトラベル可能な物理法則の宇宙を作るにはどのくらいの計算が必要なのかについて考えていました。
この記事では、その仮説について述べます。

タイムトラベル可能な宇宙では難しい計算がすぐにすむケースがある

この記事では以前書いた以下の記事の結果を利用します。

タイムマシンコンピュータを利用してNP完全問題を多項式時間内に解く

この記事自体は、Todd A. Brunという人の論文の紹介です。
この論文の言っていることはつまり、「この宇宙では量子コンピュータを持ってしてもすぐには解けないであろう問題が、タイムトラベル可能な宇宙ではあっという間に解けてしまうだろう」、ということとだいたい同じです。

それをこっちの宇宙でシミュレートするには

これはかなりヤバイ話です。
その宇宙にいる人にとっては朗報ですが、そのような宇宙をシミュレートしようとしている私にとっては悪い知らせです。

その宇宙では難しい問題を解ける、ということはどういうことでしょう？
それはつまり、この宇宙ではそのような宇宙をシミュレートするのは難しい問題となる、という事ではないでしょうか。
なにしろ、もしそのような宇宙がこっちの宇宙で簡単にシミュレートできてしまったとしたら、その宇宙の内部で難しい問題をとけば、こっちの宇宙でも難しい問題を簡単に計算できてしまう、ということになってしまいます。
それは多分、間違いです。
この宇宙ではどうあがいても無理なことを、ほかのすごい宇宙をシミュレートしたくらいで出来るようになるとは思えません。
なにしろシミュレーション自体がこの宇宙に存在するわけですから。

もし普通のチューリングマシン（決定性チューリングマシン）しか存在できない宇宙（ライフゲームのような）の知的生命体が、量子コンピュータの存在できるこの宇宙を計算しようとしたらどうなるでしょう？
量子コンピュータをシミュレートして、その宇宙でも難しい問題がすぐに解けた！とはならないでしょう。
量子コンピュータを普通のチューリングマシンでシミュレートしなくてはならず、そのぶん計算が大変になってしまう、というのが素直な考えでしょう。

というわけで、そのシミュレーション宇宙の計算論上の素晴らしい特性は、結局こちらの宇宙のコンピュータが支えてあげなければならないのです。
つまり、タイムトラベル可能な宇宙のシミュレーションは、必然的に非決定性チューリングマシンのシミュレーションを含んでいると思われます。
（非決定性チューリングマシンは決定性チューリングマシン（現代の一般的なコンピュータ）より高性能です（理論上出来る計算は同じですが、速さが違います）。ですが、この宇宙に物理的に存在できるのかどうかはよくわかっていません）
向こうではNP完全問題が楽勝なのですからね。
こっちでその宇宙を再現するにはその問題を解かねばなりません。
そしてそれはおそらくかなり、難しいでしょう。

最低必要な計算がそのくらいだとして、では最高はどのくらいでしょう？
最悪どのくらいの計算が必要になってしまうのでしょうか？
これも非決定性チューリングマシンが多項式時間内に（比較的短い時間の間に）出来る計算の範疇で済みそうな気がします。
というのも、タイムトラベル可能といえど、局所的には各物体が物理法則に従っているかどうかの検証は簡単そうだからです。
きっと多分、多項式時間内にすんでしまうでしょう。

だから多分、タイムトラベル可能な宇宙を作る計算は、ちょうど非決定性チューリングマシンが多項式時間内に出来る計算と同じクラスなのでしょう。

疑問

情報の中に意味を見出す計算

これはタイムトラベル可能な宇宙一般に関する問題ではありませんが、少なくともOrthogonal宇宙では、宇宙内の情報の解釈には時間軸が必要な気もします。
ある観測者の時間軸では難しい問題の答えとなっているものが、別の観測者の時間軸では答えになっていない、ということも有り得そうです。

そこでちょっと気になるのが、「実はOrthogonal宇宙のシミュレーション自体は簡単だが、そこから意味のある計算結果を取り出そうとすると、無数にある観測者の中から適切なものを選ばなければならなず、その分も含めると全体として難しい計算になってしまうだけだ」という可能性です。
ちょうど円周率の中から9.11を予言するような。
塵理論のような。

もしそうなら、「Orthogonal宇宙のシミュレーションは簡単である」ということと、「Orthogonal宇宙内に非決定性チューリングマシンが存在できる」ということが両立できそうです。
もしそうだったなら、私にとってはありがたい話です。

とは言え多少時間軸が傾いた程度ではコンピュータのメモリの内容を読めなくなるなんてことも無いでしょうし、杞憂（あるいは期待し過ぎ）かもしれません。

タイムトラベル可能な宇宙に非決定性チューリングマシンは常に存在するのか？

ここまでの議論は、タイムトラベル可能な宇宙の中に知的生命体が誕生し、彼らがタイムマシンを計算に利用する事を前提としてきました。
しかし、それ以前ではどうでしょう？
宇宙がもっと小規模で、知的生命体はおろか生物すら存在できないほど、少ない物質しか存在しないケースです。

その場合は、（非決定性チューリングマシンが存在しなくても良いので）、計算のクラスが実質的にもうちょっと生ぬるいものになってくれないでしょうか？
それともやはりそんな都合の良い話はなく、知的生命体がタイムトラベルを利用した情報処理を利用しなくても、単純な物質同士のやり取りが偶然（というか自己組織化か何かで必然的に）非決定性チューリングマシンを作り出し、いずれにせよこちらの宇宙でのOrthogonal宇宙の計算は難しくなってしまうのでしょうか？
よくわかりません。

他にもいくつか疑問はあるのでもう少し考えてみたほうがよさそうですね。