ハイパーグラフを使用して非決定論的チューリング マシンを実装または表現することについて説明している論文、テキスト、またはその他のドキュメントを知っている人はいますか? それらは実際に同等ですか？
たとえば、ハイパーグラフは、非決定論的なチューリング マシンの状態遷移を適切かつ完全に表現できると確信しています。しかし、私はこれまでのところ、これを確認できる印刷物を見つけることができませんでした. これは明らかな関係のように思えますが、先行技術を見つけられないという事実は、私が間違った方向に進んでいると考えさせます. (私が見つけたものが、それが何を言っているのかを理解するのに十分にアクセスできない場合もあります。) ;-)
質問する理由: 私は、ピア ツー ピア ネットワークで分散データ ストレージと分散計算を行うオープン ソース パッケージに取り組んでいます。必要な機能をサポートする最も原始的なデータ構造を探しています。これまでのところ、分散型ハイパーグラフは有望に見えます。私の推論は、ハイパーグラフが非決定論的チューリング マシンと同じくらい一般的なものをサポートできる場合、より高いレベルのチューリング完全な DSL をサポートできるはずだということです。（「非決定論的」な部分が私にとっても価値があるかもしれない他の理由があり、分散データおよび/または計算結果のバージョン管理に関係しています。ただし、ここでは論文を避けようとしています。）
部分的な回答:
- opencog 関係者は、ハイパーグラフがさまざまなコンピューティング モデルにどのように適合するかについて、興味をそそる議論をしました。これはどうやら HypergraphDB パッケージの開発に関連していたようです: http://markmail.org/message/5oiv3qmoexvo4v5j
- MathOverflow では、ハイパーグラフでできることについて議論する質問があります。チューリングについてはまだ言及されていませんが、追加しようとしています: https://mathoverflow.net/questions/13750/what-are-the-applications-of -ハイパーグラフ
- ハイパーグラフが非決定論的チューリング マシンを表すことができる場合、エッジに重み付けされたハイパーグラフは確率論的チューリング マシンと同等になると思います。 http://en.wikipedia.org/wiki/Probabilistic_Turing_machine