# Describe a TM through denotation of the transition function

I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language

$$L ={\{w\#w} \mid w \in {\{0,1}\}^*\}$$ over the input alphabet: $$\displaystyle\sum = {\{}0,1,\#\}$$

My guess is first to place a word $$w \in {\sum}^*$$

on the tape, and in every cell a symbol one after the other:

and the rest would be denoted with squares. Something like this $$...w|\#|w|\square...$$ the head would be on the first Symbol from $w$

So I guess now I know that
$$\Gamma = \{w,\#,\square\}$$

I could probably try to make a table using what I have now:

for $w$:

$q_0 = (q_0,w,\#,R)$ R would be the direction the head is going

$q_1 = (q_{yes},w,\#,N)$ N means the head doesn't move and $q_{yes}$ means that the TM accepts w

Im not sure if what I'm doing is correct. I would appreciate if someone could tell me if I'm on the right track.

• Do you mean "My guess is to place the input word $w \in \Sigma^*$" on the tape"? Otherwise it doesn't make sense, becuase $\Sigma$ is an alphabet not a set of words. In this case the $w$ you use further down is something differnt from the input word. – Simon S May 29 '14 at 17:25
• You're right sorry... – nubz0r May 29 '14 at 19:37
• What is $\Gamma$ supposed to be? – babou Jul 29 '14 at 11:32

You are making way too many guesses, and seem to be confused on the difference between words (elements of $\Sigma^*$, or $\Gamma^*$) and letters (elements of $\Sigma$ or $\Gamma$). This is basic stuff and need to be understood before even pretending to think about transition functions.
Indeed, the Turing machine gets a string on its input tape (with letters from $\Sigma$) flanked by $\Box$'s. To be precise $w$ is not an element of the tape alphabet, but a string over the input alphabet $\Sigma$. The tape alphabet equals $\Gamma = \{ 0,1,\#,\Box \}$ plus all the additional symbols that you need for the task you have to perform.
The task is: check whether the input is in fact a string of the form $w\#w$, i.e., two copies of the same string separated with $\#$. The Turing machine may write on the tape and use a little bit of memory, but cannot read stings $w$ in one go (which is what your question suggests). It makes steps on single letters like $(p,0,p_0,\bar 0,R)$: "in state $p$ I read letter $0$, switch to state $p_0$ [to remember $0$] write $\bar 0$ on the tape [replacing $0$ to indicate I have seen it] and move to the position on the right". (Now you have to add $\bar 0$ to $\Gamma$.)