gotchaMajor
Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?
Viewed 0 times
totalthewhatrejectingdifferencebetweenacceptingrecognizingmachinesdeciding
Problem
I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?
As I have also seen places where we mention a Turing machine "accepting a language"
See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?
I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?
As I have also seen places where we mention a Turing machine "accepting a language"
See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?
I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?
Solution
A Turing Machine cannot accept a language.
A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, if it halts in a rejecting state.
A TM recognises a language, if it halts and accepts all strings in that language and no others.
A TM decides a language, if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.
A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.
Edit:
To answer some of the questions in the OP's comments:
-
A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.
-
All finite languages are decidable which means that there is a corresponding Turing machine which is a decider.
A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, if it halts in a rejecting state.
A TM recognises a language, if it halts and accepts all strings in that language and no others.
A TM decides a language, if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.
A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.
Edit:
To answer some of the questions in the OP's comments:
-
A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.
-
All finite languages are decidable which means that there is a corresponding Turing machine which is a decider.
Context
StackExchange Computer Science Q#111331, answer score: 20
Revisions (0)
No revisions yet.