Information Kolmogorov Complexity Rs Kolmogorov Cert

The certificate

Kolmogorov complexity measures the length of the shortest program that produces a given piece of data. A random string of length n has complexity close to n, because no shorter description captures its patternless content. Recognition Science proposes an analogue: a recognition cost that grows as the logarithm of the data length in a particular base, the golden ratio phi, scaled by a constant factor of about 8.47.

The declaration KolmogorovCert is a formal structure, a named bundle of three properties. It states that the cost function vanishes when the two inputs are equal, that the cost is never negative for positive inputs, and that a certain threshold value, phi minus 3/2, is positive. Each property is proved in the machine-checked library of formal theorems. The certificate is inhabited, meaning the three properties are consistent and can be instantiated together.

The gap is deliberate and documented. The cost function in the certificate is defined as J(m/e), where J is a fixed function and m and e are real numbers, but nothing in the definition ties m or e to any particular notion of data, program, or description length. The certificate proves facts about the abstract function, not about Kolmogorov complexity itself. The research note records where the idea was meant to go, not a result that has arrived.

What the certificate does establish is a small, clean mathematical object: a cost function with three verified properties, packaged under a name that signals an intended application. What it does not establish is a theory of Kolmogorov complexity in the Recognition Science framework. The bridge from the abstract cost function to a concrete definition of data length remains open, and the certificate itself says so.

structure KolmogorovCert where
  cost_at_eq : ∀ r : ℝ, r ≠ 0 → domainCost r r = 0
  cost_nonneg : ∀ m e : ℝ, 0 < m → 0 < e → 0 ≤ domainCost m e
  threshold_pos : 0 < canonicalThreshold

theorem domainCost_at_eq (r : ℝ) (h : r ≠ 0) : domainCost r r = 0 := by
  unfold domainCost; rw [div_self h]; exact Jcost_unit0

theorem domainCost_nonneg (m e : ℝ) (hm : 0 < m) (he : 0 < e) : 0 ≤ domainCost m e := by
  unfold domainCost; exact Jcost_nonneg (div_pos hm he)

theorem canonicalThreshold_pos : 0 < canonicalThreshold := by
  unfold canonicalThreshold; linarith [phi_gt_onePointFive]

theorem cert_inhabited : Nonempty KolmogorovCert := ⟨cert⟩

What this page does not claim

A theory of Kolmogorov complexity in the Recognition Science framework. A definition of m and e in terms of data, programs, or description length. A proof that the cost function behaves like standard Kolmogorov complexity for any actual data.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Information/Kolmogorov_Complexity_RS.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: