交錯執行（dovetailing）
假設你必須跑許多計算，其中有些可能永不停止，但你不能被某一個卡住而忽略其他。最直覺的計畫——把第一個跑完，再跑第二個、第三個——一旦第一個永遠迴圈就破功：你連第二個都沒開始。交錯執行是個簡單的補救：輪流給每個計算一點時間，像雜耍者讓許多顆球同時在空中，使每個計算都有進展、沒有任何一個能獨佔時鐘。這名字來自鳩尾榫，兩塊木頭一齒一齒互相咬合。
把機制用白話拆解：要把計算 C1, C2, C3, ... 一起跑，先做 C1 的一步；再各做 C1、C2 一步；再各做 C1、C2、C3 一步；依此類推，一邊擴大批次、一邊加深步數。（常見的排程是對每一對 (i, j) 按對角線順序把 Ci 跑 j 步，所以這有時又叫對角線排程。）保證是：對任何特定的計算 Ci 和任何有限步數 k，排程中都有一個確定的時刻，此時 Ci 已被模擬至少 k 步。所以只要『任何一個』計算在有限步後停機，交錯執行的模擬就會在有限時間內見證那次停機——即使其他計算在背景永遠跑下去。
交錯執行是好幾個核心結果背後的主力。它是「用某語言的識別器與其補集的識別器造出判定器」的辦法（並行交錯地跑，必有一台停機）。它是枚舉器列出可識別語言成員的辦法：對所有字串交錯執行識別器，把每個模擬會接受的字串印出來。它也支撐了「可識別語言對聯集與交集封閉」的證明。這一個念頭——絕不讓某個可能無限的工作把其他工作餓死——正是讓「同時跑全部」成為嚴謹、尊重有限時間的技巧的關鍵。
若要在所有字串中尋找某個會被接受的輸入、而每次模擬都可能迴圈：第 1 輪，把 s1 跑 1 步；第 2 輪，把 s1、s2 各跑 2 步；第 3 輪，把 s1、s2、s3 各跑 3 步；…… 任何最終會被接受的字串，都會在某一個有限的輪次被找到。
深度漸增的輪轉：每個工作最終都會被模擬到你想要的任意深度。
交錯執行『不會』讓迴圈的計算停下來——那些永不停止的依然永不停止。它只保證：任何真的會發生的停機，你都會在有限時間內看到，而不被那些不停機的卡住。