machine simulation

views updated

machine simulation The process whereby one machine M1 can be made to simulate or behave like a second machine M2. There are a number of ways of formalizing simulation for each class of machines. For example, let there be functions g and h that perform encoding and decoding roles respectively: g : M1M2, h : M2M1

g encodes information for machine M1 and produces corresponding information for machine M2; h is the inverse function. Machine M2 is said to simulate machine M1 if it is possible to specify a translation algorithm such that, when given a program P1 for M1, it produces a corresponding program P2 for M2; further, the effect of P1 on M1 should be equivalent to the effect of

applying function g

then executing P2 on M2

then applying function h.

In symbols, P1 = h P2 g

An equally useful formulation has functions g : M1M2, h : M1M2

and the simulation criterion h P1 = P2 g

Machine simulation of this kind is generally discussed for idealized abstract machines, such as Turing machines, and for formal models of microprocessors. It provides a useful approach to defining the correctness of implementations. See also machine equivalence.