machine simulation

Show Summary Details

Quick Reference

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: M2M1g 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

g: M1M2, h: M2M1

applying function g

then executing P2 on M2

then applying function h.

In symbols, P1 = h P2g An equally useful formulation has functions g: M1M2, h: M1M2 and the simulation criterion h P1 = P2g 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.

P1 = h P2g

g: M1M2, h: M1M2

h P1 = P2g

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.