Comparing Computational Power

It is common practice to compare the computational power ofdifferent models of computation. For example, the recursivefunctions are strictly more powerful than the primitive recursivefunctions, 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 also standardto base comparisons on "simulation". For example, one says thatthe (untyped) lambda calculus is as powerful—computationallyspeaking—as the partial recursive functions, because thelambda calculus can simulate all partial recursive functionsby encoding the natural numbers as Church numerals. The problem is that unbridled use of these two distinct waysof comparing power allows one to show that some computationalmodels (sets of partial functions) are strictly stronger thanthemselves! We argue that a better definition is that modelA is strictly stronger than B if A can simulate B via some encoding,whereas B cannot simulate A under any encoding. We show thatwith this definition, too, the recursive functions are strictlystronger than the primitive recursive. We also prove that therecursive functions, partial recursive functions, and Turingmachines are "complete", in the sense that no injective encodingcan make them equivalent to any "hypercomputational" model.¹