一种能被TM识别但不能由TM决定的语言？

Question

一种能被TM识别但不能由TM决定的语言可以吗？

一种语言的例子，该语言可以被商标识别，但不能由商标决定

答案是：

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

我可能错了吗？

可判定性和可识别性之间的区别是什么？

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

Answer 1

对于你的第一个问题--是否有一种语言可以被商标识别，但不能被商标识别？--答案是“是的”，而你给出的语言，即通用语言，就是这种语言的一个例子。

关于你的第二个问题--可分辨性和可识别性之间的区别是什么？--你给出的答案是正确的，但它写得不正确。记住，可判定性和可识别性是语言的属性，而不是字符串。没有“可判定字符串”或“可识别字符串”这样的东西。

如果有一个具有以下属性的TM M，则语言L是可判定的:对于每一个字符串w∈L，M接受w，对于每一个字符串w∉L，M拒绝w。换句话说，如果你不知道w是否在L中，你可以在w上运行M，等待它给你一个答案，然后发现答案。

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