圖靈歸約（Turing reduction）
/ TYOOR-ing /
映射歸約是嚴格、一次性的翻譯員：把問題翻譯一次、問一次、原封不動回報答案。圖靈歸約則放鬆了上述每一條限制。想像你獲准擁有一條通往「問題 B 專家」的魔法熱線。你想打幾次都行、想問任何自己編出來的問題都行、想怎麼組合答案都行，包括把是翻成否。圖靈歸約說：如果我有那條通往 B 的熱線，我就能解 A。
形式上，A 圖靈可歸約到 B，寫作 A <=T B，是指存在一台神諭圖靈機，它一邊判定 A，一邊向 B 的神諭發問——那是一個黑盒子，會即刻且正確地回答「x 是否屬於 B？」。與映射歸約不同，這台機器可以問許多個適應性問題（後面的問題可依賴前面的答案）、以任何邏輯組合運用結果、並對它們取否定。可判定性的轉移規則是自然的那一條：若 B 可判定且 A <=T B，則 A 可判定，因為你可以用 B 的真正判定器替換神諭。反過來讀：若 A 不可判定且 A <=T B，則 B 不可判定。所以圖靈歸約仍會傳播不可判定性。
圖靈歸約嚴格地比映射歸約更強大，而這多出來的力量有代價。由於圖靈歸約能對神諭的答案取否定，它「不」尊重可識別與不可識別之間的差別：A_TM 與其補集是圖靈等價的（給定神諭，各自都能輕易解另一個），儘管其一可識別、另一不可識別。這正是為何當你想分離可識別性類別時，必須使用較弱的映射歸約，其「是對是」的忠實保住了這個區別。圖靈歸約給出「相對於某問題可解」最一般的意涵，並支撐起不可計算性的結構，包括算術階層與相對可計算性的概念。
A_TM 的補集圖靈歸約到 A_TM：要判定「M 是否『不』接受 w」，就問 A_TM 神諭「M 是否接受 w」並回傳相反的答案。這一次取否定的查詢，對映射歸約是非法的，對圖靈歸約卻完全合法，顯示兩種歸約有別。
一條可適應性查詢、甚至可取否定的 B 神諭熱線，判定了 A：這就是 A <=T B。
圖靈歸約轉移（不）可判定性，但「不」轉移（不）可識別性，因為它可能對神諭答案取否定。要分離可識別與不可識別語言，你需要映射歸約，而非圖靈歸約。