Computer Runtimes and the Length of Proofs
type: Item
instance of: scholarly article
title: Computer Runtimes and the Length of Proofs
zbMATH Open document ID: 1353.03072
DOI: 10.1007/978-3-642-27654-5_17
author: Hector Zenil
published in: Computation, Physics and Beyond
publication date: 2012-06-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/1201.0825
Mathematics Subject Classification ID: 03F20
Mathematics Subject Classification ID: 03D10
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68T15
zbMATH DE Number: 6046453
zbMATH Keywords: halting problem
zbMATH Keywords: halting probability
zbMATH Keywords: proof length
zbMATH Keywords: automatic theorem proving
zbMATH Keywords: busy beaver problem
zbMATH Keywords: program-size complexity
zbMATH Keywords: small Turing machines
describes a project that uses: Wolfram Demonstrations
describes a project that uses: Waldmeister
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W1755070918
arXiv ID: 1201.0825
cites work: The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
cites work: Computing a Glimpse of Randomness
cites work: Most programs stop quickly or never halt
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
cites work: The AProS Project: Strategic Thinking & Computational Logic
cites work: Computer Studies of Turing Machine Problems
cites work: Q4809080
cites work: Q3150942
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
description: scientific article