760
Modeling Arithmetic, Computation, and Languages
We probably consider ourselves to be finite-state machines and imagine that
our brains, being composed of a large number of cells, can take on only a finite,
although immensely large, number of configurations, or states. We feel sure, however, that if someone presented us with an arbitrarily long string of 0s followed by
an arbitrarily long string of 1s, we could detect whether the number of 0s and 1s
was the same. Let’s think of some techniques we might use.
For small strings of 0s and 1s, we could just look at the strings and decide.
Thus, we can tell without great effort that 000111 [ S and that 00011 o S. However, for the string
0000000000000001111111111111111
we must devise another procedure, probably resorting to counting. We would
count the number of 0s received, and when we got to the first 1, we would write
the number of 0s down (or remember it) for future reference; then we would begin
counting 1s. (This process is what we did mentally for smaller strings.)
However, we have now made use of some extra memory, because when we
finished counting 1s, we would have to retrieve the number representing the total
number of 0s to make a comparison. But such information retrieval is what the
finite-state machine cannot do; its only capacity for remembering input is to have
a given input symbol send it to a particular state. We have already seen that no
finite-state machine can “remember” 0
n
for arbitrarily large n because it runs out
of distinct states. In fact, if we try to solve this problem on a real computer, we
encounter the same difficulty. If we set a counter as we read in 0s, we might get an
overflow because our counter can go only so high. To process 0
n
1
n
for arbitrarily
large n requires an unlimited auxiliary memory for storing the value of our counter, which in practice cannot exist.
Another way we humans might attack the problem of recognizing S is to wait
until the entire string has been presented. Then we would go to one end of the
string and cross out a 0, go to the other end and cross out a 1, and then continue
this back-and-forth operation until we ran out of 0s or 1s. The string belongs to S
if and only if we run out of both at the same time. Although this approach sounds
rather different from the first one, it still requires remembering each of the inputs,
since we must go back and read them once the string is complete. The finite-state
machine, of course, cannot reread input.
We have come up with two computational procedures—algorithms—to decide, given a string of 0s and 1s, whether that string belongs to S = 50
n
1
n
0 n ≥ 06.
Both require some form of additional memory unavailable in a finite-state
machine. Evidently, the finite-state machine is not a model of the most general
form of computational procedure.
Definition
To simulate more general computational procedures than the finite-state
machine can handle, we use a Turing machine, proposed by the British
mathematician Alan M. Turing in 1936. A Turing machine is essentially
a finite-state machine with the added ability to reread its input and also to
erase and write over its input. It also has unlimited auxiliary memory. Thus,
the Turing machine overcomes the deficiencies we noted in finite-state machines. Unlimited auxiliary memory makes the Turing machine a hypothetical
“machine”—a model—not a real device.
Modeling Arithmetic, Computation, and Languages
We probably consider ourselves to be finite-state machines and imagine that
our brains, being composed of a large number of cells, can take on only a finite,
although immensely large, number of configurations, or states. We feel sure, however, that if someone presented us with an arbitrarily long string of 0s followed by
an arbitrarily long string of 1s, we could detect whether the number of 0s and 1s
was the same. Let’s think of some techniques we might use.
For small strings of 0s and 1s, we could just look at the strings and decide.
Thus, we can tell without great effort that 000111 [ S and that 00011 o S. However, for the string
0000000000000001111111111111111
we must devise another procedure, probably resorting to counting. We would
count the number of 0s received, and when we got to the first 1, we would write
the number of 0s down (or remember it) for future reference; then we would begin
counting 1s. (This process is what we did mentally for smaller strings.)
However, we have now made use of some extra memory, because when we
finished counting 1s, we would have to retrieve the number representing the total
number of 0s to make a comparison. But such information retrieval is what the
finite-state machine cannot do; its only capacity for remembering input is to have
a given input symbol send it to a particular state. We have already seen that no
finite-state machine can “remember” 0
n
for arbitrarily large n because it runs out
of distinct states. In fact, if we try to solve this problem on a real computer, we
encounter the same difficulty. If we set a counter as we read in 0s, we might get an
overflow because our counter can go only so high. To process 0
n
1
n
for arbitrarily
large n requires an unlimited auxiliary memory for storing the value of our counter, which in practice cannot exist.
Another way we humans might attack the problem of recognizing S is to wait
until the entire string has been presented. Then we would go to one end of the
string and cross out a 0, go to the other end and cross out a 1, and then continue
this back-and-forth operation until we ran out of 0s or 1s. The string belongs to S
if and only if we run out of both at the same time. Although this approach sounds
rather different from the first one, it still requires remembering each of the inputs,
since we must go back and read them once the string is complete. The finite-state
machine, of course, cannot reread input.
We have come up with two computational procedures—algorithms—to decide, given a string of 0s and 1s, whether that string belongs to S = 50
n
1
n
0 n ≥ 06.
Both require some form of additional memory unavailable in a finite-state
machine. Evidently, the finite-state machine is not a model of the most general
form of computational procedure.
Definition
To simulate more general computational procedures than the finite-state
machine can handle, we use a Turing machine, proposed by the British
mathematician Alan M. Turing in 1936. A Turing machine is essentially
a finite-state machine with the added ability to reread its input and also to
erase and write over its input. It also has unlimited auxiliary memory. Thus,
the Turing machine overcomes the deficiencies we noted in finite-state machines. Unlimited auxiliary memory makes the Turing machine a hypothetical
“machine”—a model—not a real device.