Turing machine and language decidability

Problem Detail: 

The document I am reading is here: Turing Machines

Before getting into the question, here is the notation used on the picture:

Here $\Delta$ denotes the blank and R, L and S denote move the head right, left and do not move it, respectively. A transition diagram can also be drawn for a Turing machine. The states are represented by vertices and for a transition $\delta( q, X ) = ( r, Y, D )$ , where D represents R, L or S , an arc from q to r is drawn with label ( X/Y , D ) indicating that the state is changed from q to r, the symbol X currently being read is changed to Y and the tape head is moved as directed by D.

According to the document:

A Turing machine T is said to decide a language L if and only if T writes "yes" and halts if a string is in L and T writes "no" and halts if a string is not in L

Here is the three examples:

• Case 1:

• Case 2:

• Case 3:

I just want to verify my understanding. According to the definition, in case 1 and case 2, its turing machines cannot decide because the machines cannot tell whether invalid inputs rather than { a } (such as aa, aaa, aaaa....) is in L or not.

In case 2, if another a appears after the first a, or if the input is empty, the machine goes to state S and loop forever.

In case 3, if a is detected and only a single a exists, that a is replaced by 1 and the machine accepts. Otherwise, a 0 is replaced and the input is decided not in the language.

Am I correct on all of these? However, in case 3, what if I give any input which contains other character rather than a (such as string ab, bc...)? Or is it said that TM decides only languages over a set of alphabet $\Sigma$ allowed by the Turing Machine?

If a string which is longer than a single a (like aa, aaa,ab,bc...), the machine may loop forever (like in case 2) or halt without accepting (in other words, it is "crashed", where it does not have transition rules for a symbol in the input such as b in the case of above Turing Machines). Is this correct also?

Asked By : Amumu

Answered By : Dave Clarke

A TM decides a language if it enters the accepting state for word in the language and it enters the rejecting state if it is not. Thus it halts on all inputs. Note the machines defined above are not entirely standard. They way they denote acceptance and reject is by writing a $1$ or $0$ and then by entering a halting state. This is equivalent to the standard definition, but less elegant.

Machine 1 does not reject words not in the language. It only accepts the language.

Machine 2 does not halt for words not in the language. It only accepts the language.

Machine 3 rejects and hence halts for words not in the language, therefore it decides the language.

Best Answer from StackOverflow

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