リバーサル計算量上でのATMとNTM間の能力の比較

山本 博章  野口 正一  

誌名
電子情報通信学会論文誌 D   Vol.J68-D   No.5   pp.1019-1026
発行日: 1985/05/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: アルゴリズム,計算複雑性
キーワード: 


本文: PDF(681.2KB)
>>論文を購入


あらまし: 
ATM(alternating Turing machine)のリバーサル計算量について調べ,次の結果を得る.第1に,任意の帰納的可算集合は1テープ1カウンタATMによって定数回のリバーサル数(ヘッドのターンの回数)で受理されるが,リバーサル数が定数回に制限された1テープ1カウンタNTM(nondeterministic TM)によっては受理されない.ここで,1テープ1カウンタTMとは1本のカウンタテープと1本の入力/記憶テープを持つTMのことである.第2に,ある条件を満足する2つの関数Rn),Bn)に対し,リバーサル数と葉数が同時にそれぞれRn),Bn)に制限された1テープATMによって受理される言語のクラスと領域がRn)*Bn)に制限されたNTMによって受理される言語のクラスとは等価である.