|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 非 ： [ひ] 1. (adj-na,n,pref) faulty- 2. non- ・ 決 ： [けつ] 【名詞】 1. decision 2. vote ・ 定性 ： [ていせい] 【名詞】 1. qualitative 2. stability of a substance ・ チューリング機械 ： [ちゅーりんぐきかい] (n) Turing machine ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 機 ： [き, はた] (n) loom ・ 機械 ： [きかい] 【名詞】 1. machine 2. mechanism
非決定性チューリング機械（ひけっていせいチューリングきかい、）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。 == 概要 == 通常の（決定性）チューリング機械（DTM）の遷移機構は、現在状態とテープ上のヘッドの現在位置にある記号によって次の3つの動作をする。(1)テープに記号を書き込む。(2)右または左にヘッドを移動させる。(3)新たな状態をとる。例えば、テープ上に X があって状態番号 3 であった場合、DTM は Y をテープに書き込み、ヘッドを右に移動させ、状態番号 5 に遷移する、といった具合である。 NTM が異なるのは、状態とテープ上の記号によって、すべきことがユニークに指定されないという点である。同じ状態と記号の組合せであっても、様々な動作をする可能性がある。例えば、テープ上に X があって状態番号 3 であるとき、NTM は Y を書き込んで右に移動して状態番号 5 となるかもしれないし、X を書き込んで左に移動して状態番号 3 のままとなるかもしれない。 NTM はこのような動作のうちどれを実行すべきかをどうやって「知る」のだろうか? これには2つの考え方がある。第一に非決定性チューリング機械は「最も幸運な推測機; luckiest possible guesser」であるとする考え方である。NTM は受理状態に到達することがあるならその状態に最終的に到達するような状態を常に選択して遷移する。第二に非決定性チューリング機械は多数の複製に分岐し、それぞれがとりうる遷移のいずれかを実行するとする考え方である。DTM には計算経路が1つしかないが、NTM には一種の計算の木構造が存在する。その木構造の一つの枝で受理状態で停止したとき、NTM 全体が入力を受理したと言える。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「非決定性チューリングマシン」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Non-deterministic Turing machine 」があります。 スポンサード リンク
|