HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMajor

Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?

Submitted by: @import:stackexchange-cs··
0
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?

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.

Context

StackExchange Computer Science Q#111331, answer score: 20

Revisions (0)

No revisions yet.