The intensional content of Rice's theorem

ABSTRACT

The proofs of major results of Computability Theory like Rice, Rice-Shapiro or Kleene's fixed point theorem hidemore information of what is usually expressed in theirrespective statements. We make this information explicit, allowing to state stronger, complexity theoretic-versions of all these theorems. In particular, we replace the notion of extensional set of indices of programs, by a set of indices of programs having not only the same extensional behavior but also similar complexity (Complexity Clique). We prove, under very weak complexity assumptions, that any recursive Complexity Clique is trivial, and any r.e. Complexity Clique is an extensional set (and thus satisfies Rice-Shapiro conditions). This allows, for instance, to use Rice's argument to prove that the property of having polynomial complexity is not decidable, and to use Rice-Shapiro to conclude that it is not even semi-decidable. We conclude the paper with a discussion of "complexity-theoretic" versions of Kleene's Fixed Point Theorem.

REFERENCES

• 1: Roberto M. Amadio, Synthesis of max-plus quasi-interpretations, Fundamenta Informaticae, v.65 n.1-2, p.29-60, January 2005
• 2: Andrea Asperti , Agata Ciabattoni, Effective Applicative Structures, Proceedings of the 6th International Conference on Category Theory and Computer Science, p.81-95, August 07-11, 1995
• 3: Andrea Asperti , Luca Roversi, Intuitionistic Light Affine Logic, ACM Transactions on Computational Logic (TOCL), v.3 n.1, p.137-175, January 2002 [doi>10.1145/504077.504081]
• 4: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 5: Manuel Blum, On Effective Procedures for Speeding Up Algorithms, Journal of the ACM (JACM), v.18 n.2, p.290-305, April 1971 [doi>10.1145/321637.321648]
• 6: E. Börger. Berechenbarkeit, Komplexität, Logik. Friedr. Vieweg & Sohn, Braunshweig, 1986.
• 7: A. Borodin, Computational Complexity and the Existence of Complexity Gaps, Journal of the ACM (JACM), v.19 n.1, p.158-174, Jan. 1972 [doi>10.1145/321679.321691]
• 8: N. J. Cutland. Computability: An Introduction to Recursive Function Theory. Cambridge University Press, Cambridge, UK, 1986.
• 9: Ugo Dal Lago , Patrick Baillot, On light logics, uniform encodings and polynomial time, Mathematical Structures in Computer Science, v.16 n.4, p.713-733, August 2006 [doi>10.1017/S0960129506005421]
• 10: J.C.E. Dekker and J. Myhill. Some theorems on classes of recursively enumerable sets. Trans. Amer. Math. Soc., 89, pp. 25--59, 1958.
• 11: P. Freyd , P. Mulry , G. Rosolini , D. Scott, Extensional PERs, Information and Computation, v.98 n.2, p.211-227, June 1992 [doi>10.1016/0890-5401(92)90019-C]
• 12: Torben Amtoft Hansen , Thomas Nikolajsen , Jesper Larsson Träff , Neil D. Jones, Experiments with Implementations of Two Theoretical Constructions, Proceedings of the Symposium on Logical Foundations of Computer Science: Logic at Botik '89, p.119-133, July 03-08, 1989
• 13: J. Hartmanis and R.E. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117, pp. 285--306, 1965.
• 14: Neil D. Jones, Constant time factors do matter, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.602-611, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167244]
• 15: D. Kozen. Indexing of subrecursive classes. Theoretical Computer Science, 11, pp. 277--301, 1980.
• 16: L. H. Landweber , E. L. Robertson, Recursive Properties of Abstract Complexity Classes, Journal of the ACM (JACM), v.19 n.2, p.296-308, April 1972 [doi>10.1145/321694.321702]
• 17: F. D. Lewis, Unsolvability considerations in computational complexity, Proceedings of the second annual ACM symposium on Theory of computing, p.22-30, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805145]
• 18: G. Lischke. Über die erfüllung gewisser erhaltungssätze durch kompliziertheitsmasse. Zeit. Math. Log. Grund. Math., 21, pp. 159--166, 1975.
• 19: G. Lischke. Natürliche kompliziertheitsmasse und erhaltungssätze i. Zeit. Math. Log. Grund. Math., 22, pp.413--418, 1976.
• 20: G. Lischke. Natürliche kompliziertheitsmasse und erhaltungssätze ii. Zeit. Math. Log. Grund. Math., 23, pp. 193--200, 1977.
• 21: E. M. McCreight , A. R. Meyer, Classes of computable functions defined by bounds on computation: Preliminary Report, Proceedings of the first annual ACM symposium on Theory of computing, p.79-88, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805423]
• 22: J. Myhill, J.C. Shepherdson. Effective operations on partial recursive functions. Zeit. Math. Log. Grund. Math., 1, pp.310--317, 1955.
• 23: P.G. Odifreddi. Classical Recursion Theory: the Theory of Functions and Sets of Natural Numbers, volume 125 of Studies in Logic and the Foundations of Mathematics. Elsevier, 1997.
• 24: P.G. Odifreddi. Classical Recursion Theory, Volume II, volume 143 of Studies in Logic and the Foundations of Mathematics. Elsevier, 1999.
• 25: J.G. Rice. Classes of recursively enumerable set and their decision problems. Trans. Amer. Math. Soc., 74, pp.358--366, 1953.
• 26: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 27: N. Shapiro. Degrees of computability. Transactions of the American Mathematical Society, 82, pp.281--299, 1956.
• 28: Paul R. Young, Toward a Theory of Enumerations, Journal of the ACM (JACM), v.16 n.2, p.328-348, April 1969 [doi>10.1145/321510.321525]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Machine-independent complexity**

General Terms:
Theory

Keywords:
complexity, computability, recursion theory