Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?$

share|improve this question
    
its basically nearly an undecidable question unless there are some restrictions on $L(T)$ and $X$ ie one or the other are provably in simpler classes than recursively enumerable. –  vzn Feb 23 '13 at 17:14
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
add comment

The main approach is to start with arbitrary word $w$ in $L(T)$ and then show that $w$ is also in $X$. In order to do so, you will probably need see the "relation" between $L(T)$ and $X$.

The specifics highly depend on $T$ and $X$, but generally, there are two ways:

  1. From the description of $T$ you figure out what $L(T)$ is, and then you can forget about Turing machines - you have two sets $A=L(T)$ and $B=X$ and you need to show $A\subseteq B$ using standard set theory.

  2. Analyze the connection between $T$ and $X$, and then show that any word $w$ that the TM accepts must have some properties, that are defined by $X$.

As said, different definition for $T$ and $X$, will change your approach.

Just to complete the answer, let's have two simple examples.
case 1 Let $T$ be the Turing Machine over $\{0,1\}$ that accepts $\{0,00,000,...\}$. Let $X=\{ w\mid w$ has more zeroes then ones $\}$.
proof. Clearly, any word that has only zeroes will have more zeroes than ones, thus $L(T) \subseteq X$.

case 2 Let $T$ be some Turing machine. Let $X$ be the language accepted by a Turing machine $T'$ that on input $w$, runs $T$ on all the words $u$ of length $|w|$ and rejects only if all of them are rejected by $T$.
proof. If $w$ is accepted by $T$ then it must be accepted by $T'$: it cannot be that $T'$ rejects, since $T$ accepts at least in the case where $u=w$ (possibly in other cases aswell). Thus $L(T) \subseteq L(T')$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.