Comparing Computational Power

Logic Journal of the IGPL 14 (5):633-647 (2006)
  Copy   BIBTEX

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 . Side-by-side with this “containment” method of measuring power, it is also standard to base comparisons on “simulation”. For example, one says that the 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 distinct 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 show that with this definition, too, the recursive functions are strictly stronger 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.1

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Unary primitive recursive functions.Daniel E. Severin - 2008 - Journal of Symbolic Logic 73 (4):1122-1138.
Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
Ramsey's Theorem for Pairs and Provably Recursive Functions.Alexander Kreuzer & Ulrich Kohlenbach - 2009 - Notre Dame Journal of Formal Logic 50 (4):427-444.
Term rewriting theory for the primitive recursive functions.E. A. Cichon & Andreas Weiermann - 1997 - Annals of Pure and Applied Logic 83 (3):199-223.
Undecidability over Continuous Time.Jerzy Mycka & José Félix Costa - 2006 - Logic Journal of the IGPL 14 (5):649-658.
Provably total functions of Basic Arithemtic.Saeed Salehi - 2003 - Mathematical Logic Quarterly 49 (3):316.
Polynomially Bounded Recursive Realizability.Saeed Salehi - 2005 - Notre Dame Journal of Formal Logic 46 (4):407-417.
Accessible recursive functions.Stanley S. Wainer - 1999 - Bulletin of Symbolic Logic 5 (3):367-388.
A foundation for real recursive function theory.José Félix Costa, Bruno Loff & Jerzy Mycka - 2009 - Annals of Pure and Applied Logic 160 (3):255-288.
Fragments of $HA$ based on $\Sigma_1$ -induction.Kai F. Wehmeier - 1997 - Archive for Mathematical Logic 37 (1):37-49.

Analytics

Added to PP
2015-02-04

Downloads
10 (#1,025,836)

6 months
1 (#1,040,386)

Historical graph of downloads
How can I increase my downloads?

References found in this work

No references found.

Add more references