2026-07-22T06:50:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4933 2024-03-06T10:35:35Z ddc:004 open_access

On the Information Carried by Programs about the Objects They Compute Hoyrup, Mathieu Rojas, Cristóbal Markov-computable representation Kolmogorov complexity Ershov topology 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mathieu Hoyrup and Cristóbal Rojas 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.447 urn:nbn:de:0030-drops-49337 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.447 eng https://creativecommons.org/licenses/by/3.0/legalcode