calendar

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526272829
30      
<< September 2018 >>

categories

blog ranking

ブログランキング・にほんブログ村へ
にほんブログ村 哲学・思想ブログへ
にほんブログ村 哲学・思想ブログ 哲学へ
にほんブログ村 科学ブログへ
にほんブログ村 科学ブログ 物理学へ
にほんブログ村 科学ブログ 技術・工学へ

archives

非決定性チューリングマシン

あなたは、どれだけ先の未来を予知したいですか。大地震の予知なら少なくとも1時間先、社会情勢の予知ならさらに先の未来を予知したいですよね。こう考えると、長時間先の予知はタイムコミュニケーションの重要な目標であることに間違いありません。


しかし一方、短時間先の予知が意味を持つ分野があります。それは、計算の分野です。


例えば、2の100乗個の解候補の中から1個の正解を見つけ出す場合を考えてみます。その場合、まず、解候補を2の99乗個のグループに2分して、どちらに正解があるかを予知します。次に、正解の入ったグループを2の98乗個のグループに2分して、どちらに正解があるかを予知します。このような予知を100ステップ繰り返せば、最終的に正解にたどりつけるでしょう。逆に、タイムコミュニケーションの情報伝達に沿って言えば、まず、1個の正解を確認した時点から、各1個からなる解候補の中から正解を選択する時点へ正解信号を送信します。つぎに、各1個からなる解候補の中から正解を選択した時点から、各2個からなる解候補グループの中から正解グループを選択する時点に正解信号を送信します。さらに、各2個からなる解候補グループの中から正解グループを選択した時点から、各4個からなる解候補グループの中から正解グループを選択する時点に正解信号を送信します。このような通信を100回行えば、グループ選択前の各時点に選択すべき正解グループを知らせることができます。このような解探索システムは、非決定性チューリングマシンとよばれているシステムに他なりません。下図は、簡単のために解候補を8個にした非決定性チューリングマシンの概念図です。


ntm

仮に、タイムコミュニケーションの1ステップが10マイクロ秒だとしましょう。すると、タイムコミュニケーションを用いた非決定性チューリングマシンは、2の100乗の解候補の中からおよそ1 ミリ秒で、すなわち一瞬で、正解を見つけ出すことができます。一方もし、しらみつぶしに正解を見つけるとしたら、仮に1回の確認が2の-39乗秒で済むとしても、正解にたどり着くまでに平均2の60乗秒かかります。つまり、365億5890万年という非現実的な計算時間を要することになります。

(つづく)



コメント
コメントする








   
この記事のトラックバックURL
トラックバック