---
title: "Logical Basis for Information Theory and Probability Theory"
authors:
  - "A. N. Kolmogorov"
year: 1968
venue: "IEEE Transactions on Information Theory"
arxiv: null
doi: "10.1109/TIT.1968.1054210"
source: "https://doi.org/10.1109/TIT.1968.1054210"
topics:
  - algorithmic-information
  - kolmogorov
  - probability
seed_rank: 606
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "Three Approaches to the Quantitative Definition of Information"
    url: "https://cqi.inf.usi.ch/qic/Kolmogorov_Complexity_1965.pdf"
    year: 1965
    arxiv: null
    doi: null
  - title: "A Mathematical Theory of Communication"
    url: "https://doi.org/10.1002/j.1538-7305.1948.tb01338.x"
    year: 1948
    arxiv: null
    doi: "10.1002/j.1538-7305.1948.tb01338.x"
see:
  - "604-three-approaches-to-the-quantitative-definition-of-informati"
  - "553-a-mathematical-theory-of-communication"
---

# Logical Basis for Information Theory and Probability Theory

## One-sentence takeaway

Kolmogorov retells algorithmic complexity for an IEEE information-theory audience and argues it supplies the missing logical foundation that Shannon entropy, being distributional, cannot give for individual objects.

## Why it matters here

This is the English carrier that put Kolmogorov complexity in front of engineers: the paper to hand someone who already knows Shannon and needs the individual-sequence story behind Broadside's compression-as-learning / AIT cards.

## Key ideas

- Shannon information is a property of a *measure*; algorithmic information is a property of a *string*.
- Universal machines make K(x) canonical up to O(1), so the definition is not programming-language-relative in any essential way.
- Complexity yields a definition of a random infinite sequence (incompressibility of prefixes) that can sit beside measure-theoretic almost-sure statements.
- The note is expository-plus-research: it advertises the 1965 *PPI* paper and the program of relating complexity to probability.

## Caveats

## Links

- DOI: [10.1109/TIT.1968.1054210](https://doi.org/10.1109/TIT.1968.1054210)