# On the information carried by programs about the objects they compute

arXiv: https://arxiv.org/abs/1409.6977 · HTML: https://mlsanity.com/paper/1409.6977/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Sep 2014.

## Built on by (most cited first, 1 of 1)

- [On the Complexity of Computing G"odel Numbers](https://mlsanity.com/paper/2302.04213/) (2023)

## Abstract (arXiv)

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.