Jas*_* M. 17 theory turing-machines computation-theory
我真的在努力理解这两者之间的区别.从我的教科书中,它实质上描述了差异
如果语言是图灵可识别语言的补充,那么这种语言就是可识别的.
我想这个定义我不理解的部分是:当它是图灵识别语言的补充时它意味着什么？
你究竟如何确定它是否是另一种语言的补充？
tem*_*def 41
(注意 - "Turing decidable"和"co-Turing decidable"这两个术语是相同的.但是,"图灵识别"和"共同图灵识别"并不相同,而这就是我决定的在我的回答中说明.原因是如果一种语言是可判定的,那么它的补语也必须是可判定的.对于可识别的语言也是如此.)
直观地说,如果有一些计算机程序,如果语言中有一个字符串,可以确认字符串确实在语言中,那么语言就是图灵可识别的.如果字符串不在语言中,该程序可能无限循环,但如果您在语言中给它一个字符串,它保证总是最终接受.
虽然语言是图灵可识别的,但如果它是图灵可识别的语言的补充,那么这个定义并没有对正在发生的事情有所了解.直观地说,如果一种语言是共同图灵可识别的,那就意味着有一个计算机程序,给定一个不在语言中的字符串,最终将确认字符串不在语言中.但是,如果字符串确实在语言中,它可能无限循环.这样做的原因很简单 - 如果某个字符串w不包含在用图灵可识别的语言中,则该字符串w必须包含在该图灵可识别语言的补充中,(根据定义)必须使用是图灵可识别的.由于w在图灵可识别的补码中,必须有一些程序可以确认w确实在补体中.因此,该程序可以确认w不是原始的用图灵可识别的语言.
简而言之,图灵可识别性意味着有一个程序可以确认字符串w是一种语言,并且共同图灵可识别性意味着有一个程序可以确认字符串w 不在该语言中.
希望这可以帮助!