計算可能性理論
有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。
正規言語でない言語の例として、文字 'a' と 'b' から構成され、各文字列に必ず 'a' と 'b' が同数含まれている言語がある。この言語が有限状態機械で認識できない理由を調べるため、まずこの言語を受容するための有限状態機械 M {\displaystyle M} があるとする。 M {\displaystyle M} は n {\displaystyle n} 個の状態を持つとする。ここで、文字列 x {\displaystyle x} が ( n + 1 ) {\displaystyle (n+1)} 個の 'a' の後に ( n + 1 ) {\displaystyle (n+1)} 個の 'b' があるような構成であるとする。
M {\displaystyle M} の状態数は n {\displaystyle n} しかないため、 x {\displaystyle x} を入力としたときに最初の 'a' が連続する部分の長さが ( n + 1 ) {\displaystyle (n+1)} であることから、鳩の巣原理により、何らかの状態を繰り返すことになる。 ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだ状態 S {\displaystyle S} が 'a' を d {\displaystyle d} 個読み込んだ時に再度現われるとする( d > 0 {\displaystyle d>0} とする)。
チャーチ=チューリングのテーゼでは、チューリングマシンよりも強力な計算モデルは存在しないと推測した。ここでは、その推定に反する「不合理」な計算モデルの例をいくつか示す。計算機科学者は様々な「ハイパーコンピュータ」を想像してきた(ここでいうハイパーコンピュータとは、スーパーコンピュータのさらに高性能なものという意味ではない)。