Turing Machine:  Basic Model of Computing

2-way infinite tape.  Every state, character combination directs to a new state (or halt) and causes either a character to overwrite the character at that part of the tape OR causes the tape head to move one space to the left or one space to the right.

You can think of a Turing machine as a mathematical function that takes in one state and one character and returns one state (or HALT) and one character (or L or R).

Turing machines can emulate any programming language ever developed.  Turing machines can solve any problem any computer anywhere as ever solved.  Turing machines never run out of memory.  Although there are a finite number of states, the tape is infinite in both directions, so you can store as much information as you need to solve a problem.

Because the mathematical definition of a TM is so simple and so precise, a lot of algorithm analysis is done on Turing Machines, even though a TM is not the best model of modern computing.  (Modern computing uses a RAM model, meaning that accessing any spot in memory takes about as much as time as accessing any other spot in memory.  A TM has to move through tape to get to the information it may require.

Suppose the input to a TM was a string of 0-9 followed by a space followed by another string of 0-9 followed by another space.

Without listing the states individually, generally speaking, how would you design a TM to add those two numbers and put the answer on the tape, followed by a space.


TAPE:  3456 789

OUTPUT: 4245


SHIFTRIGHT  SHIFTLEFT

Given a string, your head points to the beginning, and there's a space at the end, how do you shift the whole thing one space to the right?  If it makes it easier, you can imagine that there is a space immediately to the left of the head, so that the string you want to shift to the right is bounded by space on either side.

Move to the right until you hit a space, move one space to the left.  (You're now on the last character.)  Copy the character you're at to the right, replacing it with a space.

_CAT_

_CA_T_

How do you copy that T?  You can create a set for each states for each possible character.  One set writes a space moves right, writes an A.  One set of states writes a space moves right, writes a B.

Then you move left beyond the space to the previous letter.  Do the same thine.

_C_AT_

Then you move left beyond the space to the previous letter.  Do the same thing.

__CAT_

Then we move left beyond the space to the previous letter, and that's a space, so we're done.

So, if you have SHIFTRIGHT and SHIFTLEFT...how can you do addition?

Find the rightmost digit of the first number.  Move right until you get to the rightmost digit of the second number.  You have a different set of states for each possible rightmost digit of the first number.

3456_789_

I see the 6, I use the set of states corresponding ot the six to move right until I hit the second space.  Then these specific states on seeing a 9 will print a 5 and "remember" a carry.  (I also have sets of states that handle carries.

3456_789_5

I go backwards, shifting the left so that it overwrites the 9.

3456_78_5

I go backwards to the previous space and shift everything left after that.

345_78_5

Now I start again.  I find the rightmost digit of the first number, a 5, and use a states corresponding to a 5 with a carry present.  Do the same thing get to the eight.  These states indicate that on an 8 I should write a 4 and "remember" that there is a carry present.

So I shift the 5 to right.

345_78__5

And write the 4 there.

345_78_45

Move backwards.

345_7_45

34_7_45

Move right see the 4, use the set of states corresponding to the digit 4 with a carry present.  On 7, those set of states know to write 2 and choose states that represent a carry being present.

Shift _45 to the right, add the 2.

34_7_245

Again, move to the left, deleting the last digit.

34__245
3__245

My 3 with a carry present on seeing that there is no digit in the numbers  knows to write a 4, after shifting the number to the right.  It also knows to choose a set of states that do not represent a carry.

3__4245

Moving backwards, we see that there in the digits in the second number.  We move backward and delete the last digit of the first number.
__4245.

When we do it again, we see that there are no longer digits in either number so we must have our answer, make sure our head is pointing to the first digit.

4245


3456_789
3455_790
3454_791
3453_790
...
1_4244
0_4245
4245


Now, when we talk about Turing Machines we talk about a thing called the "finite control."  The "finite control" is a figure of speech; it isn't a real thing!!!!!

If we have a finite number of options, much like we did with the addition program.  A set of states of 1 with carry, 1 without carry, 2 with carry, 2 without carry, and so forth.  We do this with, say, 20 sets of states, because that's really the only way we can.

So, instead of explicitly saying "we choose a set of states that works when the digit is 5 and there is a carry" instead we say "we store 5 and a carry in the finite control."  In reality, we still have a whole bunch of sets of states.  But we can imagine that we have storage unit attached to our TM that can story a FINITE amount of information so that we are not explicitly listing the sets of states (finite, but possibly quite large) for each of the possibilities we need.


Given an input string of alphabetic characters followed by space, design a Turing Machine that gives a value of YES if the input string is a palindrome and NO if it is not.

Look at the leftmost character and put it in the finite control.  Move to space at the right, move left to the rightmost character.  Compare that character to character in the finite control.  If they match, write a space.  Move to the far left, move right to the first character, replace that with a space, and move one more to the right.

And so forth.

If the character doesn't match the finite control character, just write NO and move left to the N, and that's that.

When you run out of characters, then write YES, and move back to the Y.

An "error state" in a TM, is a deliberate infinite loop, so that you are guaranteeing the the Turing Machine does not halt.

Sometimes we are given a machine that is very similar to a Turing Machine, but may have more stuff.  It may superficially appear to be more "powerful," but may not be in reality.  In other words, this "more powerful" might not be able to solve any problem that a regular TM can't already do.  This is a common exercise.

If I give you a weird machine, you have to show that you build a regular machine that will do the same thing.  ("reducing to a Turing Machine.")

For example, let's suppose we have a 2-way infinite tape, but the tape is two characters high.  So, we can move left and we can move right.  But wherever we are on the tape, there's an upper character and a lower character.  For each state, we look at the upper and lower characters and decide whether we want to write upper, write lower, move left, move right, move to a new state, or halt.

It works exactly like a regular Turing Machine except we are always looking at two characters rather than one.

Is this more powerful than a regular Turing Machine?

The answer is no, but how would you construct a regular Turing Machine to solve the exactly problem as this more powerful machine...even if you don't know offhand what exact problem this machine is solving?

Suppose the alphabet for the more advanced machine is called SIGMA.  Say {A,B,C}.  Make a regular Turing Machine whose alphabet is SIGMAxSIGMA, the set of ordered pairs over SIGMA.  {(A,A),(A,B),(A,C),(B,A),(B,B),(B,C),(C,A),(C,B),(C,C)}.  So this Turing Machine writes letters that correspond to the TWO letters on the tape of the more powerful machine.

So, if my more powerful has a C as the upper letter and a B as the lower letter, mine would have the single letter (C,B).