World's most popular travel blog for travel bloggers.

[Solved]: Problem regarding Turing Machine notation

, , No Comments
Problem Detail: 

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.

Asked By : Anurag Kalia

Answered By : jmite

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback