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

• Item type: SIG Technical Reports(1)
• 公開日: 2002-03-15
• タイトル: 1テープ線形時間量子チューリング機械 (予備的結果報告)
• タイトル / 言語: en
• タイトル: One -Tape Linear- Time Quantum Turing Machine (Preliminary Report)
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: School of Information Technology and Engineering University of Ottawa
• 著者所属: 科学技術振興事業団創造科学技術推進事業今井量子計算機構プロジェクト
• 著者所属: School of Information Technology and Engineering University of Ottawa
• 著者所属(英): en
• 著者所属(英): School of Information Technology and Engineering, University of Ottawa
• 著者所属(英): en
• 著者所属(英): Quantum Computation and Information Project, ERATO, Japan Science and Technology Corporation
• 著者所属(英): en
• 著者所属(英): School of Information Technology and Engineering, University of Ottawa
• 著者名: 林政弘; 只木, 孝太郎; 山上, 智幸
• 著者名(英): Jack, C.H.Lin; Kohtaro, Tadaki; Tomoyuki, Yamakami
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 1テープ線形時間チューリング機械は極めて限定的な計算能力しか持たない。そのようなチューリング機械では、テープ上の入力文字列をコピーすることすら出来ないのである。1965年、Hennieは、計算能力において1テープ線形時間チューリング機械は有限オートマトンと等価であることを示した。本研究で、我々は様々なタイプの1テープ線形時間チューリング機械を考察する。はじめに、古典的チューリング機械について、Hennieの結果を一般化し、1テープ線形時間の非決定論的、可逆的、そして確率的な各チューリング機械が、正則言語しか受理できないことを示す。そして、BernsteinとVaziraniによる量子チューリング機械のモデルに厳格に従いながら、あるタイプの1テープ線形時間量子チューリング機械が、非正則言語を受理できることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: One-tape linear-time Turing machines only have very low computational power. In 1965 Hennie showed that one-tape linear-time deterministic Turing machines are computationally equal to deterministic finite automata. In this paper, we consider several types of one-tape linear-time Turing machines. By generalizing Hennie's method, it is shown that several types of classical one-tape linear-time Turing machine, i.e., nondeterministic one, reversible one, and probabilistic one, are all computationally equal to a finite automaton. In what follows, we show that a certain type of one-tape linear-time quantum Turing machine can recognize a non-regular language.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2002, 号 29(2001-AL-083), p. 1-7, 発行日 2002-03-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会