On the information carried by programs about the objects they compute

DOI10.1007/s00224-016-9726-9zbMath1393.68085OpenAlexW1485942862MaRDI QIDQ1693999

Mathieu Hoyrup, Cristobal Rojas

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4933/

zbMATH Keywords

Kolmogorov complexityErshov topologyMarkov-computable

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

The fixed-point property for represented spaces ⋮ On the complexity of learning programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Index sets in the hyperarithmetical hierarchy
• Extended admissibility.
• Quasi-Polish spaces
• Effective operations on partial recursive functions
• Degrees of Computability
• On the definitions of computable real continuous functions
• A Comparison of Five “Computable” Operators
• The Constructive Mathematics of A. A. Markov
• Optimal enumerations and optimal gödel numberings
• Index sets in Ershov's hierarchy
• Algorithmic operators in constructive metric spaces
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Representations versus numberings: On the relationship of two computability notions