しかし、この観測された明白な違いはどういう意味で正確なのか？ ある特定の問題をコンピュータで解く際の困難さの度合いを定式化し定義できるか？ その質問に答えるのが計算可能性理論の目標である。
計算の形式モデル.
計算可能性理論の中心課題に答えるために、「コンピュータとは何か」を形式的に定義する必要がある。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。
計算モデルの能力.
これらの計算モデルについて、その限界を定めることができる。すなわち、どのクラスの形式言語をその計算モデルは受容するか、である。
有限状態機械の能力.
有限状態機械が受容する言語のクラスを正規言語と呼び、正規文法で記述される。有限状態機械が持つことができる状態は有限個であるためであり、正規言語でない言語を扱うには無限の状態数を扱える必要がある。
従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。
この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。
プッシュダウン・オートマトンの能力.
しかし、プッシュダウン・オートマトンでも判定できない言語がある。その詳細は（正規言語のときとあまり変わらないので）ここでは述べない。文脈自由言語の反復補題も存在する。例えば、素数の集合からなる言語がその例である。
チューリングマシンの能力.
チューリングマシンは任意の文脈自由言語を判定できるだけでなく、プッシュダウン・オートマトンが判定できない言語（例えば素数の集合からなる言語）も判定可能である。したがってチューリングマシンはさらに強力な計算モデルと言うことができる。