計算のスタックモデル
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/10 20:03 UTC 版)
「スタックマシン」の記事における「計算のスタックモデル」の解説
計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。 スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。 スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。 一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる（チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。
※この「計算のスタックモデル」の解説は、「スタックマシン」の解説の一部です。
「計算のスタックモデル」を含む「スタックマシン」の記事については、「スタックマシン」の概要を参照ください。
- 計算のスタックモデルのページへのリンク
