Incompleteness theorems for random reals
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.
- A Theory of Program Size Formally Identical to Information Theory
- Gödel's theorem and information
- scientific article; zbMATH DE number 2123258 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3062467 (Why is no real title available?)
- scientific article; zbMATH DE number 3074175 (Why is no real title available?)
- Information-theoretic computation complexity
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Register machine proof of the theorem on exponential diophantine representation of enumerable sets
- The decision problem for exponential diophantine equations
- The definition of random sequences
- An improved zero-one law for algorithmically random sequences
- Computability and randomness of Nash equilibrium in infinite games
- The Arnol'd cat: Failure of the correspondence principle
- On independent random oracles
- Information-theoretic incompleteness
- \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness
- Computational depth and reducibility
- Efficient exact computation of iterated maps
- Randomness and reducibility
- The dimensions of individual strings and sequences
- The Kolmogorov complexity of random reals
- No random reals in countable support iterations
- Feasible reductions to Kolmogorov-Loveland stochastic sequences
- Prefix-free quantum Kolmogorov complexity
- Things that can be made into themselves
- On the computational power of random strings
- Is complexity a source of incompleteness?
- The axiomatic power of Kolmogorov complexity
- Reducibilities relating to Schnorr randomness
- Closed left-r.e. sets
- On the Reals Which Cannot Be Random
- Closed left-r.e. sets
- Increasing the gap between descriptional complexity and algorithmic probability
- Calibrating Randomness
- On initial segment complexity and degrees of randomness
- scientific article; zbMATH DE number 3943806 (Why is no real title available?)
- Fixed point theorems on partial randomness
- scientific article; zbMATH DE number 558650 (Why is no real title available?)
- RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
- Computational depth and reducibility
- Solovay functions and their applications in algorithmic randomness
- Selva Selvaggia
- QUANTUM ALGORITHMS FOR GENERATING RANDOM SEQUENCES OF INTEGERS
- An incomplete set of shortest descriptions
- Random reals and possibly infinite computations Part I: Randomness in ∅′
- Quantum algorithmic randomness
- Oscillation in the initial segment complexity of random reals
- Regainingly approximable numbers and sets
- Computing halting probabilities from other halting probabilities
- Algorithmic randomness in continuous-time Markov chains
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- A Suppes predicate for general relativity and set-theoretically generic spacetimes
This page was built for publication: Incompleteness theorems for random reals
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105595)
