The decidable properties of subrecursive functions

DOI10.4230/LIPICS.ICALP.2016.108zbMATH Open1388.68140OpenAlexW2537783236MaRDI QIDQ4598249FDOQ4598249

Authors: Mathieu Hoyrup 

Publication date: 19 December 2017

Full work available at URL: https://hal.inria.fr/hal-01308224

Recommendations

• scientific article; zbMATH DE number 1759844
• Decidable subspaces and recursively enumerable subspaces
• A decidable subclass of finitary programs
• Decidability, Recursive Enumerability and Kleene Hierarchy ForL-Subsets
• Decidable subcases of the equivalence problem for recursive program schemes
• The decidability of functional decomposition problem
• Decidability results for primitive recursive algorithms
• Decidability in the logic of subsequences and supersequences
• Finitely recursive programs: decidability and bottom-up computation
• Decidability problems for self-induced systems generated by a substitution

zbMATH Keywords

Kolmogorov complexitycompressibilityRice theoremsubrecursive classdecidable property

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursive functions and relations, subrecursive hierarchies (03D20)

Cited In (4)

• Intensional Kleene and Rice theorems for abstract program semantics
• The fixed-point property for represented spaces
• A note on the decidability of subword inequalities
• Algorithmic networks: central time to trigger expected emergent open-endedness

This page was built for publication: The decidable properties of subrecursive functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598249)