The decidable properties of subrecursive functions

Mathieu Hoyrup 1, *
* Auteur correspondant
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : What can be decided or semidecided about a primitive recursive function, given a definition of that function by primitive recursion? What about subrecursive classes other than primitive recursive functions? We provide a complete and explicit characterization of the decidable and semidecidable properties. This characterization uses a variant of Kolmogorov complexity where only programs in a subrecursive programming language are allowed. More precisely, we prove that all the decidable and semidecidable properties can be obtained as combinations of two classes of basic decidable properties: (i) the function takes some particular values on a finite set of inputs, and (ii) every finite part of the function can be compressed to some extent.
Type de document :
Communication dans un congrès
International Colloquium on Automata, Languages, and Programming (ICALP) 2016, Jul 2016, Rome, Italy. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 12-15, 2016, Rome, Italy. 〈http://www.easyconferences.eu/icalp2016/〉. 〈10.4230/LIPIcs.ICALP.2016.108〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01308224
Contributeur : Mathieu Hoyrup <>
Soumis le : mercredi 27 avril 2016 - 13:43:02
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : mardi 15 novembre 2016 - 14:53:45

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Mathieu Hoyrup. The decidable properties of subrecursive functions. International Colloquium on Automata, Languages, and Programming (ICALP) 2016, Jul 2016, Rome, Italy. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 12-15, 2016, Rome, Italy. 〈http://www.easyconferences.eu/icalp2016/〉. 〈10.4230/LIPIcs.ICALP.2016.108〉. 〈hal-01308224〉

Partager

Métriques

Consultations de la notice

144

Téléchargements de fichiers

100