I was given a quick lesson on Turing Machines which I found interesting. However, I came up with a problem which made me think a bit on a problem and since it's not an actual class, the answer was not given. First, let me give you some background info on a Turing Machine:
A Turing machine is a quadruple (K, sigma, small delta, s), where
K is a finite set of states, not containing the halt stage h;
sigma is an alphabet, containing the blank symbol #, but not containing symbols L and R;
s is in K is the initial state;
small delta is the rate of change.
With that info in mind, I have the following problem:
Consider the Turing machine M = (K, sigma, small delta, s), where
K = {q0,q1} //only has two states
sigma = {a,#} //only has a and the blank symbol
s = q0 //will start at 10
and small delta is given by the following table.
q small sigma small delta(q,small sigma)
q0 a (q1,#)
q0 # (h,#)
q1 a (q0,a)
q1 # (q0,R) //move one cell of the tape to the right
With this info and the following example, we have:
a|a|#
Let's check the first cell, it's a and we are in the initial state. If it's a, change it to #.
#|a|#
We're still on the same cell, but we changed states, q1. The alphabet is #, so let's go back to the initial state and go one cell to the Right.
The next cell has an a as well, so we change it to #. Go to state q1 and check if the alphabet is blank. It is, so we go one cell to the right.
#|#|#<we're in this cell now.
Now we go to the initial state and check if the alphabet is a, it isn't so let's check if it's blank. It is, so we halt the whole thing.
We have
#|#|#
Pretty straightforward, right? Well, I have thought of one thing. What if the tape had something that was not taken into consideration?
Something like
a|b|a|#
Would the Turing machine crash or would it ignore it?
Thank you for your time.