On the information carried by programs about the objects they compute (Q1693999)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the information carried by programs about the objects they compute |
scientific article; zbMATH DE number 6833244
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the information carried by programs about the objects they compute |
scientific article; zbMATH DE number 6833244 |
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
