[Solved]: What happens if we expand the alphabet of a given Turing Machine?

Problem Detail: 

If we expanded the alphabet Sigma = { 0, 1, u, > } to Sigma' = { 0, 1, 2, u, > }. How would the table change? We're just learning about Turing Machines in class and I'm a bit confused. Is the table in the picture calculated in some way?

Asked By : Chris Johnson

Answered By : Davislor

That's a table of transitions, and it determines what the program does when it encounters a given symbol on its tape while in a given state. This program, if I'm reading it right, accepts strings containing two consecutive 1 symbols before the first space.

If there were another symbol, it would be necessary to define what the program would do on encountering them. For example, to ignore them, there would be a pair of transitions saying that, if the program is in state s1 and reads a 2, it should stay in state s1 and move to the right, and that if it is in state s2 and reads a 2, it should stay in state s2 and move to the right.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47647