plurigrid/asi / ies/music-topos/.codex/skills/kolmogorov-compression
kolmogorov-compression
VerifiedKolmogorov complexity as the ultimate intelligence measure. Shortest program that outputs data.
| File | Kind | Size |
|---|---|---|
| SKILL.md | skill md | 3.3 KB |
SKILL.md
View on GitHub---
name: kolmogorov-compression
description: "Kolmogorov complexity as the ultimate intelligence measure. Shortest program that outputs data."
trit: -1
polarity: MINUS
source: "Solomonoff 1964, Kolmogorov 1965, KoLMogorov-Test 2025"
technologies: [Python, MLX, Lean4]
---
# Kolmogorov Compression Skill
> *"The Kolmogorov complexity of x is the length of the shortest program that outputs x."*
> — Andrey Kolmogorov
## Overview
**Kolmogorov complexity** K(x) = length of shortest program P where P() = x.
**Intelligence = Compression**: Finding short descriptions of data.
## Core Concept
```latex
K(x) = min { |P| : U(P) = x }
Where:
U = Universal Turing Machine
P = program (binary string)
|P| = length of P
Properties:
- K(x) ≤ |x| + O(1) (trivial: print x)
- K(x) is uncomputable (halting problem)
- K(x|y) = conditional complexity given y
```
## The KoLMogorov-Test (2025)
Use LLMs to approximate Kolmogorov complexity:
```python
class KolmogorovCompressor:
"""
Approximate K(x) via code generation.
"""
def __init__(self, llm):
self.llm = llm
def compress(self, data: str) -> str:
"""Generate shortest program that outputs data."""
prompt = f"""
Generate the shortest Python program that prints exactly:
{data[:100]}...
The program must output EXACTLY this string.
Make it as SHORT as possible.
"""
program = self.llm.generate(prompt)
return self.extract_code(program)
def complexity(self, data: str) -> int:
"""Estimate K(data)."""
program = self.compress(data)
return len(program.encode())
def intelligence_score(self, model, data: str) -> float:
"""
KoLMogorov-Test score.
Higher = better compression = more intelligent.
"""
program = model.compress(data)
ratio = len(program) / len(data)
return 1 - ratio # Higher = better
```
## Integration with Sutskever's Thesis
```
Sutskever's Insight:
Compression = Prediction = Understanding = Intelligence
If you can compress x to K(x) bits:
- You understand x's structure
- You can predict x from the program
- You have a model of x
```
## GF(3) Triads
```
kolmogorov-compression (-1) ⊗ cognitive-superposition (0) ⊗ godel-machine (+1) = 0 ✓
kolmogorov-compression (-1) ⊗ turing-chemputer (0) ⊗ dna-origami (+1) = 0 ✓
kolmogorov-compression (-1) ⊗ solomonoff-induction (0) ⊗ information-capacity (+1) = 0 ✓
```
As **Validator (-1)**, kolmogorov-compression:
- Measures true complexity (validates claims)
- Filters noise from signal
- Provides lower bound on description
## Connection to Theorem Proving
```
For proof P of theorem T:
K(T) ≈ min |P| over all proofs P
Short proofs = Simple theorems
Long proofs = Complex theorems (but still provable)
Gödel: Some true statements have K(T) = ∞ (unprovable)
```
## References
1. Kolmogorov, A.N. (1965). "Three approaches to the quantitative definition of information."
2. Solomonoff, R.J. (1964). "A formal theory of inductive inference."
3. Li, M. & Vitányi, P. (2008). *An Introduction to Kolmogorov Complexity and Its Applications*.
4. Fan et al. (2025). "The KoLMogorov-Test: Compression-Based Intelligence Evaluation."
Related skills
| Skill | Stars | Updated | Works with | Status | Install |
|---|---|---|---|---|---|
| slack-gif-creatoranthropics/skillsKnowledge and utilities for creating animated GIFs optimized for Slack. Provides constraints, validation tools, and animation concepts. Use when users request animated GIFs for Slack like "make me a GIF of X doing Y for Slack." | Stars: 198k | Updated | Claude CodeCodex | Verified | Install |
| ponytailDietrichGebert/ponytailLazy senior dev mode for any coding task: the smallest change that fully solves it, and a reply a busy human understands in one read. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |
| ponytail-debtDietrichGebert/ponytailHarvest every shortcut: comment into one debt ledger, so deferrals get tracked instead of forgotten. One-shot report. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |
| ponytail-debtDietrichGebert/ponytailList every `shortcut:` comment (and older `ponytail:` ones) as a debt ledger. One-shot report, changes nothing. Use for "ponytail debt", "what did ponytail defer", "list the shortcuts", /ponytail-debt. | Stars: 194k | Updated | Claude CodeCodex | Verified | Install |