Given two machines, and
, why would you care to know
whether they are ``equivalent''? The most compelling answer is that
if you know
is equivalent to
then you know that you can
substitute
for
without changing the overall system
in which you do the substitution. This substitution principle is
extremely important. Many areas in Computer Science rely on this
principle. The most obvious example is in using a compiler. A
compiler transforms a program into (we hope) a more efficient one.
The source and target programs had better compute the same answer
given the same inputs; in this sense the two programs are equivalent,
and the target program is an efficient substitute for the source
program. Similarly, software engineering relies on the notion of
modularity where you can replace one component for another without
affecting the rest of the system; functional programming, equational
reasoning, and rewrite rule theory all rely on the principle of
substituting equals for equals, sometimes called referential
transparency; even caching protocols in a multiprocessor or
distributed system aim at keeping replicas equivalent (the ``cache
consistency'' problem) so that the existence of multiple versions is
hidden from the user.
Efficiency is one reason you might want to substitute one machine for
another. may have fewer states or fewer state variables or
fewer state transitions than
. In the real world, there are
other good reasons: cost, user-friendliness, maintainability,
portability, or just esthetics.