Simulation in a Theory of Programmable Machines

In a theory of machines controlled by programs, automata-theoretic simulation can be presented simply and directly, and can be understood as an aspect of the algebraic structure of such machines.

Here the notions of product and homomorphism of devices in such a theory are presented, along with a notion of (computational) reducibility of one device to another. Simulation in the automata-theoretic sense is formally defined, and its validity as a technique for proving reducibility established uniformly.

The notions of device, product, homomorphism, and reducibility are then extended to model costs of computation evaluated a posteriori (in the manner of concrete complexity studies), and the validity of simulation as a proof technique established in this extended setting.