5
$\begingroup$

Here I have a Turing Machine (sorry for awful drawing):

enter image description here

So, I have a question regarding the usage of a here. It is treated as a variable here. But since it doesn't alter input tape in any way, shouldn't it be stored in an implicit storage? My question is if this implicit storage (tell me if I am wrong) is in conflict with the fact that a Turing Machine only has a single input tape.

My hunch is that it is syntactic sugar and it can be explicitly defined with less-intuitive notation (another input tape?), but I am not sure.

$\endgroup$
4
$\begingroup$

Unless I'm misunderstanding the diagram, the way to replace it is with a transition for every letter in your tape alphabet.

Say your tape alphabet $\Gamma = \{ 0,1,2,3 \}$, plus the blank symbol. Then you would have a transition from $R$ to $La$ when reading 0, another when reading 1, another when reading 2, another when reading 3, but NOT one when reading a blank.

You are right in your intuition that this is just syntactic sugar. What it is really doing is using one transition to represent several.

$\endgroup$
  • 2
    $\begingroup$ The best answers seem obvious after the fact. Thank you! $\endgroup$ – Anurag Kalia May 10 '13 at 17:21

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.