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.
For example, imagine we had 4 symbols like the subtraction machine: "1", " ", "-", and "=". Remember, for state one, the part of the transition function was:
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:
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).
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.
Now, to do the copy:
So here's what the machine does:
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.- 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).
- 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).
- We need to add states for seeking markers.
Now, to do the copy:
- Seek back from the target mark until you reach either the start or the
end of copy region marks.
- 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.
- If you get the end mark first, then there's more to copy. So seek
back to the start mark.
- 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.)
- 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.
- 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:
- Put "start" and "end" marks at the beginning and end of the second number on the tape.
- Put a "counter" mark at the start of the first number on the tape.
- Put a "target" mark at the "=" on the tape.
- Scan back to the counter mark. If it's on "*", halt. If not, move it forward by one cell.
- Do a copy from the start and end marks to the target mark.
- Put the target mark on the cell after the last digit that you copied.
- Scan back to the "start" mark, and replace it with the end mark.
- Scan back to the character after the "*", and write the start mark.
- Go back to step 4.
# 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 |
posted by MarkCC at
1:36 PM
|
1 comments
RSS