1テープ線形時間量子チューリング機械 : (予備的結果報告)

スポンサーリンク

概要

• 論文の詳細を見る

• 1テープ線形時間チューリング機械は極めて限定的な計算能力しか持たない。そのようなチューリング機械では、テープ上の入力文字列をコピーすることすら出来ないのである。1965年、Hennieは、計算能力において1テープ線形時間チューリング機械は有限オートマトンと等価であることを示した。本研究で、.我々は様々なタイプの1テープ線形時間チューリング機械を考察する。はじめに、古典的チューリング機械について、Hennieの結果を一般化し、1テープ線形時間の非決定論的、可逆的、そして確率的な各チューリング機械が、正則言語しか受理できないことを示す。そして、BernsteinとVaziraniによる量子チューリング機械のモデルに厳格に従いながら、あるタイプの1テープ線形時間量子チューリング機械が、非正則言語を受理できることを示す。

• 一般社団法人情報処理学会の論文
• 2002-03-15

著者

• 林 政弘

  School Of Information Technology And Engineering University Of Ottawa

• 只木 孝太郎

  中央大学21世紀COEプログラム

• 只木 孝太郎

  科学技術振興事業団創造科学技術推進事業今井量子計算機構プロジェクト

• 山上 智幸

  School of Information Technology and Engineering, University of Ottawa

• 山上 智幸

  School Of Information Technology And Engineering University Of Ottawa

関連論文

• 多次多変数型公開鍵暗号に対する持駒コンセプトの提案
• 1テープ線形時間量子チューリング機械 : (予備的結果報告)
• Chaitin's halting probability $\Omega$ and quantum measurements in an infinite dimensional quantum system (Theoretical Computer Science and its Applications)
• Kolmogorov complexity upper bound of probability in computable POVM measurement (New Aspects of Theoretical Computer Science)
• 31pSG-11 Kolmogorov complexity と POVM 測定
• 31pSG-11 Kolmogorov complexity と POVM 測定
• レモ・バディイ, アントニオ・ポリティ(著), 相澤洋二(監訳), 龍野正実, 時田恵一郎, 橋本敬, 奏浩起(訳), "複雑さの数理", 産業図書(2001-06), A5判, 定価(本体4,300円+税)

スポンサーリンク