### Abstract

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 language | English |
---|---|

Title of host publication | Turing-100 |

Editors | A. Voronkov |

Publisher | EasyChair |

Pages | 168-180 |

Publication status | Published - 2012 |

Event | conference; Turing-100. The Alan Turing Centenary - Duration: 1 Jan 2012 → … |

### Publication series

Name | EPiC Series |
---|---|

Volume | 10 |

ISSN (Print) | 2040-557X |

### Conference

Conference | conference; Turing-100. The Alan Turing Centenary |
---|---|

Period | 1/01/12 → … |

Other | Turing-100. The Alan Turing Centenary |

## Fingerprint 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

Huizing, C., Kuiper, R., & Verhoeff, T. (2012). Generalizations of Rice's theorem, applicable to executable and non-executable formalisms. In A. Voronkov (Ed.),

*Turing-100*(pp. 168-180). (EPiC Series; Vol. 10). EasyChair.