FORMAL MODELS OF COMPUTATION

The theory of computing has advanced by adopting formal models of computation whose properties can be
explored mathematically. The most influential model was proposed by the mathematician Alan Turing in 1936.
Turing used the human as the model computing agent. He imagined a human, in a certain state of mind,
looking at a symbol on paper. The human reacts to the symbol on paper by
1 erasing the symbol, or erasing the symbol and writing a new symbol, or neither,
2 perhaps changing his or her state of mind as a result of contemplating the symbol, and then
3 contemplating another symbol on the paper, next to the first.
This model of computation captures the ability to accept input (from the paper), store information in
memory (also on the paper), take different actions depending on the input and the computing agent’s “state of
mind,” and produce output (also on the paper). Turing recast this drastically simple model of computation into
mathematical form, and derived some very fundamental discoveries about the nature of computation. In particular,
Turing proved that some important problems cannot be solved with any algorithm. He proved not that these
problems have no known solution; he proved that these problems cannot ever have a solution. For instance, he
proved that one will never be able to write one program that will be able to determine whether any other arbitrary
program will execute to a proper completion, or crash.
Hmmm... that’s too bad... it would be nice to have a program to check our work and tell us whether or not
our new program will ever crash.
The mathematical conception of Turing’s model of computation is called a Turing machine or TM. A TM
is usually described as a machine reading a tape.
● The tape contains symbols or blanks, and the tape can be infinitely long.
● The machine can read one symbol at a time, the symbol positioned under the “read/write head” of the TM.
● The machine can also erase the symbol, or write a new symbol, and it can then position the tape one
cell to the left or right.
● The machine itself can be in one of a finite number of states, and reading a symbol can cause the state
of the TM to change.
● A special state is the halting state, which is the state of the machine when it terminates normally.
● When the machine starts, it is in state 1, it is positioned at the extreme left end of the tape, and the tape
extends indefinitely to the right.
A particular TM will have a set of instructions it understands. Each instruction consists of a 5-tuple (rhymes
with couple), which is a mathematical way of saying that one instruction consists of five values. These values are
1 the current state
2 the current symbol being read
3 the symbol with which to replace the current symbol
4 the next state to enter
5 the direction to move the tape (Right, Left, or Stationary)
As a first example, suppose a TM includes these three instructions (Δ means blank):
1 (1, 0, 1, 1, Right )
2 (1, 1, 0, 1, Right )
3 (1, Δ, Δ, halt, Stationary)
The first says that if the symbol being read is a 0, replace it with a 1 and move right. The second says that
if the symbol being read is a 1, replace it with a 0 and move right. The third says that if the symbol being read
is a blank, halt the machine without moving the tape.
Assume the tape presented to this TM contains the symbols:
1 1 0 1 0 1 0 0 Δ Δ Δ...
Starting in state 1, and positioned at the extreme left of the tape, the machine reads the symbol 1. Instruction
2 applies to this situation, so the instruction causes the 1 to be replaced by a 0, the machine state to remain 1,
and the machine to move 1 cell to the right on the tape.
Next the TM reads another 1. Instruction 2 applies again, so the TM changes the second 1 to a 0, and moves
right again, remaining in state 1.
When the TM reads the symbol 0, instruction 1 applies, so instruction 1 causes the 0 to be replaced by a 1,
the machine to stay in state 1, and the machine to move right once again.
As the machine advances down the tape, every 1 will be changed to a 0, and every 0 will be changed to
a 1. Finally, the machine will read a blank. In that case, instruction 3 will apply, and the machine will halt.
This simple TM is a machine for complementing (inverting) the bits of a binary number. The result of the
computation will be a tape that contains these symbols:

0 0 1 0 1 0 1 1 Δ Δ Δ...
Complementing the bits of a binary number is a frequently required task, so this is a useful TM.
A slightly more complex task is that of complementing and incrementing a binary number. That operation is
often used by computers to perform binary subtraction. In fact, in the “old days” when the only calculating
machines available were mechanical adding machines, people performed subtraction the same way in base 10,
using the 10’s complement method. To subtract 14 from 17 in base 10, they found the 9’s complement of 14, which
is 85 (subtract 1 from 9 to get the 8, and subtract 4 from 9 to get the 5). They incremented 85 by 1, to get 86, or
what’s called the 10’s complement. Adding 17 and 86 gave 103. Ignoring the carry digit gave the answer of 3!
To perform binary subtraction by the 2’s complement method, the subtrahend is complemented and
incremented, and then added to the minuend. For instance, to subtract 2 from 5, we can complement and increment
2, and add that to 5 to get 3:
010 2 (in base 2: 0 fours, 1 two, 0 units)
101 2 complemented (1s --> 0s; 0s --> 1s)
110 2 complemented & incremented
(adding 001 to 101 --> 110 in base 2)
+101 5 (1 four, 0 twos, 1 unit)
1011 3 (in base 2: 0 fours, 1 two, 1 unit --
ignore the carry bit to the left)

Since subtraction is often required, a TM for complementing and incrementing a binary number is interesting.
Here are the instructions for such a machine:
1 (1, 0, 1, 1, Right )
2 (1, 1, 0, 1, Right )
3 (1, Δ, Δ, 2, Left )
4 (2, 0, 1, 3, Right )
5 (2, 1, 0, 2, Left )
6 (3, 1, 1, 3, Right )
7 (3, 0, 0, 3, Right )
8 (3, Δ, Δ, halt, Stationary)
Instructions 1 and 2 are the same as for the simpler TM which complemented the bits on the tape.
Instruction 3 will apply when the TM has complemented all the bits and encountered the blank on the right end
of the tape. When that happens, the machine will go into state 2 and move left.
If the machine is in state 2 and encounters a 0, instruction 4 will cause the 0 to be replaced
by a 1, the machine to enter state 3, and move right. Once the machine is in state 3, instructions 6 and
7 will cause the machine to move right without further changing the contents of the tape. When
the machine finally encounters the blank on the right again, instruction 8 will cause the machine
to halt.
If the machine is in state 2 and encounters a 1, instruction 5 will cause the 1 to be replaced by a 0, the
machine to stay in state 2, and move left again. This will continue in such manner until the TM encounters a 0,
in which case instruction 4 will apply, as described in the previous paragraph.
Using the binary number 2 as the example again, the TM will create the following contents on the tape as
it executes:
0 1 0 Δ Δ original tape
1 0 1 Δ Δ complementing complete
1 0 0 Δ Δ after executing instruction 5
1 1 0 Δ Δ after executing instruction 4
1 1 0 Δ Δ halted after executing instruction 8
This TM works for many inputs, but not all. Suppose the original input tape were all zeros:
0 0 0 Δ Δ original tape

After the complementing is complete, and all the 0s become 1s, the TM will back up over the tape repeatedly
executing instruction 5. That is, it will back up changing each 1 to 0. In this case, however, the TM will never
encounter a 0, where instruction 4 would put the TM into state 3 and start the TM moving toward the end of the
tape and a proper halt.
Instead, the TM will ultimately encounter the first symbol on the tape, and instruction 5 will command it
to move again left. Since the machine can go no further in that direction, the machine “crashes.”
Likewise, the TM will crash if one of the symbols on the tape is something other than 1 or 0. There are
no instructions in this TM for handling any other symbol, so an input tape such as this will also cause the TM to
crash:
0 3 0 Δ Δ original tape
Another way a TM can fail is by getting into an infinite loop. If instruction 7 above specified a move to the
left instead of the right, certain input tapes containing only 1s and 0s would cause the TM to enter an endless
loop, moving back and forth endlessly between two adjacent cells on the tape.
Algorithms can be specified as TMs and, like all algorithms, TMs must be tested for correctness, given
expected inputs.