The disadvantage is that it’s hard to reason about programs at this level. Computations in the functional model have simple specifications—the function to be computed—and while proving that a program satisfies the specification may be hard, it’s at least a clearly defined notion. Under the imperative model, it can be difficult even to write a specification, much less determine whether an implementation satisfies it.

Now that we have a couple of different ways to think about computation, let’s think about what we mean by computers and what makes them unusual as a kind of mechanism.

COMPUTERS

Although computation always involves the manipulation of representations, the modern digital computer has the additional property that those procedures are themselves representations. They can be manipulated like any other data: copied, modified, erased, etc. Procedures differ from other representations only in the machine is able to interpret (execute) them. This provides us with one of the two defining characteristics of modern digital computers: programmability.

Programmability allows a single device to serve many different functions, simply by changing a stored representation inside the device. Although easy to take for granted, it is this programmability that makes computers the social and economic force that they are today. Computers could never have become economically viable if consumers had to buy separate machines for email, text processing, and Web browsing.

The second defining property of modern digital computers is their use of a single uniform meta-representation for all types of data, namely text. Computer text is like any other text— strings of symbols drawn from a fixed alphabet. The only interesting difference from any other text is that it uses an alphabet with only two symbols, conventionally called 0 and 1. The choice of a binary alphabet is ultimately a matter of engineering convenience: It’s easier to make a reliable electronic memory circuit if it only has to reliably distinguish between two symbols. And over the last 50 years, we’ve

devised clever ways of encoding other representations as binary text strings, including human text, tree and graph structures, pictures, and sound.

 

META-PROGRAMMING
Modern digital computers are charac-
terized by:
• A unified meta-representation (bi-
nary text strings) in which all other
representations can be encoded.

 

The fact that procedures are stored in the same bit-string format as other data has profound consequences; it allows us to write meta-programs that examine, manipulate, and even create other procedures.

While programmability makes computer hardware economically viable, meta-programmability makes software economically viable. Humans are the scarcest and most expensive resource in the computer industry. So just as the Industrial Revolution required the use of machines to make machines, software engineering requires the use of software to make software. Consequently, the over whelming historical trend in software development has been to automate more and more of the development task, even at the expense of writing less efficient programs that require more powerful computers.

All the tools we take for granted as programmers—compilers, debuggers, profilers, static checkers, testing rigs, and even source-code management systems—are meta-programs. They automate mundane aspects of programming, freeing you to focus on the tasks that require human creativity.

SIMULATION

Although all modern computers share
the same broad traits, they can’t nec-
essarily run one another’s programs.
Yet any computer can at least store any
other computer’s programs, because
all modern computers store data as
bit strings. Given that, we can write a
meta-program for one computer to in-
terpret or emulate the instruction set
of another. The emulator makes the
machines behaviorally equivalent.

UNIVERSALIT Y

The first machines that could simulate other computers were designed by British mathematician Alan Turing, and so are now referred to as Turing machines [ 1]. Most Turing machines weren’t even programmable, but Turing showed there was a particular kind of Turing machine, which he called the Universal Machine, which could take representations of other Turing machines and simulate them. That meant the Universal Machine was not only programmable, it could compute anything that any Turing machine could compute.

The details of Turing machines
aren’t important to this discussion.
What matters is that they can simulate
all the computers we’ve managed to
think up, and consequently can com-
pute anything those computers can
compute. This means any computer
that’s able to simulate Turing’s Uni-
versal Machine is also able to simu-
late any computer, and therefore able
to compute anything we know how to
compute. This property of being able
to simulate Turing machines, and
therefore being able to simulate any
known computer, is called “Turing
completeness,” “Turing equivalence,”
or just “universality.”
The amazing thing is that nearly
all digital computers are Turing com-
plete. In fact, some stunningly simple