theory - 图灵机不能接受的所有已知语言有哪些？

Question

例如，不接受自己编码的图灵机的语言不能被任何图灵机接受。

Answer 1

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

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

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