計算理論
(en:P′′)チューリングマシンと同様、無限長のテープに記号を記録するが、チューリングマシンにおける有限状態オートマトンに相当するものを、固定長でループの記述が可能な命令の列によって記述する。これを元に、命令セットを理論向けから実装向けに大幅にアレンジして設計されたプログラミング言語がBrainfuckである。
計算理論は、チューリングマシンより弱い(制限された)計算モデルを対象とすることもある。これらに関する理論を、「オートマトン(の)理論」と呼ぶことがある(この文脈では「オートマトン」とは、チューリングマシンより弱い(制限された)機械の総称である)。
正規表現は文字列パターンを指定するのによく使われる。また、それと等価な有限オートマトンは回路設計などに使われる。文脈自由文法はプログラミング言語の構文を定義するのに使われる。非決定性プッシュダウン・オートマトンは文脈自由文法と等価である。原始再帰関数は再帰関数のサブクラスを定義したものである。モデルが異なれば得意分野も異なる。
また、形式言語とその文法と、計算モデルとの間には対応する関係があり、計算可能性=表現力について包含関係があることが知られている。チョムスキー階層及び形式言語の階層の記事を参照のこと。