2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Simon S May 29 '14 at 17:25
  • $\begingroup$ You're right sorry... $\endgroup$ – nubz0r May 29 '14 at 19:37
  • $\begingroup$ What is $\Gamma$ supposed to be? $\endgroup$ – babou Jul 29 '14 at 11:32
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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