What is the difference between a TM accepting and deciding a language?

Problem Detail: 

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?

Asked By : agent154

Answered By : Andrej Bauer

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9234