8
$\begingroup$

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language $L = \{ x \in \{0,1\}^* \mid x \text{ is divisible by } 4 \}$. I know that any binary string ending with $00$ is divisible by 4, so $\{00,100,1100,1000,11100,11000,10100,10000,\dots\}$ is the language that this TM accepts.

But on the topic of (un)decidability: I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language — and that same TM rejects all strings and only strings not in that language.

Which leads to the question: What is the difference between a Turing machine accepting and deciding a language?

$\endgroup$
1
  • 2
    $\begingroup$ Usually, a Turing machine accepts (or rejects) a string in some language, whereas it decides some language. In other words, the language a Turing machine $M$ decides is exactly the set of strings it accepts. $\endgroup$
    – John K.
    Commented Jan 28, 2013 at 9:06

3 Answers 3

10
$\begingroup$

In situations like these, where you are wondering about the difference between two phrases, the correct thing to do is to look up some definitions and think about them. You will discover several variations, perhaps something like this:

  1. A machine "eats" a language $L$ if on input $x$ it halts and outputs $1$ if $x \in L$, and $0$ otherwise.

  2. A machine "drinks" a language $L$ if on input $x$ it halts in an accept state when $x \in L$ and in a reject state if $x \not\in L$.

  3. A machine "sniffs" a language $L$ if on input $x$ it halts in an accept state when $x \in L$, and never terminates if $x \not\in L$.

  4. A machine "gobbles" a language $L$ if on input $x$ it reaches a OK state when $x \in L$ and never enters the OK state otherwise.

  5. A machine "chews" a language $L$ if on input $x$ it halts in state 0 when $x \in L$, and either never terminates or halts in state 1 when $x \not\in L$.

These all look the same but are all slightly diffent. You should expect some definitions to be slightly broken (because you got it from Wikipedia or your classmate's notes), or phrased in a weird way that suits the needs of a particular texbook, etc.

The most important thing to do is to figure out what the definitions are really trying to convey. If they are basic definitions that everyone refers to, they are likely to tell you something important. (In a research paper people sometimes make definitions to numb the readers' brains.) Once the concepts are clear, it does not matter what they are called. Also, in case of terminological confusion, you will always be able to quckly resolve possible misunderstanding because you already know what concepts to expect.

In the present case, there are really two possible notions. One in which a machine always halts and signals acceptance/non-acceptance in some way, for example by halting in certain states, or by outputting certain symbols. The other concept is when a machine does not always halt, and it uses halting to indicate acceptance and non-halting to indicate non-acceptance.

A nice exercise is to figure out which of the five definitions given above corresponds to which of the two concepts (and which definition is a bit unclear, if any). But even before the exercise you need to know why these are two different concepts! You need to be aware of a language which falls under one but not the other concept.

The trouble with learning math is that you have to simultaneously learn new phrases and their meaining, and figure out why people invented them.

$\endgroup$
1
  • 2
    $\begingroup$ +1 for not getting impressed by sometimes-inconsistently-used CS vocabulary and making up one's own (as long as a clear definition is provided) $\endgroup$ Commented Dec 29, 2015 at 12:37
9
$\begingroup$

There is major difference. A turing machine "accepts" a language, if it enters an accepting state for any input from the langue, while it "decides" the language if it "accepts" it and enters a rejecting state for any input not in the language.

These are different, because there is a third thing that a Turing machine can do: never stop. Such Turing machine accepts the language, but does not decide it.

See also this other question and definition of decidable language on WP.

$\endgroup$
2
  • $\begingroup$ I dunno, where I come from "accept and decide" are synonyms, while the third option is "recognize". $\endgroup$ Commented Jan 28, 2013 at 9:53
  • $\begingroup$ @AndrejBauer: Indeed the terminology does not seem to be completely unified. But I linked the definition on WikiPedia, which clearly says "decidable" means that it's complement is also decidable. $\endgroup$
    – Jan Hudec
    Commented Jan 28, 2013 at 9:58
3
$\begingroup$

They are usually used as synonyms. In your example, the Turing Machine should first go all the way to the end of the input, and then check that the two rightmost digits are 0, as you suggest.

$\endgroup$
2
  • 7
    $\begingroup$ No, actually "decides" means it accepts or rejects, while it can accept or never stop. $\endgroup$
    – Jan Hudec
    Commented Jan 28, 2013 at 9:36
  • $\begingroup$ The terminology does not seem to be fixed here. I disagree with Jan, but I don't really care, I can perfectly well adapt to Jan's terminology. $\endgroup$ Commented Jan 28, 2013 at 10:11

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.