The proofs of major results of Computability Theory like Rice, Rice-Shapiro or Kleene's fixed point theorem hide more information of what is usually expressed in their respective 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

A. Asperti (2008). The intensional content of Rice's theorem.. NEW YORK : ACM.

The intensional content of Rice's theorem.

ASPERTI, ANDREA
2008

Abstract

The proofs of major results of Computability Theory like Rice, Rice-Shapiro or Kleene's fixed point theorem hide more information of what is usually expressed in their respective 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
2008
POPL '08: The 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
113
120
A. Asperti (2008). The intensional content of Rice's theorem.. NEW YORK : ACM.
A. Asperti
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/61097
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact