Generalizations of Rice's theorem, applicable to executable and non-executable formalisms



We formulate and prove two Rice-like theorems that characterize limitations on nameability of properties within a given naming scheme for partial functions. Such a naming scheme can, but need not be, an executable formalism. A programming language is an example of an executable naming scheme, where the program text names the partial function it implements. Halting is an example of a property that is not nameable in that naming scheme. The proofs reveal requirements on the naming scheme to make the characterization work. Universal programming languages satisfy these requirements, but also other formalisms can satisfy them. We present some non-universal programming languages and a non-executable specification language satisfying these requirements. Our theorems have Turing's well-known Halting Theorem and Rice's Theorem as special cases, by applying them to a universal programming language or Turing Machines as naming scheme. Thus, our proofs separate the nature of the naming scheme (which can, but need not, coincide with computability) from the diagonal argument. This sheds further light on how far reaching and simple the `diagonal' argument is in itself.
Original languageEnglish
Title of host publicationTuring-100
EditorsA. Voronkov
Publication statusPublished - 2012
Eventconference; Turing-100. The Alan Turing Centenary -
Duration: 1 Jan 2012 → …

Publication series

NameEPiC Series
ISSN (Print)2040-557X


Conferenceconference; Turing-100. The Alan Turing Centenary
Period1/01/12 → …
OtherTuring-100. The Alan Turing Centenary


Dive into the research topics of 'Generalizations of Rice's theorem, applicable to executable and non-executable formalisms'. Together they form a unique fingerprint.

Cite this