Skip to Main content Skip to Navigation
Reports

A Rice-like theorem for primitive recursive functions

Mathieu Hoyrup 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We provide an explicit characterization of the properties of primitive recursive functions that are decidable or semi-decidable, given a primitive recursive index for the function. The result is much more general as it applies to any c.e. class of total computable functions. This is an analog of Rice and Rice-Shapiro theorem, for restricted classes of total computable functions.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download

https://hal.inria.fr/hal-01130868
Contributor : Mathieu Hoyrup <>
Submitted on : Thursday, March 12, 2015 - 2:42:13 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Long-term archiving on: : Monday, April 17, 2017 - 11:06:59 AM

File

ricelike.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01130868, version 1

Collections

Citation

Mathieu Hoyrup. A Rice-like theorem for primitive recursive functions. [Research Report] Inria Nancy - Grand Est (Villers-lès-Nancy, France); Loria. 2015. ⟨hal-01130868⟩

Share

Metrics

Record views

196

Files downloads

119