# How to derive Turing Machine language?

Say you're given a TM (Turing Machine) $M = (Q, \Sigma, \Gamma, \vdash, \sqcup, \Diamond)$ and given the partial $\delta$:

$$\begin{array}{c|cc} \delta&\vdash&a&b&c&\sqcup&\Diamond\\ \hline 1&(1,\vdash,R)&(2,\vdash,R)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ 2&-&(3,\vdash,R)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ 3&-&(3,a,R)&(4,\Diamond,R)&(r,-,-)&(r,-,-)&(3,\Diamond,R)\\ 4&-&(r,-,-)&(4,b,R)&(5,\Diamond,L)&(r,-,-)&(4,\Diamond,L)\\ 5&(1,\vdash,R)&(5,a,L)&(5,b,L)&-&-&(5,\Diamond,L)\\ 6&-&(r,-,-)&(r,-,-)&(r,-,-)&(t,-,-)&(6,\Diamond,R)\\ t&-&-&-&-&-&-\\ r&-&-&-&-&-&- \end{array}$$

What steps can I take to get $L(M)$?

So far I have drawn $M$, and I can think of strings which will make it halt, but I have no idea how to get $L(M)$

I know $L(M) = \{a^{2n}b^{n}c^{n} \mid n \in ℕ \}$. What steps do I take to get there?

• In general you can't. Partly the question is unclear: the Turing machine is itself a description of $L(M)$, so you need to say what different kind of description your would prefer. But also the problem in general is undecidable. For example, even to answer the question “Here is $M$; is $L(M)$ empty?” is undecidable in general. You need to use some kind of informal reasoning , arguing that state 7 is for skipping rightwards over a block of as, or whatever. – MJD May 23 '16 at 19:00
• @MJD Understood. And say you would want $L(M)$ in the format $L(M) = \{a^{2n}b^{n}c^{n} \mid n \in ℕ \}$ what steps could I take, with the given information to derive that? – marcusvb May 23 '16 at 19:03