可化約性與進階不可判定性

轉移不可識別性(transferring unrecognizability)

映射歸約傳遞的不只是可判定性;它也傳遞較弱的可識別性概念——一台機器對語言中的每個字串都說是、卻可能對語言外的字串乾脆無限迴圈下去的那種性質。可識別性沿著同一根單向管傳遞:若 A <=m B 且 B 可識別,則 A 也可識別。以逆否讀之,若 A 不可識別,則 B 不可識別。翻譯員精確地保留是的答案,而那正是識別器唯一承諾的事。

機制如下。B 的識別器是一台機器 R,當且僅當輸入屬於 B 時停機並接受,對不屬於 B 的輸入則可能迴圈。若 A <=m B 由可計算的 f 實現,就建造 A 的識別器:在輸入 w 上,計算 f(w) 並對它跑 R。由於 w 屬於 A 若且唯若 f(w) 屬於 B,這台機器恰好接受 A 的字串,該迴圈時就迴圈,所以 A 可識別。反過來:若 A 已知不可識別,B 必定不可識別,否則該構造就識別了不可識別的 A。這是判定一個語言確實連識別都辦不到(而不只是不可判定)的標準做法。

關於對稱性,有一點微妙但要緊。由於映射歸約把是送到是、否送到否,它同時也給出(A 的補集)<=m(B 的補集)。所以 A <=m B 也轉移共可識別性。這個雙邊對稱正是為何分離「可識別」與「不可識別」時,正確的工具是映射歸約,而非更強的圖靈歸約。經典的收穫是:A_TM 可識別但其補集不可識別,而 A_TM 的補集正是用來透過這種轉移、把不可識別性播種到其他語言上的標準範例。

A_TM 的補集(所有 M「不」接受 w 的 (M, w) 之集合)不可識別。若你給出一個映射歸約(A_TM 的補集)<=m L,對某個語言 L 成立,那麼 L 也不可識別:一個 L 的識別器會給出一個不可識別語言的識別器,而那是不可能的。

可識別性沿映射歸約由目標流向源頭;不可識別性由源頭流向目標。

要轉移不可識別性,請用「映射」歸約,而非圖靈歸約。圖靈歸約能向神諭發問並翻轉是/否,這會破壞可識別性的轉移;映射歸約一次性、是對是的忠實,正是它奏效的原因。

又称
how reductions transfer recognizability傳遞不可識別性傳遞可識別性