1974/07/01 by Gregory J. Chaitin · 7 citations
Computer Science · Mathematics · #Computability, Logic, AI Algorithms #Benford’s Law and Fraud Detection #Evolutionary Algorithms and Applications
paper · pdf · doi:10.1145/321832.321839
openalex publication_date 1974/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15
An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time it takes the computer to perform these tasks. This is applied to measuring the difficulty of proving a given set of theorems, in terms of the number of bits of axioms that are assumed, and the size of the proofs needed to deduce the theorems from the axioms.