Turing Zeta Functions
and
Uncertainty


Mike Stay
stay@google.com

(Work done with Cristian Calude at University of Auckland, New Zealand)

What is information?

  • Liebniz, 1686: The year before Newton's Principia
    • How to distinguish a world describable by science from one that isn't?
    • "Lawful behavior"
    • Data fitting
    • Law is a smaller description of the data

What's a description?

Turing Machines

000000111101101000000000
......^.................

Turing Machines

000000111101101000000000
......^.................

Universal Turing Machines

Universal Programming Language

Algorithmic Information Theory

Formal Axiomatic Systems

Chaitin's $\Omega$ (1974)

$$\Omega = \sum_{\small \mbox{$p$ halts}} 2^{-|p|}$$

Chaitin's $\Omega$ (1974)

Chaitin's $\Omega$ (1974)

Chaitin's $\Omega$ (1974)

Chaitin's $\Omega$ (1974)

Chaitin's Incompleteness Theorem

Chaitin's Incompleteness Theorem

Tadaki: Partial Randomness (2002)

$$\Omega_U(s) = \sum_{\small \mbox{$p$ halts}} 2^{-s|p|}$$

Stay: Zeta function of a Turing machine (2005)

Stay: Zeta function of a Turing machine (2005)

$$\zeta_T(s) = \sum_{\small \mbox{bin$(n)$ halts}} n^{-s}$$

Stay: Uncertainty principle

Stay: Uncertainty Principle

$\Delta \zeta \Delta n \ge 2^{-c_U}$