計算可能性理論
プッシュダウン・オートマトンが受容する言語のクラスを文脈自由言語と呼び、文脈自由文法によって記述される。正規言語でないとされた 'a' と 'b' を同数含む文字列からなる言語はプッシュダウン・オートマトンで判定可能である。また一般に、プッシュダウン・オートマトンを有限状態機械のように動作させることもできるので、正規言語も判定可能である。従ってこの計算モデルは有限状態機械よりも強力である。
しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は(正規言語のときとあまり変わらないので)ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。
しかし、停止しないチューリングマシンの記述を入力として与えられたとき、それを判定するチューリングマシンが永遠に動作することを許容するなら、停止問題は一応解決する。従って、停止問題判定は帰納的可算言語である。しかし、帰納的可算ですらない言語も存在する。
そのような言語の単純な例は、停止判定の補問題である。つまり、全てのチューリングマシンとそれらが停止しない入力の全組合せからなる言語である。この言語が帰納的可算言語でないことを示すため、そのような全チューリングマシンについて停止して答えを返すチューリングマシン M {\displaystyle M} を構築することを考える。このマシンはチューリングマシンとその入力の組合せが停止する場合は永遠に動作し続ける。そして、このマシンの動作をシミュレートするチューリングマシン M ′ {\displaystyle M'} を考える。
有限状態機械に似ているが、任意のサイズに成長可能な実行スタックを利用可能である点が異なる。状態遷移の際に記号をスタックに積むかスタックから記号を除くかを指定できる。