Comparing Computational Power 

It is standard to establish that one computational model, e.g.
recursive functions, is strictly stronger—-from the computational point
of view—-than another model, primitive recursive functions, for example,
by showing that the functions computed by the second model are a
proper subset of those computed by the first.  Another standard method
to show that a model, such as the untyped lambda calculus, is at least as
powerful—-computationally speaking—-as another, the partial recursive
functions, say, is to demonstrate that the former can simulate all partial
functions of the latter under some suitable encoding of the domain.

The problem we raise is the incompatibility of these two
methods of comparing computational power.  There are examples 
when one of two models is at least as powerful as the other by
the second method, but weaker by the first.

On the positive side, we prove that (1) both the recursive and partial
recursive functions are robust, in the sense that no encoding can make
them equivalent to a hyper-recursive model, and that (2) the recursive
functions are strictly more powerful than the primitive recursive functions,
even according to the second approach.

(with Udi Boker)