遞迴語言（recursive language）
想像一位完美的圖書館員：不論你念出哪一本書名，他總會回來給你一個明確的「有」（我們收藏了）或「沒有」（我們沒有）——而且關鍵是，他一定會回來。你永遠不會等到天荒地老；答案保證會送達。遞迴語言就是「存在這種永不卡死的機器」的字串集合：一台圖靈機（Turing machine），對每一個可能的輸入都會停機（halt）並宣布正確的判決。這正是我們說「這件事有演算法」的數學核心。
形式地說，字母表 Σ（Sigma）上的語言 L 是遞迴的（較現代的說法是可判定的，DECIDABLE），如果存在某台圖靈機 M 是 L 的判定器（decider）：對每一個輸入字串 w，M 都會停機，並且當 w ∈ L（w 屬於 L）時恰好接受 w、當 w 不屬於 L 時恰好拒絕 w。接受與拒絕兩種結果都是停機結果，因此 M 永遠不會掉進無窮迴圈。因為這台機器總是以正確答案收場，L 就是「電腦在足夠（但有限）時間內能可靠解決」的那類問題。
這裡的「遞迴」是 1930 年代研究遞迴函數時留下的歷史用語，跟「函數呼叫自己」毫無關係；用現代白話讀就是「可判定」即可。許多自然問題都是遞迴的：判斷一個數是不是質數、判斷一個字串是否符合某個正規表示式、判斷某台 DFA 是否接受某個輸入。理論真正精彩的戲碼，是從「不是遞迴」的語言開始的——但要看清那道鴻溝，你得先有這個乾淨的概念：那些永遠有停機演算法的問題。
語言 {w : w 是某偶數的二進位寫法} 是遞迴的：一台小機器讀到最後一個位元，若是 0 就接受、若是 1 就拒絕——它總是會停機。
遞迴 = 存在某台機器，總會停機並給出正確的接受／拒絕。
「遞迴」不是指自我引用，也不是指有限——像偶數那樣的無限語言也可以是遞迴的。唯一的定義性質是：存在一台總會停機並給出正確判決的機器。