Computer Runtimes and the Length of Proofs

DOI10.1007/978-3-642-27654-5_17zbMath1353.03072arXiv1201.0825OpenAlexW1755070918MaRDI QIDQ2891314

Hector Zenil

Publication date: 15 June 2012

Published in: Computation, Physics and Beyond (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1201.0825

zbMATH Keywords

halting probabilityhalting problemautomatic theorem provingprogram-size complexityproof lengthbusy beaver problemsmall Turing machines

Mathematics Subject Classification ID

Related Items (2)

Shortening of Proof Length is Elusive for Theorem Provers ⋮ Life as thermodynamic evidence of algorithmic structure in natural environments

Uses Software

• Wolfram Demonstrations
• Waldmeister

Cites Work

• Unnamed Item
• Unnamed Item
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• Most programs stop quickly or never halt
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• A Theory of Program Size Formally Identical to Information Theory
• The AProS Project: Strategic Thinking & Computational Logic
• Computing a Glimpse of Randomness
• Computer Studies of Turing Machine Problems
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

This page was built for publication: Computer Runtimes and the Length of Proofs