確率的Turing Machine
Probabilistic Turing Machine(PTM): 現在の状態と入力記号に対して、次の動作が確率的に決定されるもの。考え方としては、非決定性Turing Machineの同一の入力に対する遷移関数が複数あり、どの遷移関数が選ばれるかという確率が付随しているもの。
1bitのPTMを考える： テープは１マスしかなく、左右には動けない。状態は状態０、状態１の二つ。状態０はテープのマスの内容が0の状態、状態１は1の時の状態に対応する。マスの内容が入力となるため、それぞれ入力は0,1になる。
このptmでは次のような計算木を構築することができる。
PTMの計算木は以下の三つの条件を満たさなければならない。
1. 計算木の同じラベルを持つノードは、辺の枝分かれの仕方が同一である
2. 計算木の親から子への辺は、ＰＴＭで実現可能な遷移に対応していなくてはならない
3. 各レベルにおいて、ノードの発生確率の合計は常に１でなくてはならない。
この機械では初期状態が0であるとき、2単位時間が経過した後の状態は、0である可能性が(1/4+1/6)で、1である可能性が(1/4+1/3)の重ねあわせの状態になる。
各状態は確率的に決まる。これは、状態ベクトルで表される。
v0は状態0をあらわし、v1は状態1をあらわす。
状態遷移は次の行列で表される。
行列Aの第i行第j列成分は、Pが「状態j-1」から「状態i-1」に遷移する確率を示す。
状態遷移行列の各列の合計は1にならなくてはならない。
上の計算木と比較し、level2における各状態の確率と正しいことを確認すること。すなわち状態0である確率が1/4+1/6=5/12であり、状態１である確率が1/4+1/3=7/12であること。
トラックバック(0)
このブログ記事を参照しているブログ一覧: 確率的Turing Machine
このブログ記事に対するトラックバックURL: http://www.imaq.net/cgi-bin/mt/mt-tb.cgi/195
突然どうしたの？
ところでいまちゃん、いまちゃんサーバーはどこにあるの？このサーバーのことを言ってる訳じゃないけど、大学にサーバーおいてるBlogでアマゾンとかのアフィリエイトってやっていいのかな。みんなやってる？やってない？聞きたかっただけ。
結構前から計算論関連勉強してて、最近量子コンピュータ勉強してるところ。昔からオートマトン理論とか好きだったし。
うんと、サーバは自宅です。別に宣伝している気はなくて、単なる自分の日記なので。。。
いや、もちろんamazonが本をただで送ってくれるならば、もっと書きますよ：）
でも、やめたほうがいいかな。なんとなくあそこのレビューも見れたほうがいいかと思ってやっていたのですが。
とりあえず今後止めることにしました。