theory - 图灵机不能接受的所有已知语言是什么？

Question

对于example，任何图灵机都不能接受不接受其自身编码的图灵机的语言。

Answer 1

TM不能决定无限多种语言。确实，“大多数”语言是不确定的。有许多可判定的语言，但有无数种语言(因此，无数许多不可判定的语言)。

赖斯定理可让您提出许多不确定的语言示例。参见维基百科页面:Rice's Theorem

基本上，如果您有一组非平凡的语言(即，有一些TM可以识别集合中的语言，而TM则可以识别集合中没有的语言)，则无法确定任意TM的语言是否在S中例如，令S为由空语言组成的集合。然后，无法确定任意TM是否接受空语言，即没有字符串。提出任何非平凡的语言集，您就会拥有一种新的不确定语言(识别该语言集的TM的所有编码)。