Evolving Algebras and Linear Time Hierarchy.
Andreas R. Blass, Yuri G. Gurevich · 1994
Devices, Models of Computation; Computation by Abstract Devices, Complexity Classes; Logics and Meanings of Programs, Semantics of Programming Languages 1 Introduction A program Q simulates a program P in lock-step under a given representation ae of states of P as states of Q if there is a constant c such that if P transforms a state A to a state A + in time ø then Q transforms ae(A) into ae(A + ) in time cø . (Cf. the related notions of real-time computation and simulation [R,S].) The constant c is the lag factor of the simulation. We speak about time rather than the number of steps because the number of steps may be too crude a measure of time and a more honest measure may be required. The representation function ae may be multi-valued, in which case Q transforms any ae(A) into some ae(A + ). The inverse function ae \\Gamma1 is usually single-valued. Neil Jones [J] calls a universal program U for a language L efficient if there is a constant c such that U simulates every ...