Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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
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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Mathieu Hoyrup Connect in order to contact the contributor
Submitted on : Wednesday, April 27, 2016 - 1:43:02 PM
Last modification on : Thursday, January 20, 2022 - 5:26:12 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