  It is common practice to compare the computational power of different models
of computation. For example, the recursive functions are strictly more powerful
than the primitive recursive functions, because the latter are a proper subset
of the former (which includes Ackermann's function). Side-by-side with this
"containment" method of measuring power, it is standard to use an approach
based on "simulation". For example, one says that the (untyped) lambda calculus
is as powerful--computationally speaking--as the partial recursive functions,
because the lambda calculus can simulate all partial recursive functions by
encoding the natural numbers as Church numerals.
  The problem is that unbridled use of these two ways of comparing power allows
one to show that some computational models are strictly stronger than
themselves! We argue that a better definition is that model A is strictly
stronger than B if A can simulate B via some encoding, whereas B cannot
simulate A under any encoding. We then show that the recursive functions are
strictly stronger in this sense than the primitive recursive. We also prove
that the recursive functions, partial recursive functions, and Turing machines
are "complete", in the sense that no injective encoding can make them
equivalent to any "hypercomputational" model.
