On the information carried by programs about the objects they compute

Mathieu Hoyrup, Cristóbal Rojas

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publication32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
EditorsErnst W. Mayr, Nicolas Ollinger
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages447-459
Number of pages13
ISBN (Electronic)9783939897781
DOIs
Publication statusPublished - 1 Feb 2015
Event32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Germany
Duration: 4 Mar 20157 Mar 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume30
ISSN (Print)1868-8969

Other

Other32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
Country/TerritoryGermany
CityGarching
Period4/03/157/03/15

Keywords

  • Ershov topology
  • Kolmogorov complexity
  • Markov-computable
  • Representation

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'On the information carried by programs about the objects they compute'. Together they form a unique fingerprint.

Cite this