Search

Abstract: In this paper we introduce the notion of ε-universal prefix-free Turing machine (ε is a computable real in ) and study its halting probability. The main result is the extension of the representability theorem for left-computable random reals to the case of ε-random reals: a real is left-computable ε-random iff it is the halting probability of an ε-universal prefix-free Turing machine. We also show that left-computable ε-random reals are provable ε-random in the Peano Arithmetic. The theory developed here parallels to a large extent the classical theory, but not completely. For example, random reals are Borel normal (in any base), but for , some ε-random reals do not contain even arbitrarily long runs of 0s. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to provide a probabilistic, but non-quantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random N-bit program has halted by a random time. We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer , we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than . We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that “long” runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time has effectively zero density. [Copyright &y& Elsevier]

Abstract: In this paper we prove Chaitin''s “heuristic principle,”the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself, for an appropriate measure of complexity. We show that the measure is invariant under the change of the Gödel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo–Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive. [Copyright &y& Elsevier]