2026-07-21T14:56:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6243 2024-03-06T10:37:52Z ddc:004 open_access

The Decidable Properties of Subrecursive Functions Hoyrup, Mathieu Rice theorem subrecursive class decidable property Kolmogorov complexity compressibility 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathieu Hoyrup 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.108 urn:nbn:de:0030-drops-62435 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.108 eng https://creativecommons.org/licenses/by/3.0/legalcode