Incompleteness theorems for random reals
type: Item
instance of: scholarly article
title: Incompleteness theorems for random reals
zbMATH Open document ID: 0649.03046
DOI: 10.1016/0196-8858(87)90010-8
published in: Advances in Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Using approaches from thermodynamics and information theory, the author shows several results in diophantine theory with stochastic proofs. Indeed, these ideas can be used to construct an exponential diophantine equation whose solutions are, in a very definite sense, random; e.g., in the sense of Martin-Löf. Many limitative theorems of logic follow from such results; e.g., modified incompleteness theorems of Gödel type. In the process, the author shows the equivalence of several different senses of random: (1) Martin-Löf; (2) Chaitin and (3) Solovay. The author seems to believe that God plays dice even with (pure) mathematics.
Mathematics Subject Classification ID: 03F99
Mathematics Subject Classification ID: 94A17
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03F35
zbMATH DE Number: 4059395
zbMATH Keywords: randomness
zbMATH Keywords: random reals
zbMATH Keywords: constructive mathematics
zbMATH Keywords: diophantine theory
zbMATH Keywords: stochastic proofs
zbMATH Keywords: exponential diophantine equation
zbMATH Keywords: modified incompleteness theorems of Gödel type
author: Gregory J. Chaitin
reviewed by: Albert A. Mullin
MaRDI profile type: Publication
full work available at URL: 0196-8858(87)90010-8
OpenAlex ID: W2001279301
cites work: Information-theoretic computation complexity
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Gödel's theorem and information
cites work: The decision problem for exponential diophantine equations
cites work: Q4830809
cites work: Q5538132
cites work: Q5813263
cites work: Register machine proof of the theorem on exponential diophantine representation of enumerable sets
cites work: The definition of random sequences
cites work: Q5801644
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
description: scientific article; zbMATH DE number 4059395