Describe a TM through denotation of the transition function

Question

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.

Answer 1

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$.)

So check your lecture notes on the technical details again, and start thinking how to do the comparison letter-by-letter. It is not that hard: just pretend you are the machine and analyse your steps on a simple example input.