Abstract
In computability theory and computable analysis, finite programs can compute infinite objects. Such objects can then be represented by finite programs. Can one characterize the additional useful information contained in a program computing an object, as compared to having the object itself? Having a program immediately gives an upper bound on the Kolmogorov complexity of the object, by simply measuring the length of the program, and such an information cannot usually be derived from an infinite representation of the object. We prove that bounding the Kolmogorov complexity of the object is the only additional useful information. 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. This article is an extended version of Hoyrup and Rojas (2015), including complete proofs and a new result (Theorem 9).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
In its original form due to Kreisel-Lacombe-Shœnfield, this theorem is stated for functionals.
References
Čeitin, G.S.: 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
de Brecht, M.: Quasi-polish spaces. Ann. Pure Appl. Logic 164(3), 356–381 (2013)
Freivalds, R, Wiehagen, R.: Inductive inference with additional information. J. Inf. Process. Cybern. 15, 179–185 (1979)
Friedberg, R.M.: Un contre-exemple relatif aux fonctionnelles récursives. Comptes Rendus de l’Académie des Sciences 247, 852–854 (1958)
Grassin, J.: Index sets in Ershov’s hierarchy. J. Symb. Logic 39, 97–104, 3 (1974)
Grzegorczyk, A.: On the definitions of computable real continuous functions. Fundamenta Mathematicae 44, 61–71 (1957)
Hertling, P.: Computable real functions: Type 1 computability versus Type 2 computability. In: CCA (1996)
Hoyrup, M., Rojas, C.: On the information carried by programs about the objects they compute. In: Mayr, E. W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pp 447–459. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
Kreisel, G., Lacombe, D., Shøe nfield, J.R.: Fonctionnelles récursivement définissables et fonctionnelles récursives. Comptes Rendus de l’Académie des Sciences 245, 399–402 (1957)
Kushner, Boris A.: The constructive mathematics of A. A. Markov. Amer. Math. Monthly 113(6), 559–566 (2006)
Lacombe, D.: 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)
Markov, A.A.: On the continuity of constructive functions (russian). Uspekhi Mat. Nauk 9, 226–230 (1954)
Myhill, J., Shepherdson, J.C.: Effective operations on partial recursive functions. Math. Logic Quart. 1(4), 310–317 (1955)
Marian, B.: Pour-El. A comparison of five “computable” operators. Math. Logic Quart. 6(15–22), 325–340 (1960)
Rice, H.G.: Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74(2), 358–366 (1953)
Rogers, H. Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)
Schnorr, C.P.: Optimal enumerations and optimal gödel numberings. Math. Syst. Theory 8(2), 182–191 (1974)
Schröder, M.: Extended admissibility. Theor. Comput. Sci. 284(2), 519–538 (2002)
Selivanov, V.L.: Index sets in the hyperarithmetical hierarchy. Siber. Math. J. 25, 474–488 (1984)
Shapiro, N.: Degrees of computability. Trans. Amer. Math. Soc. 82, 281–299 (1956)
Spreen, D.: Representations versus numberings: On the relationship of two computability notions. Theor. Comput. Sci. 262(1), 473–499 (2001)
Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 2(42), 230–265 (1936)
Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)
Acknowledgments
This work was partially supported by Inria program “Chercheur invité”. C.R. was partially supported by a FONDECYT grant No. 1150222, a Universidad Andres Bello grant No. DI-782-15/R and a BASAL grant No. PFB-03 CMM-Universidad de Chile.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hoyrup, M., Rojas, C. On the Information Carried by Programs About the Objects they Compute. Theory Comput Syst 61, 1214–1236 (2017). https://doi.org/10.1007/s00224-016-9726-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-016-9726-9