2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

The behavior of the Turing machine is not defined in this case. So, the mathematical formalism does not predict or require anything about how the machine will behave in such a circumstance.

Since a Turing machine is only a mathematical construct anyway, it's perfectly reasonable to impose such a limitation and only think about what happens when you run it on a tape that follows all the rules.

Put another way: If it's possible for the symbol b to occur in the tape, then it's your job to make sure that b is included in the alphabet.

$\endgroup$
  • $\begingroup$ Ah, fair enough. But what about the case a symbol is not defined if it's not predicted? Eg. A greek symbol or a Russian one? $\endgroup$ – Julio Garcia Oct 18 '13 at 18:19
  • $\begingroup$ @JulioGarcia, sorry, I'm not following you. $\endgroup$ – D.W. Oct 19 '13 at 3:56
  • $\begingroup$ Sorry, I didn't word my question right. What I wanted to ask is: let's say you take care of the alphabets you want to take care of, but there's one that wasn't taken into consideration. What will the Turing Machine do? Will it stop or will it move on to the next cell? $\endgroup$ – Julio Garcia Oct 19 '13 at 18:28
  • 1
    $\begingroup$ @JulioGarcia, that seems like the same question you asked and I answered. The answer is: its behavior is not defined. $\endgroup$ – D.W. Oct 19 '13 at 19:14
  • 3
    $\begingroup$ It's like asking what's the sum of 4 and an elephant. The sum operation is defined for real numbers. If your teacher asks you to compute the sum of 4 and an elephant, you'll be at a loss. $\endgroup$ – Yuval Filmus Oct 19 '13 at 20:14

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.