Information-theoretic incompleteness
type: Item
instance of: scholarly article
title: Information-theoretic incompleteness
zbMATH Open document ID: 0776.68065
DOI: 10.1016/0096-3003(92)90099-M
published in: Applied Mathematics and Computation
publication date: 1993-01-17T00:00:00Z
review text: In this interesting note the author continues his many investigations of the incompleteness of basic topological systems. Several fundamental incompleteness theorems in his book on algorithmic information theory [Algorithmic information theory (1987; Zbl 0655.68003)] are reformulated based upon an improved definition of the complexity of a formal axiomatic system. The value added comes from measuring the complexity of a formal system in terms of the program-size complexity of enumerating its infinite set of theorems rather than in terms of the program-size complexity of the finite strings of axioms. Included is an incompleteness theorem for diophantine equations.
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03F99
zbMATH DE Number: 96914
zbMATH Keywords: algorithmic entropy
zbMATH Keywords: randomness
zbMATH Keywords: complexity of a formal axiomatic system
zbMATH Keywords: incompleteness theorem for diophantine equations
author: Gregory J. Chaitin
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
cites work: Q4331759
cites work: Algorithmic entropy of sets
cites work: Q3995518
cites work: Algorithmic Information Theory
cites work: Gödel's theorem and information
cites work: Incompleteness theorems for random reals
cites work: Information-theoretic computation complexity
cites work: Information-Theoretic Limitations of Formal Systems
cites work: RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Q3135847
cites work: Proof of Recursive Unsolvability of Hilbert's Tenth Problem
cites work: Register machine proof of the theorem on exponential diophantine representation of enumerable sets
cites work: Q4003732
full work available at URL: 0096-3003(92)90099-m
OpenAlex ID: W1969403659
description: scientific article; zbMATH DE number 96914