Comparing Computational Power

@misc{citeulike:383919, abstract = {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.}, author = {Boker, Udi and Dershowitz, Nachum }, citeulike-article-id = {383919}, eprint = {cs.LO/0510069}, keywords = {comparing, computational, power}, month = {Oct}, posted-at = {2005-11-08 16:15:31}, priority = {2}, title = {Comparing Computational Power}, url = {http://arxiv.org/abs/cs.LO/0510069}, year = {2005} }

TY - ELEC ID - citeulike:383919 L3 - citeulike-article-id:383919 TI - Comparing Computational Power N2 - 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. KW - comparing KW - computational KW - power AU - Boker, Udi AU - Dershowitz, Nachum PY - 2005/Oct/23/ UR - http://arxiv.org/abs/cs.LO/0510069 ER -