TM能识别但TM不能决定的语言?

A language that can be recognised by a TM but cannot be decided by a TM?

TM能识别但TM不能判断的语言可以吗?

example of a language which can be recognised by a TM but cannot be decided by a TM

答案是:

 TM={<M,w> M is a TM that accepts input string w}

我会不会错了?


可判定性和可识别性有什么区别?

简而言之,任何被TM识别的字符串称为TM可识别的,而任何被TM接受的字符串称为TM可判定的。

关于您的第一个问题 - 是否存在一种 TM 可识别但 TM 不可判定的语言? - 答案是 "yes,",您给出的语言是 通用语言 ,就是这种语言的一个例子。

关于你的第二个问题 - 可判定性和可识别性之间有什么区别? - 你给出的答案是正确的,但写得不正确。请记住,可判定性和可识别性是 语言 的属性,而不是 字符串 的属性。没有 "decidable string" 或 "recognizable string."

这样的东西

如果存在具有以下属性的 TM M,则语言 L 是可判定的:对于每个字符串 w ∈ L, M 接受 w,并且对于每个字符串 w ∉ L,M 拒绝 w。换句话说,如果你不知道w是否在L中,你可以运行M on w,等它给你答案,自己去发现答案。

如果存在具有以下属性的 TM M,则语言 L 是可识别的:对于每个字符串 w ∈ L,M 接受 w,并且对于每个字符串 w ∉ L,M 不接受 w(即,M 循环 w,或者 M 拒绝 w)。换句话说,如果您确定 w ∈ L 并想确认这一点,你可以 运行 M on w,观察它接受 w,并确定你的答案是正确的,但如果你事先不知道 w 是否在 L 中,你可能不知道能够使用 M 找出答案,因为 M 可能会在 w 上循环。