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).
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.
https://hal.inria.fr/hal-01308224 Contributor : Mathieu HoyrupConnect 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
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⟩