Top

Theory of Computing Systems

Published in:

09-12-2016

On the Information Carried by Programs About the Objects they Compute

Authors: Mathieu Hoyrup, Cristóbal Rojas

Published in: Theory of Computing Systems | Issue 4/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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).

previous article Characterisation of Limit Measures of Higher-Dimensional Cellular Automata

next article Multi-k-ic Depth Three Circuit Lower Bound

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

In its original form due to Kreisel-Lacombe-Shœnfield, this theorem is stated for functionals.

Č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, 1967MathSciNet

de Brecht, M.: Quasi-polish spaces. Ann. Pure Appl. Logic 164(3), 356–381 (2013)MathSciNetCrossRefMATH

Freivalds, R, Wiehagen, R.: Inductive inference with additional information. J. Inf. Process. Cybern. 15, 179–185 (1979)MathSciNetMATH

Friedberg, R.M.: Un contre-exemple relatif aux fonctionnelles récursives. Comptes Rendus de l’Académie des Sciences 247, 852–854 (1958)MATH

Grassin, J.: Index sets in Ershov’s hierarchy. J. Symb. Logic 39, 97–104, 3 (1974)MathSciNetCrossRefMATH

Grzegorczyk, A.: On the definitions of computable real continuous functions. Fundamenta Mathematicae 44, 61–71 (1957)MathSciNetMATH

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)MATH

10.

Kushner, Boris A.: The constructive mathematics of A. A. Markov. Amer. Math. Monthly 113(6), 559–566 (2006)MathSciNetCrossRefMATH

11.

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)MathSciNetMATH

12.

Markov, A.A.: On the continuity of constructive functions (russian). Uspekhi Mat. Nauk 9, 226–230 (1954)MathSciNetMATH

13.

Myhill, J., Shepherdson, J.C.: Effective operations on partial recursive functions. Math. Logic Quart. 1(4), 310–317 (1955)MathSciNetCrossRefMATH

14.

Marian, B.: Pour-El. A comparison of five “computable” operators. Math. Logic Quart. 6(15–22), 325–340 (1960)MATH

15.

Rice, H.G.: Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 74(2), 358–366 (1953)MathSciNetCrossRefMATH

16.

Rogers, H. Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)MATH

17.

Schnorr, C.P.: Optimal enumerations and optimal gödel numberings. Math. Syst. Theory 8(2), 182–191 (1974)CrossRefMATH

18.

Schröder, M.: Extended admissibility. Theor. Comput. Sci. 284(2), 519–538 (2002)MathSciNetCrossRefMATH

19.

Selivanov, V.L.: Index sets in the hyperarithmetical hierarchy. Siber. Math. J. 25, 474–488 (1984)MathSciNetCrossRefMATH

20.

Shapiro, N.: Degrees of computability. Trans. Amer. Math. Soc. 82, 281–299 (1956)MathSciNetCrossRefMATH

21.

Spreen, D.: Representations versus numberings: On the relationship of two computability notions. Theor. Comput. Sci. 262(1), 473–499 (2001)MathSciNetCrossRefMATH

22.

Turing, A.: On computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc. 2(42), 230–265 (1936)MathSciNetMATH

23.

Weihrauch, K.: Computable Analysis. Springer, Berlin (2000)CrossRefMATH

Title: On the Information Carried by Programs About the Objects they Compute
Authors: Mathieu Hoyrup
Cristóbal Rojas
Publication date: 09-12-2016
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 4/2017
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-016-9726-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2017

Welfare Maximization with Friends-of-Friends Network Externalities

Editorial: Special Issue on “Theoretical Aspects of Computer Science” (STACS 2015)

Layerwise Computability and Image Randomness

The Advice Complexity of a Class of Hard Online Problems

New Pairwise Spanners

Characterisation of Limit Measures of Higher-Dimensional Cellular Automata

Premium Partner