The decidable properties of subrecursive functions

DOI10.4230/LIPICS.ICALP.2016.108MaRDI QIDQ4598249zbMATH OpenOpenAlexFDO

Authors Mathieu Hoyrup

Publication date 19 December 2017

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

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)

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

Cited in

(4)

• 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
• Intensional Kleene and Rice theorems for abstract program semantics

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)