The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Information distance
Abstract
While Kolmogorov (1965) complexity is the accepted absolute measure of information content in an individual finite object, a similarly absolute notion is needed for the information distance between two individual objects, for example, two pictures. We give several natural definitions of a universal information metric, based on length of shortest programs for either ordinary computations or reversible (dissipationless) computations. It turns out that these definitions are equivalent up to an additive logarithmic term. We show that the information distance is a universal cognitive similarity distance. We investigate the maximal correlation of the shortest programs involved, the maximal uncorrelation of programs (a generalization of the Slepian-Wolf theorem of classical information theory), and the density properties of the discrete metric spaces induced by the information distances. A related distance measures the amount of nonreversibility of a computation. Using the physical theory of reversible computation, we give an appropriate (universal, antisymmetric, and transitive) measure of the thermodynamic work required to transform one object in another object by the most efficient process. Information distance between individual objects is needed in pattern recognition where one wants to express effective notions of "pattern similarity" or "cognitive similarity" between individual objects and in thermodynamics of computation where one wants to analyze the energy dissipation of a computation from a particular input to a particular output.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Irreversibility and heat generation in the computing process
Landauer, R. (1961) · IBM Journal of Research and Development · doi:10.1147/rd.53.0183 · Cited by 4,980
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Self-citationIrreversibility and heat generation in the computing process
Landauer, R. (2000) · IBM Journal of Research and Development · doi:10.1147/rd.441.0261 · Cited by 2,585
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
Self-citationFredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896
An Introduction to Kolmogorov Complexity and Its Applications
Li, M., & Vitányi, P. (1997) · Springer eBooks · doi:10.1007/978-1-4757-2606-0 · Cited by 1,775
Self-citationFeynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
A Theory of Program Size Formally Identical to Information Theory
Chaitin, G. J. (1975) · Journal of the ACM · doi:10.1145/321892.321894 · Cited by 849
Zvonkin, A. K., & Levin, L. A. (1970) · Russian Mathematical Surveys · doi:10.1070/rm1970v025n06abeh001269 · Cited by 665
Time/Space Trade-Offs for Reversible Computation
Bennett, C. H. (1989) · SIAM Journal on Computing · doi:10.1137/0218053 · Cited by 405
Self-citationAlgorithmic randomness and physical entropy
Zurek, W. H. (1989) · Physical Review A · doi:10.1103/physreva.40.4731 · Cited by 364
Self-citationThermodynamic cost of computation, algorithmic complexity and the information metric
Zurek, W. H. (1989) · Nature · doi:10.1038/341119a0 · Cited by 279
Self-citationMinimal Energy Dissipation in Logic
Keyes, R. W., & Landauer, R. (1970) · IBM Journal of Research and Development · doi:10.1147/rd.142.0152 · Cited by 265
Classical and quantum limitations on energy consumption in computation
Likharev, K. K. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857733 · Cited by 141
Benioff, P. A. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857725 · Cited by 113
Uncertainty principle and minimal energy dissipation in the computer
Landauer, R. W. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857731 · Cited by 100
On the Nearest Neighbour Interchange Distance Between Evolutionary Trees
Li, M., Tromp, J., & Zhang, L. (1996) · Journal of Theoretical Biology · doi:10.1006/jtbi.1996.0188 · Cited by 99
Self-citationA Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Levine, R. Y., & Sherman, A. T. (1990) · SIAM Journal on Computing · doi:10.1137/0219046 · Cited by 71
Quantum Mechanical Hamiltonian Models of Computersa
Benioff, P. A. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12450.x · Cited by 49
Comment on ‘‘Quantitative limits on the ability of a Maxwell demon to extract work from heat’’
Caves, C. M., Unruh, W. G., & Zurek, W. H. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.1387 · Cited by 18
Self-citation
Cited by
The Google Similarity Distance
Cilibrasi, R. L., & Vitanyi, P. M. B. (2007) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2007.48 · Cited by 1,760
Self-citationCilibrasi, R., & Vitanyi, P. M. B. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.844059 · Cited by 1,188
Self-citationLi, M., Chen, X., Li, X., Ma, B., & Vitanyi, P. M. B. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.838101 · Cited by 1,062
Self-citationSimplicity: a unifying principle in cognitive science?
Chater, N., & Vitányi, P. (2003) · Trends in Cognitive Sciences · doi:10.1016/s1364-6613(02)00005-0 · Cited by 494
Integrated information theory of consciousness: an updated account.
(2012) · PubMed · doi:10.4449/aib.v149i5.1388 · Cited by 370
Metadata
- Authors
- Bennett, C. H., Gacs, P., Li, M., Vitanyi, P. M. B., & Zurek, W. H.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1998-07
- Volume
- 44
- Issue
- 4
- Pages
- 1407-1423
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2295278941
- Cited by
- 506
- References
- 20
- FWCI
- 4.52
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.