Document Open Access Logo

On the Information Carried by Programs about the Objects They Compute

Authors Mathieu Hoyrup, Cristóbal Rojas

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.447.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Mathieu Hoyrup
Cristóbal Rojas

Cite As Get BibTex

Mathieu Hoyrup and Cristóbal Rojas. On the Information Carried by Programs about the Objects They Compute. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 447-459, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.447

Abstract

In computability theory and computable analysis, finite programs can compute infinite objects. Presenting a computable object via any program for it, provides at least as much information as presenting the object itself, written on an infinite tape. What additional information do programs provide? We characterize this additional information to be any upper bound on the Kolmogorov complexity of the object. Hence we identify the exact relationship between Markov-computability and Type-2-computability. We then use this relationship to obtain several results characterizing the computational and topological structure of Markov-semidecidable sets.

Subject Classification

Keywords
  • Markov-computable
  • representation
  • Kolmogorov complexity
  • Ershov topology

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. G. S. Ceitin. Algorithmic operators in constructive metric spaces. Trudy Matematiki Instituta Steklov, 67:295-361, 1962. English translation: American Mathematical Society Translations, series 2, 64:1-80, 1967. Google Scholar
  2. Matthew de Brecht. Quasi-polish spaces. Ann. Pure Appl. Logic, 164(3):356-381, 2013. Google Scholar
  3. Rusins Freivalds and Rolf Wiehagen. Inductive inference with additional information. Journal of Information Processing and Cybernetics, 15:179-185, 1979. Google Scholar
  4. Richard M. Friedberg. Un contre-exemple relatif aux fonctionnelles récursives. Comptes Rendus de l'Académie des Sciences, 247:852-854, 1958. Google Scholar
  5. Andrzej Grzegorczyk. On the definitions of computable real continuous functions. Fundamenta Mathematicae, 44:61-71, 1957. Google Scholar
  6. Peter Hertling. Computable real functions: Type 1 computability versus Type 2 computability. In CCA, 1996. Google Scholar
  7. G. Kreisel, D. Lacombe, and J.R. Schœ nfield. Fonctionnelles récursivement définissables et fonctionnelles récursives. Comptes Rendus de l'Académie des Sciences, 245:399-402, 1957. Google Scholar
  8. Boris A. Kushner. The constructive mathematics of A. A. Markov. Amer. Math. Monthly, 113(6):559-566, 2006. Google Scholar
  9. Daniel Lacombe. Extension de la notion de fonction récursive aux fonctions d?une ou plusieurs variables réelles I-III. Comptes Rendus Académie des Sciences Paris, 240,241:2478-2480,13-14,151-153, 1955. Google Scholar
  10. A. A. Markov. On the continuity of constructive functions (russian). Uspekhi Mat. Nauk, 9:226-230, 1954. Google Scholar
  11. J. Myhill and J. C. Shepherdson. Effective operations on partial recursive functions. Mathematical Logic Quarterly, 1(4):310-317, 1955. Google Scholar
  12. Marian B. Pour-El. A comparison of five "computable" operators. Mathematical Logic Quarterly, 6(15-22):325-340, 1960. Google Scholar
  13. H. G. Rice. Classes of recursively enumerable sets and their decision problems. Transactions of the American Mathematical Society, 74(2):pp. 358-366, 1953. Google Scholar
  14. Hartley Jr. Rogers. Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge, MA, USA, 1987. Google Scholar
  15. C.P. Schnorr. Optimal enumerations and optimal gödel numberings. Mathematical systems theory, 8(2):182-191, 1974. Google Scholar
  16. Matthias Schröder. Extended admissibility. Theoretical Computer Science, 284(2):519-538, 2002. Google Scholar
  17. Victor L. Selivanov. Index sets in the hyperarithmetical hierarchy. Siberian Mathematical Journal, 25:474-488, 1984. Google Scholar
  18. N. Shapiro. Degrees of computability. Transactions of the American Mathematical Society, 82:281-299, 1956. Google Scholar
  19. Dieter Spreen. Representations versus numberings: on the relationship of two computability notions. Theoretical Computer Science, 262(1):473-499, 2001. Google Scholar
  20. Alan Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42:230-265, 1936. Google Scholar
  21. Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact