paper
active
paper:2021-10-18-prabros-1604-02603-pdf-6f9f31

Information, Processes and Games

BySamson Abramsky
arXiv 1604.02603
conservation of information flowBayesian orderbisimulation"Domain Theory is a static theory resting on dynamic intuitions."Hoare LogicHindley-Milner algorithmdynamic tautologyKripke SemanticsStructural Operational Semanticsinformation increase in computationQuantum Logic (Birkhoff–von Neumann)open systemsShannon Information TheoryQualitative-Quantitative Theory Classification Axis+2 more

TL;DR

Information dynamics — a free-standing, syntax-independent science of informatic processes — requires unifying static/dynamic and qualitative/quantitative theories of information, and the paper's load-bearing contribution is the programme of showing how this unification can be achieved using three families of formal machinery: Scott Domain Theory, Game Semantics, and Geometry of Interaction. Coecke and Martin's construction of the Bayesian order on classical n-states (probability simplices Δₙ) and quantum states (density operators Ωₙ on n-dimensional Hilbert spaces Hₙ) provides the key bridge between Shannon entropy and Domain Theory: Shannon entropy μ(x) = −Σxᵢ log xᵢ is a measurement on the domain (Δₙ, ⊑), and von Neumann entropy S(ρ) = −tr(ρ log ρ) is a measurement on (Ωₙ, ⊑), with both domains' lattices of irreducible elements recovering exactly the Birkhoff–von Neumann quantum logics via Theorem 4.7. On the dynamic side, the paper introduces the partial involutions model — a particle-traversal Geometry of Interaction construction in which all combinators (B, C, I, K, W) are realised as partial involutions on a countably infinite set Pos of positions, with functional application defined via feedback composition f•g = f₂₂ ∪ f₂₁;g;(f₁₁;g)*;f₁₂, yielding a Linear Combinatory Algebra that embeds into a Standard Combinatory Algebra and hence a universal model of computation (Theorems 6.3 and 6.1). Game Semantics interprets the copy-cat strategy as the canonical proof of A ⊸ A in Multiplicative Linear Logic, linking conservation of information flow directly to logical tautology. The paper argues that this implies logical principles should be understood not as static truths but as conservation laws governing information flow between interacting agents, and that a mature Information Dynamics will subsume both computational complexity and the philosophy of information under a single geometric-logical framework.

What to take away

  1. 1. Coecke and Martin prove that the Bayesian order makes (Δₙ, ⊑) a domain whose least element is the uniform distribution (1/n, …, 1/n) and whose maximal elements are the pure states {eᵢ}, and that Shannon entropy μ(x) = −Σxᵢ log xᵢ is a measurement on this domain (Theorem 4.2).
  2. 2. The same construction lifts to quantum states: (Ωₙ, ⊑) is a domain with least element I/n and maximal elements Σₙ (pure states), and von Neumann entropy S(ρ) = −tr(ρ log ρ) is a measurement on it (Theorem 4.5).
  3. 3. The lattices of Birkhoff and von Neumann arise as order-duals of irreducible elements: Ir(Δₙ)* ≅ P{1,…,n}\{∅} (classical logic) and Ir(Ωₙ)* ≅ Lₙ\{0} (quantum logic), recovering the distributive/non-distributive distinction from the domain structure alone (Theorem 4.7).
  4. 4. The partial involutions model — the paper's central Geometry of Interaction construction — realises all Linear Combinatory Algebra combinators (B, C, I, K, W, D, δ, F) as partial involutions on a countably infinite position set Pos, with function application defined by the feedback formula f•g = f₂₂ ∪ f₂₁;g;(f₁₁;g)*;f₁₂.
  5. 5. By Theorem 6.3, any Linear Combinatory Algebra yields a Standard Combinatory Algebra under the substitution a·ₛb ≡ a·!b, and by Theorem 6.1 the partial recursive functions are exactly those numeralwise representable in CL, establishing that the partial involutions model is computationally universal.
  6. 6. The copy-cat strategy — copying opponent moves between two game boards — is proved to be a winning strategy for A⊥ ⅋ A (linear tautology A ⊸ A), making it a dynamic analogue of the classical tautology A ∨ ¬A and grounding logical principles as conservation laws for information flow.
  7. 7. Domain Theory, originating with Dana Scott c. 1970, is classified as a static qualitative theory, while Process Algebra (Milner's CCS, 1980) is the paper's first example of a genuinely dynamic qualitative theory that makes temporality and event flow explicit; Dynamic Logic (Pratt, 1976) is classified as static despite its name because it captures only input-output relations.
  8. 8. The paper raises the open hypothesis that polynomial-time computation and other complexity classes might be characterisable in a machine-independent, geometrical, non-inductive way analogous to how Game Semantics characterises programming disciplines (purely functional, stateful, non-deterministic, concurrent, etc.) without referring back to Turing machines.
  9. 9. To replicate the Bayesian order construction, one defines the base case on Δ₂ by x ⊑ y ≡ (y₁ ≤ x₁ ≤ 1/2) ∨ (1/2 ≤ x₁ ≤ y₁), then extends inductively to Δₙ₊₁ via the Bayesian projections pᵢ(x) = (x₁,…,x̂ᵢ,…,xₙ₊₁)/(1−xᵢ) by requiring x ⊑ y iff ∀i, pᵢ(x) ⊑ pᵢ(y) whenever both are defined (Definition 4.1).
  10. 10. The equational theory of strong bisimulation on CCS process terms is not finitely axiomatisable (Moller, LICS 1990), but a finite axiomatisation is achievable with the auxiliary left-merge operator, illustrating the persistent non-canonicity problem — the 'next 700 syndrome' — that the paper identifies as the fundamental challenge for Information Dynamics.

Peer brief — for seminar discussion

Abramsky's survey, written for a Handbook of Philosophy of Information, proposes the programme of Information Dynamics: a free-standing mathematical science of informatic processes that integrates qualitative structure, quantitative measure, and explicit dynamics. Rather than reporting experimental results, it maps out partial exemplifications of this programme across six formal frameworks and argues that their convergence points toward a unified theory. The paper does, however, introduce one technically specific construction — the partial involutions model of Geometry of Interaction — as a concrete instantiation of universal computation from pure copying, and it is this that constitutes the paper's most original formal contribution. The load-bearing finding is a cluster of three interlocking results. First, Coecke and Martin's Bayesian order places a domain structure on probability simplices Δₙ and on quantum state spaces Ωₙ such that Shannon entropy and von Neumann entropy respectively become domain measurements (Theorems 4.2 and 4.5). Second, the lattices of Birkhoff and von Neumann — the classical distributive lattice P{1,…,n} and the non-distributive quantum lattice Lₙ of closed subspaces of an n-dimensional Hilbert space Hₙ — are recovered as order-duals of irreducible elements of these domains (Theorem 4.7), unifying logic, probability, and order theory in one construction. Third, in the partial involutions model, combinators B, C, I, K, W are realised as partial involutions on a countably infinite set Pos of positions, functional application is defined by a feedback formula involving relational composition and reflexive transitive closure, and Theorems 6.3 and 6.1 together deliver computational universality: the partial recursive functions are exactly those representable in the resulting Standard Combinatory Algebra. The paper argues this implies that logical principles — the tautologies of Linear Logic and beyond — should be understood not as static truths but as conservation laws governing information flow between interacting agents, with the copy-cat strategy serving as the paradigm case: it is simultaneously a winning strategy for A ⊸ A in Multiplicative Linear Logic and a proof that mere copying is computationally universal. An alternative approach the paper could have used for the dynamic component is traced monoidal category theory (Joyal, Street, and Verity 1996), which the paper itself acknowledges as the general axiomatic home for Geometry of Interaction constructions; working directly in that setting would have given more categorical generality at the cost of immediate geometric concreteness. A critical reader would push back primarily on scope and evidentiary status: the paper presents Information Dynamics as a nascent field defined largely by what it is not yet, and the specific formal results — Coecke–Martin's domain structure on Δₙ and Ωₙ, the partial involutions model — are cited from pre-existing or concurrent work rather than proved here in full. The survey thus risks conflating the programme with its partial exemplifications, leaving unanswered the central question of whether a single unified framework can simultaneously handle quantitative rate-of-flow questions, the non-canonicity problem in concurrency (the 'next 700 syndrome'), and complexity-theoretic characterisations. The prediction that polynomial-time complexity classes might admit a geometrical, machine-independent characterisation analogous to Game Semantics' characterisation of programming disciplines remains entirely conjectural, with no formal constraints given on what such a characterisation would require.

Methods (3)

Frameworks (5)

  • Bayesian order
    The partial order on classical probability distributions (Delta^n) that makes Shannon entropy a measurement on a domain.
  • Hoare Logic
    Compositional proof system for imperative programs using pre/post-conditions.
  • Kripke Semantics
    Possible-worlds semantics for modal logics using Kripke structures.
  • Quantum Logic (Birkhoff–von Neumann)
    Lattice of subspaces of Hilbert space as logic of quantum propositions.
  • Shannon Information Theory
    Classical quantitative theory of information; paper seeks to reconcile with qualitative domain-theoretic approaches.

Findings (9)

Claims (14)

Hypotheses (2)

Questions (5)

Related work— refs + corpus + external arXiv

Cited / in-corpus / arXiv badges show which signals surfaced each row. Multi-source rows weighted higher.

+29 more

Similar preprints — Semantic Scholar

Cross-corpus bridges (1)

same_concept_as · Nomic cosine

External markdown files that talk about the same concept as this entity.

  • alexander
    2021 10 18 Prabros. 1604.02603.pdf 6f9f31papers/extracted/2021-10-18_Prabros._1604.02603.pdf_6f9f31.md0.823