可判定 ⟺ 可識別且共可識別（decidable iff recognizable and co-recognizable）

這是整張地圖的拱心石定理。假設你有兩位助手在找同一個字串。一位在尋找「這字串『在』語言裡」的證據，一找到就喊「是」。另一位在尋找「這字串『不在』語言裡」的證據，一找到就喊「否」。如果對每個字串，這兩場搜尋恰好有一場保證會成功，那麼同時跑這兩場，就得到一個總會回傳答案的程序。這正是把兩台單邊機器變成一台雙邊判定器的把戲。

精確的敘述：語言 L 可判定，若且唯若 L 既可識別（遞迴可枚舉）又共可識別（它的補集可識別）。一個方向很容易——L 的判定器本身就給出 L 的識別器（直接接受即可），把接受／拒絕對調就給出補集的識別器。另一個方向才是巧妙之處。設 R1 識別 L、R2 識別 L 的補集。對輸入 w，把 R1 與 R2 並行執行，交替它們的步驟（這種穿插叫做交錯執行，dovetailing）。對任何 w，R1、R2 中恰有一台最終會停機並接受：若 w ∈ L 則 R1 接受，若 w 不屬於 L 則 R2 接受。所以這台合成機器總會停機——R1 贏就接受、R2 贏就拒絕——這就是一台判定器。因此 L 可判定。

這個定理是可計算世界諸多結構背後的引擎。它解釋了為什麼一個「可識別卻不可判定」的語言（如 A_TM）的補集一定『不』可識別——否則該語言就會可判定，矛盾。它給出乾淨的三分圖像：可判定語言坐在可識別與共可識別兩類的交集裡；真正困難的語言恰好坐在其中之一；還有些語言落在兩者之外。它也是「交錯執行」之所以如此關鍵的原因：並行的耐心，把兩個部分答案合成一個完整答案。