翻訳と辞書
Words near each other
・ 非毒性
・ 非民主
・ 非水性懸濁液
・ 非水溶媒
・ 非水滴定
・ 非水相
・ 非水系重合
・ 非永続伝搬
・ 非求核塩基
・ 非決定性チューリングマシン
非決定性チューリング機械
・ 非決定性卵割
・ 非決定性時間
・ 非決定性有限オートマトン
・ 非法人地域
・ 非法集會
・ 非洲
・ 非活動
・ 非活動(性)萎縮、無動(性)萎縮、廃用萎縮、不(使)用萎縮
・ 非活動ウィンドウ


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

非決定性チューリング機械 : ミニ英和和英辞書
非決定性チューリング機械[ひ]
=====================================
〔語彙分解〕的な部分一致の検索結果は以下の通りです。

: [ひ]
  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 」があります。




スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.