Demonstrating that two computational models compute the same class of functions requires constructing a simulation where each basic step of one model is simulated by one or more steps of the other.
When two different systems can do exactly the same jobs, even if they work in different ways—showing they're equally powerful.
Functions (in mathematics/computation)(as used in computational theory)
Rules that take inputs and produce specific outputs; think of it like a machine where you put something in and always get the same thing out for the same input.
Simulation(as used in computational theory)
A computer model or calculation that mimics how a real system works, used to predict outcomes or test ideas without running the actual system.
In particular, a RAM machine \(A\) consists of a finite sequence of instructions (or program) \(\langle \pi_1,\ldots,\pi_n \rangle\) expressing how numerical operations (typically addition and subtraction) are to be applied to a sequence of registers \(r_1,r_2, \dots\) in which values may be stored and retrieved directly by their index. Showing that one of these models \(\mathfrak{M}_1\) determines the same class of functions as some reference model \(\mathfrak{M}_2\) (such as \(\mathfrak{T}\))