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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2218
