喬姆斯基階層上的可判定性（decidability across the Chomsky hierarchy）

喬姆斯基階層按表達力把語言類別疊起來，像一道梯子：底層是正規語言（由有限自動機識別），往上是上下文無關語言（由下推自動機識別），頂層是遞迴可枚舉語言（由圖靈機識別），而可判定語言就藏在頂層階梯的內側。沿著這道梯子有個自然的問題：當你爬向更強的模型，你還能在『演算法上』判定語言的多少事情？答案是一個穩定而誠實的取捨——能力升，可判定性降。

就成員問題與基本結構問題來讀這道梯子：對『正規』語言，幾乎一切都可判定——成員、空語言、有限性、等價、子集、普遍性——全靠有限的狀態搜尋了結。對『上下文無關』語言，消息是好壞參半：成員可判定（CYK）、空語言可判定（可生成符號標記）、有限性可判定，但等價『不可判定』，歧義與普遍性也是。對『遞迴可枚舉』語言（圖靈機這一層），成員只是半可判定——可識別但不可判定——所以基本的接受問題 A_TM 本身就不可判定，空語言與等價也不可判定。可判定語言自成一類，嚴格地坐落在上下文無關與遞迴可枚舉之間：對補集封閉，其中每個成員問題依定義都能回答。

要帶走的教訓，是這個取捨的形狀，誠實地陳述：往上爬這道階層不是免費的——模型能表達的東西每往上一步，往往就讓你失去「最想問的那些問題」的可判定性。正規與上下文無關這兩階是世界中『溫馴』的部分，成員與空語言總會停機；出事的那條線，恰好就在「躍進到圖靈機那無界記憶」之處。本領域已經測繪了溫馴的一側；緊接著的下一個領域將顯示：頂層那些你回答不了的問題——從停機問題開始——不只是困難，而是可被證明對任何演算法都不可能。