在图灵机中区分可识别和可判定?

当我们谈论图灵机 (TM) 时,它可以接受输入、拒绝输入或保持计算,这称为循环。

现在,当且仅当图灵机接受字符串时,当提供的输入位于语言中时,语言才是可识别的。

此外,如果 TM 终止并拒绝字符串或根本不终止,则可以识别语言。这意味着当提供的输入不在语言中时,TM 继续计算。

然而,当且仅当有一台机器在提供的输入位于该语言中时接受字符串并在提供的输入不在该语言中时拒绝该字符串,该语言才是可判定的。

例子

  • A = {hM,wi | M 是一个 DFA 并且 w ∈ L(M)} 是可判定的。

  • A = {hM,wi | M 是一个 TM 并且 w ∈ L(M)} 是可识别的。

车床中可识别和可判定之间的主要区别如下 -

先生。没有图灵可识别图灵可判定
1一种图灵可识别的语言,如果有一台机器将停止并只接受该语言中的字符串而不接受该语言中的字符串,那么该 TM 要么拒绝,要么根本不停止。A language is said to be Decidable if there is a Machine that will accept strings in the language and reject strings not in the language.
2如果某种图灵机识别出一种语言,则该语言称为图灵可识别语言。A Language is called Turing Decidable if some Turing Machine decides it.
3如果存在这样的图灵机,当遇到该语言的字符串时,机器终止并接受该字符串,那么我们可以说该语言类型是图灵可识别的。If there exists a Turing Machine such that when encountering a string in that language, the machine terminates and accepts that string then we say that type of language is Turing decidable.
4如果存在一个图灵机,当遇到一个不是该语言的字符串时,机器要么终止并拒绝该字符串,要么根本不终止,那么我们可以说它是图灵可识别的。If there exists a Turing Machine such that when encountering a string not in that language, the machine terminates and rejects that string then we can say it is Turing-Decidable.
5它不是比图灵可判定强的条件这是比图灵可识别更强的条件。