代码之家 › 专栏 › 技术社区 › S A

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

turing-machines computation-theory

0

S A · 技术社区 · 9 年前

可以被TM识别但不能被TM决定的语言吗?

TM可以识别但不能识别的语言示例由TM决定

答案是:

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

我可能错了吗?

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

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

1 回复 | 直到 9 年前

1

templatetypedef 9 年前

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

关于第二个问题-可判定性和可识别性有什么区别?-你给出的答案是正确的,但写得不正确。记住,可判定性和可识别性是语言不串不存在“可判定字符串”或“可识别字符串”

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

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