theoretical

Basic idea

Mathematical foundations of computation: complexity classes, computability, descriptive measures (Kolmogorov complexity), and structural tools (space-filling curves) used by theoreticians and systems folks alike.

Key formulas

• Kolmogorov complexity: $K(x) = \min\{|p| : U(p) = x\}$
• Universal prior (Solomonoff): $M(x) = \sum_{p : U(p)=x*} 2^{-|p|}$
• Big-O: $f = O(g) \iff \exists c, n_0.\ f(n) \le c g(n)$ for $n \ge n_0$

Pages

• Hilbert Curve
• Hilbert curve scheduling
• Kolmogorov complexity
• Solomonoff's theory of inductive inference
• Z-order curve

Siblings

• ai
• compression
• computer algebra
• data structures
• distributed systems
• formal verification
• Operating Systems
• programming language theory
• search