Information Technology Reference
In-Depth Information
some details. To be more precise, let's consider computers with the
following elements:
A CPU that can perform simple arithmetic and logical operations
Some type of input and output device(s), such as a keyboard
and monitor
Some main memory—to hold a simple program
A storage device that can be used to insert and remove disks,
tapes, or CDs. (With a floppy drive or the equivalent, com
puters effectively have infinite storage capabilities; we can
keep purchasing new disks when we fill the old. Even without
a builtin drive, a computer likely contains a plug for an ex
ternal drive or storage device, and we could use that capabil
ity to store any desired amount of information.)
Virtually all home computers satisfy these constraints. Some
computers are more restricted or are specialized for a particular
task. (For example, the electronics that control your microwave
oven are basically a computer designed to cook your food; your
car's engine is a computer created to move your car.) Although such
restricted computers have limited capabilities, fundamentally all of
today's computers for home, office, or a lab usually meet the listed
criteria. What are the capabilities of our typical personal computers
with the standard elements listed here? Remarkably, the answer re
lates to a theoretical model of a computer, called a Turing Machine.
What Are Turing Machines?
In 1936, Alan Turing first proposed a model for a computer,
now called a Turing Machine . Although the details of Turing
Machines require considerable discussion and a careful formalism,
the basic idea is that a Turing Machine consists of an infinite tape, a
readwrite head for the tape, a table of potential actions, a mecha
nism to keep track of where it is within a computation, and a sim
ple processor that reads the tape and responds according to the
table. The mechanism for keeping track of what has been accom
plished by the machine during processing is called a state .
To illustrate the idea of a Turing Machine, here are two (rela
tively) simple examples. In each case we use binary numbers to keep
 
Search WWH ::




Custom Search