TURING MACHINES:

Design a Turing Machine that adds 1 to a decimal number.  The input string is the decimal number followed by a space.  The output should be the following number followed by a space.

Move left once.  Write a space.

Go to the end, when you hit a space go left once.  It it's not a nine replace the digit with the following digit.  If it is a nine, write zero go left once and continue this process.  If you hit a space, write a one there, and you're done.  If you hit a number other than 9, increment it and move to the far left.  (Meaning move left until you hit a space, then move right.)

"RAM Model" is also theoretical model of computing:
You imagine that you have an infinite number number of memory locations numbered 0, 1, 2, ... , one for each nonnegative integer.  Each memory location is allowed to hold a nonnegative integer.
You have basic operations:  ADD A,B,C  SUB A,B,C  MUL A,B,C, DIV A,B,C MOD A,B,C .  You also conditional branches:  IF A GOTO L  (if the value in register A is nonzero jump directly to a statement labeled L) and you also have an unconditional branch GOTO L.

Now let's say our input is two decimal integers with one space following each.  The output is the sum of these integers.  How would you do this?

Make that space on the left.

Remember that for Turing Machines, no one cares how efficient your algorithm is.  So, going back and forth, decrementing one number and incrementing the other until the first one is zero, works fine.

Testing whether a number is zero:  I mean a string of zeros.  You move through the string, if you ever hit a nonzero go to the state for that.  If you to make it to the space at the other end, then go to the state meaning it's zero.

If it's the second number you decrement, and the first number you increment, our increment function expands to the left.  If we use a decrement that doesn't shrink the number, then our decrement will eventually give us a string of zeros.  Can I decrement the second number?  If so, decrement and then increment the first number.  There will always be one space between the numbers, so you can easily get from one to the other.

Now let's say that you wanted to emulate the childhood addition algorithm.  What are the tricky parts you have to worry about?

1.  Where am I in the number?
2.  Handling the carry.

1.  Couple of approaches:  Erase digits when you're done using them (which is fine unless you still need the original numbers around).
I add a few extra characters to the tape language.  Underscore0, Underscore1, etc.  And I can replace or "mark" the characters I'm using with the underscore, and that way I know where I am in the number, the next digits I need to add are the rightmost ones without underscores.

Tangent:  Let's say I want to make a copy of a string.  One way to do it, is to start the left, move the leftmost character one space to the left, put a space for the first character used to be.  Move to the right, until you find a space, and write that first character down.
Then move back to that first space, move the character after that (the second character) into that space, replace the second character with that space, then move right, find the second space and put the second character there.  AND SO FORTH.

How does your TM "remember" the character you need to write after you move down all those spaces when you're making the copy?  Is to have completely distinct sets of states for all possibilities which could be quite large.

This is where the "finite control" comes in.  When describing a TM in English, it is customary to make use of the "finite control" which is a figure of speech and doesn't really exist.

You imagine the finite control contains FINITE information.  The finite control is only allowed to hold a FINITE number of values.  In reality, the TM is dealing distinct sets of states, but we use the finite control as a shortcut in our description.  If we are trying add a digit of one number to a digit of another number, we say we store the first digit in the finite control and move to the proper position in the other number and add the number in the finite control to the digit in the new position.  In reality, you have separate sets of states for 0, 1, 2, etc., but we shortcut this by saying that we're storing the digit in the finite control.

We can do the same thing with the carry for an addition.  We can store the carry digit in the finite control and add it to the next left digit at the appropriate time.  So, our finite control can be in one of twenty different states.  It's storing a digit (ten possibilities) and a carry (two possibilities).  20 is a finite number so this is a perfectly valid finite control.

Now, if you use the finite control, use it correctly.  For example, do not store the length of a string in the finite control because, generally speaking, there's no upper limit on the length of a string, so the finite control would have an infinite number of possible values.

Now, let's suppose you did a magic finite control that COULD store an infinite number of values.  That machine would be equivalent to a TM, but it wouldn't actually be one.

Original definition of a TM:  the tape was infinite only on the right, and if you moved beyond the left end, the TM would "hang" meaning it was in a permanent of non-halting.

How would you prove that a one-way infinite tape can solve any problem that a two-way infinite tape can solve?

Is T is the tape alphabet on the two-way tape, make TxT the alphabet for the one-way tape.  You "imagine" that each cell on the tape has a top character and a bottom character.  If you're processing the bottom character, left means left and right means right.  But if you're processing the top character, left menas right and right means left.  You can keep track of whether you're processing the top or bottom in the finite control.  When you get the left most square on the tape (you can certainly mark that if you need to) then switch your reference from top to bottom or bottom to top.