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.
Type de document :
Rapport
[Research Report] Inria Nancy - Grand Est (Villers-lès-Nancy, France); Loria. 2015
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01130868
Contributeur : Mathieu Hoyrup <>
Soumis le : jeudi 12 mars 2015 - 14:42:13
Dernière modification le : mardi 2 octobre 2018 - 10:41:12
Document(s) archivé(s) le : lundi 17 avril 2017 - 11:06:59

Fichier

ricelike.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

156

Téléchargements de fichiers

88