Technical Reports

The ICICS/CS Reading Room

UBC CS TR-77-07 Summary

Simulation in a Theory of Programmable Machines, July 1977 J. L. Baker

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.

If you have any questions or comments regarding this page please send mail to