图灵机无法接受的所有已知语言是什么？

Question

对于例如,图灵机的不接受自己的编码语言不能被任何图灵机接受.

Answer 1

有无数种语言是 TM 无法决定的。事实上，“大多数”语言都是不可判定的。有可数的可判定语言，但不可数的语言（因此，不可数的不可判定的语言）。

赖斯定理允许你想出许多不可判定语言的例子。请参阅维基百科页面：赖斯定理

基本上，如果您有一组非平凡的语言（即，有识别集合中语言的 TM，以及识别不在集合中的语言的 TM），则无法确定任意 TM 的语言是否属于 S . 例如，设 S 是由空语言组成的集合。那么就无法确定任意 TM 是否接受空语言，即没有字符串。想出任何非平凡的语言集，你就有了一个新的不可判定的语言（所有 TM 的编码在集合中识别语言）。