キューオートマトン

キューマシン、キューオートマトン、またはプルアップオートマトン（PUA）^[要出典]は、無限メモリのキューにデータを格納および取得する機能を備えた有限状態機械です。その設計はプッシュダウンオートマトンに似ていますが、スタックをこのキューに置き換えている点が異なります。キューマシンはチューリングマシンと等価な計算モデルであり、したがって同じクラスの形式言語を処理できます。

理論

キューマシンは6つのタプルとして定義できる

M=(Q,\Sigma ,\Gamma ,\$,s,\delta )

どこ

$\,Q$ は有限の状態集合である。
$\,\Sigma \subset \Gamma$ は入力アルファベットの有限集合です。
$\,\Gamma$ 有限キューアルファベットです。
$\,\$\in \Gamma \setminus \Sigma$ は初期キューシンボルです。
$\,s\in Q$ 開始状態です。
$\,\delta :Q\times \Gamma \rightarrow Q\times \Gamma ^{*}$ は遷移関数です。

マシン構成とは、その状態とキューの内容の順序付きペアであり、はのクリーネ閉包を表します。入力文字列における開始構成はと定義され、ある構成から次の構成への遷移はと定義されます。 $\,(q,\gamma )\in Q\times \Gamma ^{*}$ $\,\Gamma ^{*}$ $\,\Gamma$ $\,x$ $\,(s,x\$)$ $\rightarrow _{M}^{1}$

\,(p,A\alpha )\rightarrow _{M}^{1}(q,\alpha \gamma )

ここで、はキューのアルファベットの記号、はキューの記号の列 ( )、です。関係式におけるキューの「先入れ先出し」特性に注意してください。 $A$ $\alpha$ $\alpha \in \Gamma ^{*}$ $(q,\gamma )=\delta (p,A)$

機械は、有限回数の遷移の後に、初期構成が文字列を使い尽くす（ヌル文字列に到達する）まで進化した場合、またはそうでなければ、^[1] $\,x\in \Sigma ^{*}$ $\,\epsilon$ $\,(s,x\$)\rightarrow _{M}^{*}(q,\epsilon ).$

チューリング完全性

キューマシンがチューリングマシンをシミュレートできること、またその逆も可能であることを示すことによって、キューマシンがチューリングマシンと同等であることを証明できます。

チューリングマシンは、キューマシンでシミュレートできます。キューマシンは、チューリングマシンのコンテンツのコピーを常にキューに保持し、2 つの特別なマーカー (チューリングマシンのヘッド位置用とテープ終了用) を使用します。キューマシンの遷移は、キュー全体を実行し、各シンボルをポップして、ポップされたシンボルまたはヘッド位置の近くでチューリングマシンの遷移の効果と同等のものを再度キューに追加することで、チューリングマシンの遷移をシミュレートします。

キューマシンはチューリングマシンでシミュレートできますが、マルチテープチューリングマシンの方がより容易です。マルチテープチューリングマシンは通常のシングルテープマシンと等価であることが知られています。シミュレートするキューマシンは、1つのテープから入力を読み取り、2つ目のテープにキューを保存します。プッシュとポップは、テープの先頭と末尾のシンボルへの単純な遷移によって定義されます。^[2]この正式な証明は、理論計算機科学の授業で演習として扱われることがよくあります。

アプリケーション

キューマシンは、コンピュータアーキテクチャ、^[3]^[4] プログラミング言語、またはアルゴリズムのベースとなる単純なモデルを提供します。^[5]^[6]

参照

計算可能性
チューリングマシン相当物
決定性有限オートマトン
タグシステム
Manufactoria は、キューマシンモデルを使用してさまざまなアルゴリズムを実装することをプレイヤーに課すブラウザーフラッシュゲームです。

参考文献

^ Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider (編). Automata and Computability (ハードカバー). Undergraduate Texts in Computer Science (第1版). New York: Springer-Verlag. pp. 368–370. ISBN 978-0-387-94907-9。
^ Rus, Teodor. 「チューリングマシンの変種」（PDF） .計算理論に関する講義ノート.アイオワ大学, アイオワシティ, アイオワ州, 52242-1419. オリジナル（PDF）から2008年9月21日にアーカイブ。 2007年11月6日閲覧。
^ Feller, M.; MD Ercegovac (1981). 「キューマシン：並列計算のための構成」. Conpar 81.コンピュータサイエンス講義ノート. 第111巻. pp. 37– 47. doi :10.1007/BFb0105108. ISBN 978-3-540-10827-6。
^ Schmit, H.; Levine, B.; Ylvisaker, B. (2002). 「キューマシン：ハードウェア内ハードウェアコンパイル」. Proceedings. 第10回IEEEフィールドプログラマブルカスタムコンピューティングマシンシンポジウム. pp. 152– 160. CiteSeerX 10.1.1.6.7718 . doi :10.1109/FPGA.2002.1106670. ISBN 978-0-7695-1801-5. S2CID 8993845。
^ Moore, Christopher (1999年9月20日). 「キュー、スタック、そしてカオスへの遷移における超越性」.アルゴリズム・プロジェクト・セミナー. INRIA . 2007年11月6日閲覧。
^ von Thun, Manfred (2007). 「式を評価するためのキューマシン」.ラ・トローブ大学. 2007年8月7日時点のオリジナルよりアーカイブ。 2007年11月6日閲覧。

[1] Kozen, Dexter C. (1997) [1951]. David Gries, Fred B. Schneider (編). Automata and Computability (ハードカバー). Undergraduate Texts in Computer Science (第1版). New York: Springer-Verlag. pp. 368–370. ISBN 978-0-387-94907-9。

[2] Rus, Teodor. 「チューリングマシンの変種」（PDF） .計算理論に関する講義ノート.アイオワ大学, アイオワシティ, アイオワ州, 52242-1419. オリジナル（PDF）から2008年9月21日にアーカイブ。 2007年11月6日閲覧。

[3] Feller, M.; MD Ercegovac (1981). 「キューマシン：並列計算のための構成」. Conpar 81.コンピュータサイエンス講義ノート. 第111巻. pp. 37– 47. doi :10.1007/BFb0105108. ISBN 978-3-540-10827-6。

[4] Schmit, H.; Levine, B.; Ylvisaker, B. (2002). 「キューマシン：ハードウェア内ハードウェアコンパイル」. Proceedings. 第10回IEEEフィールドプログラマブルカスタムコンピューティングマシンシンポジウム. pp. 152– 160. CiteSeerX 10.1.1.6.7718 . doi :10.1109/FPGA.2002.1106670. ISBN 978-0-7695-1801-5. S2CID 8993845。

[5] Moore, Christopher (1999年9月20日). 「キュー、スタック、そしてカオスへの遷移における超越性」.アルゴリズム・プロジェクト・セミナー. INRIA . 2007年11月6日閲覧。

[6] von Thun, Manfred (2007). 「式を評価するためのキューマシン」.ラ・トローブ大学. 2007年8月7日時点のオリジナルよりアーカイブ。 2007年11月6日閲覧。