Skip to Main content Skip to Navigation
Conference papers

The decidable properties of subrecursive functions

Mathieu Hoyrup 1, *
* Corresponding author
1 CARTE - Theoretical adverse computations, and safety
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Mathieu Hoyrup <>
Submitted on : Wednesday, April 27, 2016 - 1:43:02 PM
Last modification on : Thursday, March 5, 2020 - 4:55:00 PM
Long-term archiving on: : Tuesday, November 15, 2016 - 2:53:45 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License




Mathieu Hoyrup. The decidable properties of subrecursive functions. International Colloquium on Automata, Languages, and Programming (ICALP) 2016, Jul 2016, Rome, Italy. ⟨10.4230/LIPIcs.ICALP.2016.108⟩. ⟨hal-01308224⟩



Record views


Files downloads