Contents

• Contents
• Introduction to Describable Universes
  • Outline of Main Results
• Preliminaries
  • Notation
  • Turing Machines: Monotone TMs (MTMs), General TMs (GTMs), Enumerable Output Machines (EOMs)
  • Infinite Computations, Convergence, Formal Describability
  • Formally Describable Functions
  • Weak Decidability and Convergence Problem
• Complexity of Constructive Descriptions
  • Generalized Kolmogorov Complexity for EOMs and GTMs
  • Expressiveness of EOMs and GTMs
• Measures and Probability Distributions
  • Dominant and Universal (Semi)Measures
  • Universal Cumulatively Enumerable Measure (CEM)
  • Approximable and Cumulatively Enumerable Distributions
  • TM-Induced Distributions and Convergence Probability
  • Universal TM-Induced Measures
  • Universal CEM vs EOM with Random Input
• Probability vs Descriptive Complexity
  • Theorems for EOMs and GTMs
  • Tighter Bounds?
  • Between EOMs and GTMs?
• Temporal Complexity
  • Fast Computation of Finite and Infinite Strings
  • FAST: The Most Efficient Way of Computing Everything
  • Speed-Based Characterization of the Describable
  • Enumerable Priors vs FAST
  • Speed Prior S and Algorithm GUESS
  • Speed Prior-Based Inductive Inference
  • Practical Applications of Algorithm GUESS
• Consequences for Physics
  • Plausibility of Recursive Priors
  • Plausibility of Cumulatively Enumerable Priors
  • Plausibility of Approximable Priors
  • Plausibility of Speed Prior S
  • S-Based Predictions
  • Short Algorithm Detectable?
  • Relation to Previous Work on All Possible Universes
• Concluding Remarks
• Bibliography

Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI