理解计算理论中的识别器和决策器
我在理解机器识别和决定语言的含义时遇到了一些困难。我认为我接近定义但不正确。
当有人说图灵机 T 识别语言 L where
L = { <A> | A is a DFA }
其中 DFA = 确定性有限自动机时，
我的理解是，这意味着可以构建一个图灵机，给定任何类型的输入（字符串、汽车、人，等等！），它将能够告诉您作为输入提供的东西是否是 DFA。我的意思是，将始终接受 DFA 并始终拒绝非 DFA 输入。
也就是说，如果该输入是 L 的成员。另一个例子是说X是他父亲的识别者，因为无论你放在他面前的东西是什么，他都能告诉你他面前的东西是否是他的父亲。这是正确的吗？哪一部分不正确？
另一方面，一种语言的决策者似乎是一个永远不会循环的图灵机，也就是说，它总是会停止在任何接受或拒绝状态。输入。这不是与我上面关于识别器的解释相似或相同吗？
谢谢
I am having some trouble grasping what it means for a machine to recognize and decide a language. I think I'm close to the definitions but not right.
When one says that a Turing Machine T recognizes language L where
L = { <A> | A is a DFA }
where DFA = deterministic finite automaton
my understanding is that it means that it is possible to build a Turing Machine that given any kind of input (strings, cars, persons, whatever!) will be able to tell you whether that thing you gave it as input is a DFA or not. With this I mean, will always accept a DFA and will always reject a non-DFA input.
That is, if that input is a member of L. Other example would be saying that guy X is a recognizer of his father, as whatever is the thing you put in front of him, he will be able to tell you if what is in front of him is his father or not. Is this correct? Which part is not correct?
On the other hand, a decider over a language seems to be a Turing Machine that never loops, that is, it will always halt in either an accept or reject state for any input. Isn't this going to be similar, or the same, as what I explained above about recognizers?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
经过一番研究，我想我明白了两者之间的区别。
一如既往，细节决定成败。
首先，可判定语言始终是可识别语言。
可识别的语言是至少有一台机器将其作为语言的语言。乍一看，这可能看起来像是又一个循环定义，但是……
用通俗的话说，如果你能想到一台能够接受其所有字符串的机器，那么一种语言就是可识别的。
示例
让我们设计一些非常简单的语言：
该语言仅由单词 abc 组成。这意味着要证明这种语言是可识别的，必须建造一台接受它的机器。我们将非正式地这样做：
这台机器接受语言 L 的所有成员，因此它是 L 的识别器。然而，对于所有其他输入，它将永远保留。如果存在一种机器，对于每个输入接受/拒绝，这种语言也可以是可判定语言类别的一部分。你能建造一个吗？
（剧透警告！！！11@#$!1）
也就是说，因为有一台机器可以识别 L 并且无论你给它什么输入，它总是会接受/拒绝，所以该语言被认为是可判定的。
此外，如果你有一天有兴趣构建一台识别 L 的机器，你就会知道你至少有一台机器总是能够做到这一点，而不会出现能够接受 abc 但在其他情况下惨败的问题，永远坚持下去！
After some studying, I think I got the difference between the two.
As always, the devil is in the details.
To start off, a decidable language is always a recognizable language.
A recognizable language is a language for which there is at least one machine that has it as its language. At first this may seem like one more of those circular definitions, but..
In lay terms, a language is recognizable if you can think of a machine that'd be able to accept all its strings.
An example
Let's devise some really simple language:
this language is composed only by the word abc. This means that to prove that this language is recognizable, one must build one machine that accepts it. We'll informally do it:
This machine accepts all the members of the language L, so it is a recognizer for L. Yet, for all other inputs it will just hang on forever. Would a machine exist that for every input accepts / rejects, this language could also be part of the class of decidable languages. Can you build one?
(spoiler alert!!!11@#$!1)
That is, as there is a machine that recognizes L and that whatever the input you give it, will always either accept / reject, the language is considered decidable.
Moreover, were you interest in one day building a machine that recognizes L, you'd know that you have at least one machine that's able to always do it without incurring in the problem of being able to accept abc but failing miserably in the other cases, hanging on forever!
我认为简单的答案是：
决策器总是停止、接受或拒绝，
但
识别器并不总是停止，机器可以接受、拒绝或循环。通过循环意味着机器不会停止。
对于识别器，有时我们使用决策器来决定，如果机器处于循环状态，那么决策器将根据我们的描述拒绝。
The simple Answer as I thinks is:
Decider always halts, accept or reject
But
Recognizer do not always halt, Machine can accept, reject or loop. By loop means machine does not halts.
For recognizer sometime we use deciders to decide, if machine is in looping then decider will reject according to our description.
图灵可判定意味着有一个图灵机接受该语言中的所有字符串并拒绝所有非该语言中的字符串，请注意，如果该机器是决策器，则不允许该机器永远在字符串上循环，它必须在一个阶段停止并接受或拒绝输入字符串。
图灵可识别意味着有一个图灵机可以接受该语言的所有字符串。请注意，机器不必拒绝不属于该语言的字符串，换句话说，允许该机器在不属于该语言的字符串上永远循环。
用高级英语来说，决策机必须对“字符串 x 是 A 语言中的字符串吗”这个问题回答“是”或“否”
如果字符串是该语言，则识别器必须对同一问题回答“是”，但如果字符串不是该语言，则允许说“否”或“无注释，即永远循环”
Turing decidable means that there is a Turing Machine that accepts all strings in the language and rejects all strings not in the language, note that this machine is not allowed to loop on a string forever if it was a decider, it must halt at one stage and accept or reject the input string.
Turing Recognizable means there is a Turing Machine that accepts all strings in that language. Note that the machine does not have to reject strings which are not in the language, in other words, this machine is allowed to loop forever on strings which are not in the language.
To put it in high-level English, a decider machine must answer "Yes" or "No" to the question "is the string x in the language A"
A recognizer must answer "Yes" to the same question if the string is in the language BUT if the string is not, it is allowed to say "No" or "No comment i.e. loop forever"
我认为图灵机识别 L 这样的语言意味着图灵机将接受与 L 组成的 DFA 相同的所有输入。因此，它们在这方面在某种意义上是等效的。
I think what it means for a Turing machine to recognize a language such as L is that the Turing machine will accept all of the same input as the DFA which L is composed of. Thus they are in a sense equivalent in that respect.