翻訳と辞書 Words near each other ・ 交易広場 ・ 交易廣場 ・ 交易港 ・ 交易雑器 ・ 交易雑物 ・ 交替 ・ 交替 (歴史学) ・ 交替 (言語学) ・ 交替利用耕地 ・ 交替式 ・ 交替性チューリングマシン ・ 交替性チューリング機械 ・ 交替欠 ・ 交期土壌動物 ・ 交楽竜弾 ・ 交楽龍弾 ・ 交機 ・ 交款 ・ 交歓 ・ 交歓会 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 交替性チューリングマシン ： ウィキペディア日本語版 交替性チューリング機械[こうたいせいちゅーりんぐきかい] 交替性チューリング機械（こうたいせいチューリングきかい、）は、非決定性チューリング機械 (NTM) の一種であり、複雑性クラス NP および co-NP の定義で使われる規則を一般化した計算受理規則を持つ。1976年、Chandra と Stockmeyer が ATM の概念を定式化した。 == 定義 == === 概要 === NP の定義では、計算の「存在的様式 (existential mode)」が使われる。すなわち、任意の選択が受理状態に到達すれば、計算全体が受理されたことになる。co-NP の定義では、計算の「全称的様式 (universal mode)」が使われる。すなわち、全ての選択が受理状態に到達すれば、計算状態が受理されたことになる。交替性チューリング機械（より正確に言えばそのような機械における受理の定義）はこれら2つの様式を混在して利用する。 交替性チューリング機械は非決定性チューリング機械の一種であり、その状態は2つの集合、「存在的状態 (existential states)」と「全称的状態 (universal states)」に分けられる。存在的状態では、受理状態となる遷移が1つでもあれば受理される。全称的状態では、全ての遷移が受理状態となる場合にのみ受理される。従って、遷移のない全称状態は無条件で受理され、遷移のない存在状態は無条件で拒絶される。機械全体としては、初期状態が受理される場合に受理する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「交替性チューリング機械」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Alternating Turing machine 」があります。 スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.