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?

  • $\begingroup$ There's no such thing as "the language the Turing machine is defined over". $\endgroup$ – Yuval Filmus Jun 30 '19 at 19:12
  • $\begingroup$ Many differents turing machines can decide the same language (in fact for every language that has a TM that decides it there is an infinite number of TM deciding it... just take that TM and modify it so that when it would stop and accept/reject instead it does 1 step to the right and then stops and accepts/rejects. Then modify it again to move 1 step farther before stopping. You can do this for every n) $\endgroup$ – Giacomo Alzetta Jul 1 '19 at 10:45
  • $\begingroup$ @user466720 Try not to add new question(s) to an existing question, especially when it was posted months ago, especially it was not posted by yourself, especially when there are multiple answers and especially when there is an accepted answer. $\endgroup$ – John L. Mar 11 at 20:17

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, of 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 Turing machine 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.


To answer some of the questions in the OPs 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

  • 2
    $\begingroup$ Minor nit: a recognizer for a language halts and accepts on all strings in that language and no others. $\endgroup$ – templatetypedef Jul 1 '19 at 11:48
  • 1
    $\begingroup$ "A Turing Machine will either accept or reject a string." ...unless it diverges on that string. $\endgroup$ – chi Jul 1 '19 at 13:25
  • $\begingroup$ I have added the corrections from the two above comments. I have not gone further into divergence on a string as it is not applicable for the question asked, however it would be incorrect to not mention it $\endgroup$ – user106386 Jul 1 '19 at 13:50
  • $\begingroup$ It might be worth emphasizing the difference between recognition and decision for people like me who didn't get it at first. Maybe change "and no others" to "and either halts and rejects or doesn't halt at all on others"? I don't know enough CS to word that well, though. $\endgroup$ – Fund Monica's Lawsuit Jul 1 '19 at 17:56
  • 2
    $\begingroup$ @NicHartley Something along the lines of ;recognising only cares that it accepts all strings in that language, there is no specification for if the string is not in the language, ie it can halt and reject or it can loop forever. Deciding says it must reject strings not in the language $\endgroup$ – user106386 Jul 1 '19 at 18:00

One considers two different types of Turing machines:

  • Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as the set of all inputs accepted by it.
  • General Turing machines: these are machines that are not guaranteed to halt on all inputs (but may). When we are interested in this kind of machine, we generally associate with them the language of all inputs on which the machine halts.
  • $\begingroup$ How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite? $\endgroup$ – WeCanBeFriends Jun 30 '19 at 19:26
  • $\begingroup$ A Turing machine is total if it halts on all inputs. This is the definition. $\endgroup$ – Yuval Filmus Jun 30 '19 at 19:27
  • $\begingroup$ Is it correct to say that a TM accepts a string? If so, does that mean it halts+accepts or does it mean it does not reject, ie it can loop? $\endgroup$ – WeCanBeFriends Jun 30 '19 at 19:27
  • 1
    $\begingroup$ I'm not sure what you mean by "how do I know". There is no algorithm that can determine whether an input Turing machine is total. But some Turing machines are total nevertheless. $\endgroup$ – Yuval Filmus Jun 30 '19 at 19:29
  • 1
    $\begingroup$ No. You're confusing Turing machines and languages. $\endgroup$ – Yuval Filmus Jun 30 '19 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.