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 metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01308224
Contributor : Mathieu Hoyrup <>
Submitted on : Wednesday, April 27, 2016 - 1:43:02 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Long-term archiving on : Tuesday, November 15, 2016 - 2:53:45 PM

File

ricelike.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

412

Files downloads

957