On the information carried by programs about the objects they compute (Q1693999)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the information carried by programs about the objects they compute |
scientific article |
Statements
On the information carried by programs about the objects they compute (English)
0 references
1 February 2018
0 references
The paper asks and answers the following question: Is it possible to characterise the additional useful information contained in a program computing an object as compared with the object itself? The authors prove that bounding the Kolmogorov complexity of the object is the only additional useful information.
0 references
Markov-computable
0 references
Kolmogorov complexity
0 references
Ershov topology
0 references
