[Solved]: Proof-sketch on the language accepted by a Turing machine

Problem Detail: 

Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$

Asked By : And

Answered By : Hendrik Jan

In order to prove that any machine, automaton or grammar satisfies $L(T) \subseteq X$ you have to translate your intuition of how it was designed into hard facts. What is the intended meaning of a certain configuration, how where the states chosen? So you have to divide the operation of the machine into phases. Like, "if the TM is in state $q$ on the left of the tape, it will move right, marking half of the symbols $A$ ending in state $q$ on the leftmost cell used". If the design of the machine is done right, such explanations usually suffice, if they can be easily understood. Otherwise one has to apply induction, on whatever seems interesting (like the remaining symbols $A$).

Let me try to add an example, what I would consider sufficient "proof". A Turing machine deciding the language $\{ a^{2^n} \mid n\ge 1\}$. States used $p_0,p_1,p_O,p_E,\ell,p_A,p_R$, accepting state $p_A$, rejecting $p_R$. Tape alphabet $\{a,X,B\}$, with $B$ for blank. Instructions in the order (state, symbol, new state, new symbol, direction).

We scan the tape from left to right. In each scan we halve the number of $a$'s. When the number of $a$'s on the tape is $1$ we accept, otherwise when the number is odd we reject (and halt), finally when the number is even, we return to the leftmost symbol on the tape.

Start in state $p_0$, indicating $0$ $a$'s read. Other states $p_1,p_E,p_O$ for single, even, odd number of $a$'s read.

• $(p_0,a,p_1,a,R)$, $(p_1,a,p_e,X,R)$, $(p_E,a,p_O,a,R)$, $(p_O,a,p_E,X,R)$, move right, crossing out every second $a$.
• $(p,X,p,X,R)$, for $p = p_0,p_1,p_E,p_O$, ignore symbol $X$.
• $(p_0,B,p_R,B,L)$, $(p_1,B,p_A,B,L)$, $(p_E,B,\ell,B,L)$, $(p_O,B,p_R,B,R)$, make decision on reaching the right end of the tape, as explained above.
• $(\ell,\sigma,\ell,\sigma,L)$, $\sigma = a,X$
• $(r,B,p_0,B,R)$ in state $\ell$ move left to first symbol on tape, ending there in state $p_0$.

Finally, note we reject on empty tape.

Best Answer from StackOverflow

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