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_{p \mbox{ 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_{p \mbox{ halts}} 2^{-s|p|}`

Stay: Zeta function of a Turing machine (2005)

Stay: Zeta function of a Turing machine (2005)

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

Stay: Uncertainty principle

Stay: Uncertainty Principle

`\Delta \zeta * \Delta \n \ge 2^{-c_U}`