Turing Machine Tricks

Now that you know what Turing machines are, we can play some games with them. But as things stand, talking or writing about Turing machine programs is really painful. But we can work out a bunch of extensions to the Turing machine. They're not really extensions in the sense of adding a capability to the TM that it didn't have before, but more in the sense of shorthands: things that we can do with a normal turing machine, but where the extension gives us an easier, more concise way of saying it.

The point of these extensions isn't to give the machine the ability to do anything it couldn't do before; it's to give us a way to talk about the algorithms that turing machines use in an easier to understand way, without using state tables.

Non-writing Transitions

In our original turing machine description, we said that on every step, the transition function had to specify a target state, a symbol to write to the tape, and a direction to move the head. But as we saw in the subtraction machine state 1, there are some transitions that just don't change the symbol on the tape cell. In the basic Turing machine, that means we have to have an entry for every symbol specifying a transition to the same target state, moving in the same direction, and writing the same symbol that was read from the tape.

For example, imagine we had 4 symbols like the subtraction machine: "1", " ", "-", and "=". Remember, for state one, the part of the transition function was:

(State,Symbol)	(State,Symbol,Direction)
(1, " ")	(1 , " ", forward)
(1, "1")	(1 , "1", forward)
(1, "-")	(1 , "-", forward)
(1, "=")	(2 , " ", back)

We need three entries in the transition function just to say "move forward wihout changing the symbol on the tape". Instead, we can just say that the transition function can say "nothing" for the value to write, which means that the transition shouldn't change the value on the cell; and we can say that the input symbol can be any of a set of choices: (1, {"1", "-", " "}) -> (1, nothing, forward).

Moving the Head

We can add a couple of alternative ways to talk about moving the tape head.

move forward/backward to symbol X, then switch to state S

This is usually called a seek operation. The way you add it to a Turing machine is by adding one state to the machine; that state moves in the correct direction, leaving the tape unchanged, until it gets to the correct symbol, and switches to the new state. That's state 1 in the subtraction machine - it moves left, not changing the state, until it reaches an "=". We can just say "In state 1, move forwards until '=', then switch to state 2".

Move forward/backward N cells, then switch to state S

This is a tad more tricky, but still not bad. We need to add N states s_1, s_2, ... s_n:

(State,Symbol)	(State,Symbol,Direction)
(s_1, any)	(s_2, nothing, forward)
(s_1, any)	(s_2, nothing, forward)
...	...
(s_(n-1), any)	(s_n, nothing, forward)
(s_n, any)	(S, nothing, forward)

Marking the tape and Moving to a mark

We can add the ability to add a marker to a cell on the tape without erasing the symbol already there, and then use a version of the "move to symbol A" instruction. The way we do that is by modifying the set of symbols that we can have on the tape.

Suppose we wanted to be able to have two marks on a machine that uses the same four symbols as our original subtraction machine. We would expand the alphabet from four symbols to twelve: that is, from { '1', '-', ' ', '=' } to { ('1', none), ('1', m1), ('1', m2), (' ', none), (' ', m1), (' ', m2), ('-', none), ('-', m1), ('-', m2), ('=', none), ('=', m1), ('=', m2) }.

So when we write a mark, we're really changing the symbol on the tape from something like ('1', none) to ('1', m1). And when we move forward to a mark, we're just doing move forward to (anything, m1).

Adding Variables

We can add "variables" to the machine by increasing the set of states. A variable is a part of the state of the machine where we can store the a symbol or a marker. The easiest way to add them is to just multiply the number of states by the number of symbols that can be stored in the variable. For example, in our "subtraction" machine, we had four states and three symbols. If we wanted to have a variable that could remember a symbol, we would expand to 12 states: each state would have the "original" state from the machine, plus it would "encode" the value of the variable. So if we called the variable x, the states would be {(1, x='1'), (1,x='-'), (1,x='='), (1,x=' '),(2, x='1'), (2,x='-'), (2,x='='), (2,x=' '),(3, x='1'), (3,x='-'), (3,x='='), (3,x=' '),(4, x='1'), (4,x='-'), (4,x='='), (4,x=' ')}.

Using the variable, we can add "instructions" to read and write variables. Read instructions change both the numbered state and set the value of the variable to the symbol on the tape; write instructions change the numbered state and write the symbol stored in the variable onto the tape.

Copying Sections of Tape

We can copy sections of tape using the pieces we described above. To be able to do it, we need to be able to add a few things to the machine.

1. We need to add some states to the machine: a few states for each character in the alphabet that can be copied (one set of states for copying forward; one for copying backward).
   
2. We need to add three markers: one to mark the beginning of the region to be copied (the source region); one to mark the end of the source region; and one to mark the beginning of the place to copy to (the target region).
   
3. We need to add states for seeking markers.
   

To set up to do a copy, you need to place the three marks; and you need to know whether the place to copy to is before or after the section you want to copy. For now, let's assume it's after. Then you need to position the head at the start of of the target region. (Which you can do with a seek for the mark.)

Now, to do the copy:

1. Seek back from the target mark until you reach either the start or the
   end of copy region marks.
   
2. If you get the start mark before you see an end mark, that means that you finished the copy; so just seek back to the target mark, and then stop.
   
3. If you get the end mark first, then there's more to copy. So seek
   back to the start mark.
   
4. Read the symbol from the start mark into a variable; erase the start mark, and move forward one cell. Write the start mark onto the cell. (If the "end" mark is on that cell, it gets erased by the start mark.)
   
5. Seek forward to the target mark. When you find it, write the symbol stored in the variable, and erase the target mark, step forward, and write the target mark.
   
6. Now, you've finished copying one character; go back to the beginning,
   and keep doing this until the "end" mark gets erased.
   

Using the Extensions: Multiplication on the Turing Machine

Now, to show why it was worth all the trouble of figuring out how to add all of those extensions, we'll describe how to build a Turing machine that does multiplication. Basically, it takes two numbers in unary on the tape, like "111*1111=", and runs until it's written the product after the "=": "111*1111=111111111111".

So here's what the machine does:

1. Put "start" and "end" marks at the beginning and end of the second number on the tape.
   
2. Put a "counter" mark at the start of the first number on the tape.
   
3. Put a "target" mark at the "=" on the tape.
   
4. Scan back to the counter mark. If it's on "*", halt. If not, move it forward by one cell.
   
5. Do a copy from the start and end marks to the target mark.
   
6. Put the target mark on the cell after the last digit that you copied.
   
7. Scan back to the "start" mark, and replace it with the end mark.
   
8. Scan back to the character after the "*", and write the start mark.
   
9. Go back to step 4.
   

Just to give you an idea of how an algorithmic description of the machine these extensions makes things easier to read, here's the state transition table for a turing machine, which includes some of our extensions, for essentially this multiplication algorithm (I found this program here after I wrote the algorithm above, so it's not an exact match.)

# Turing machine to multiply two numbers:
# Number n is represented by string of n+1 1's.
# Initially, tape is assumed to be in form of _n1_n2_ (where _ is blank),
# and head is assumed to be positioned at leftmost non-blank square.
# Initial internal machine state is "start".
# At halt, tape is _n1_n2_n3_, where n3=n1*n2,
# and head is positioned at leftmost non-blank square.

State,Symbol	State,SymbolToWrite, Direction	comment
start, 1	move1right, W, R	# mark first bit of 1st argument
move1right, 1	move1right, 1, R	# move right til past 1st argument
move1right, _	mark2start, _, R	# square between 1st and 2nd arguments found
mark2start, 1	move2right, Y, R	# mark first bit of 2nd argument
move2right, 1	move2right, 1, R	# move right til past 2nd argument
move2right, _	initialize, _, R	# square between 2nd argument and answer found
initialize, _	backup, 1, L	# put a 1 at start of answer
backup, _	backup, _, L	# move back to leftmost unused bit of 1st arg
backup, 1	backup, 1, L	# ditto
backup, Z	backup, Z, L	# ditto
backup, Y	backup, Y, L	# ditto
backup, X	nextpass, X, R	# in position to start next pass
backup, W	nextpass, W, R	# ditto
nextpass, _	finishup, _, R	# if square is blank, we're done. finish up
nextpass, 1	findarg2, X, R	# if square is not blank, go to work. mark bit
findarg2, 1	findarg2, 1, R	# move past 1st argument
findarg2, _	findarg2, _, R	# square between 1st and 2nd arguments
findarg2, Y	testarg2, Y, R	# start of 2nd arg. skip this bit, copy rest
testarg2, _	cleanup2, _, L	# if blank, we are done with this pass
testarg2, 1	findans, Z, R	# if not, increment ans. mark bit, move there
findans, 1	findans, 1, R	# still in 2nd argument
findans, _	atans, _, R	# square between 2nd argument and answer
atans, 1	atans, 1, R	# move through answer
atans, _	backarg2, 1, L	# at end of answer--write a 1 here, go back
backarg2, 1	backarg2, 1, L	# move left to first unused bit of 2nd arg
backarg2, _	backarg2, _, L	# ditto
backarg2, Z	testarg2, Z, R	# just past it. move right, and test it
backarg2, Y	testarg2, Y, R	# ditto
cleanup2, 1	cleanup2, 1, L	# move back through answer
cleanup2, _	cleanup2, _, L	# square between 2nd arg and answer
cleanup2, Z	cleanup2, 1, L	# restore bits of 2nd argument
cleanup2, Y	backup, Y, L	# done with that. backup to start next pass
finishup, Y	finishup, 1, L	# restore first bit of 2nd argument
finishup, _	finishup, _, L	# 2nd argument restored, move back to 1st
finishup, X	finishup, 1, L	# restore bits of 1st argument
finishup, W	almostdone, 1, L	# restore first bit of 1st arg. almost done
almostdone, _	halt, _, R	# done with work. position properly and halt