6
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ There's no such thing as "the language the Turing machine is defined over". $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2019 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
    Commented Jul 1, 2019 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.
    Commented Mar 11, 2021 at 20:17

2 Answers 2

Reset to default
20
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ Minor nit: a recognizer for a language halts and accepts on all strings in that language and no others. $\endgroup$
    – templatetypedef
    Commented Jul 1, 2019 at 11:48
  • 1
    $\begingroup$ "A Turing Machine will either accept or reject a string." ...unless it diverges on that string. $\endgroup$
    – chi
    Commented Jul 1, 2019 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
    Commented Jul 1, 2019 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$
    – anon
    Commented Jul 1, 2019 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
    Commented Jul 1, 2019 at 18:00
4
$\begingroup$

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.
Improve this answer
$\endgroup$
8
  • $\begingroup$ How do I know a Turing machine is total? Maybe if the language defined by the Turing machine is finite? $\endgroup$
    – WeCanBeFriends
    Commented Jun 30, 2019 at 19:26
  • $\begingroup$ A Turing machine is total if it halts on all inputs. This is the definition. $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2019 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
    Commented Jun 30, 2019 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
    Commented Jun 30, 2019 at 19:29
  • 1
    $\begingroup$ No. You're confusing Turing machines and languages. $\endgroup$
    – Yuval Filmus
    Commented Jun 30, 2019 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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