算術階層（arithmetical hierarchy）

不可判定性不是單一樓層；它是一座有無窮多層的高塔，每一層都嚴格地比下一層更難。算術階層是這座塔的地圖。它依照「描述一個決定問題需要多少個交替的『對所有』與『存在』量詞」來分類，而一個問題真正需要的交替越多，它就坐得越高、越難。在入門層次，訊息很簡單：可判定之上有豐富的結構，停機問題只是往上的第一階。

塔底是可判定問題，那些有真正是非演算法的問題。往上第一層分為兩支。可識別（遞迴可枚舉，常標記為 Sigma_1）的問題，是那些能表述成「存在一個見證，使某個可判定的檢查通過」的問題，例如「M 在 w 上停機」意思是「存在一個步數，過了它之後 M 已停機」。它們的鏡像是共可識別（Pi_1）問題，用「對所有」，如「M 在每個輸入上都迴圈」。再往上爬，Sigma_2 允許「存在……對所有……」，Pi_2 允許「對所有……存在……」，依此類推；每多一次交替，就觸及一個真正全新、嚴格更大的類別。全域性問題（M 是否對所有輸入停機？）坐在 Pi_2，可證明地比停機問題本身更難。一個 r.e. 完全的問題，如停機問題，是 Sigma_1 層最難的問題，是其他每個 r.e. 問題都歸約到的標靶。

這座階層建立在相對可計算性上：每一層對應於「給定下一層的神諭，你能判定什麼」。有了停機問題神諭，你能判定更多，但隨即出現一個新的、更高的停機問題，它相對於那個神諭又不可判定，於是塔永遠往上長（這就是跳躍運算）。兩點誠實的提醒。其一，這是入門草圖；精確的理論（Tarski-Kuratowski 演算法、各層的完全性、階層的嚴格性）是研究所層級的主題。其二，別把這個「不可判定性」的階層與複雜度階層（P、NP、PSPACE）搞混：後者衡量可判定問題之間的資源，而算術階層整個位於可判定線之上，衡量不可解的程度。