Search

The Halting Problem, the most (in)famous undecidable problem, has important applications in theoretical and applied computer science and beyond, hence the interest in its approximate solutions. Experimental results reported on various models of computation suggest that halting programs are not uniformly distributed – running times play an important role. A reason is that a program which eventually stops but does not halt “quickly”, stops at a time which is algorithmically compressible. In this paper we work with running times to define a class of computable probability distributions on the set of halting programs in order to construct an anytime algorithm for the Halting problem with a probabilistic evaluation of the error of the decision. [ABSTRACT FROM AUTHOR]

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 main topics of the present work are universal machines for plain and prefix-free description complexity and their domains. It is characterised when an r.e. set is the domain of a universal plain machine in terms of the description complexity of the spectrum function mapping each non-negative integer to the number of all strings of length in ; furthermore, a characterisation of the same style is given for supersets of domains of universal plain machines. Similarly the prefix-free sets which are domains or supersets of domains of universal prefix-free machines are characterised. Furthermore, it is shown that the halting probability of an r.e. prefix-free set containing the domain of a universal prefix-free machine is Martin-Löf random, while may not be the domain of any universal prefix-free machine itself. Based on these investigations, the question whether every domain of a universal plain machine is the superset of the domain of some universal prefix-free machine is discussed. A negative answer to this question had been presented at CiE 2010 by Mikhail Andreev, Ilya Razenshteyn and Alexander Shen, while this paper was under review. [Copyright &y& Elsevier]

Abstract: Universality, provability and simplicity are key notions in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, Peano arithmetic or Zermelo–Fraenkel set theory. In all cases some, but not all, machines are simple. [ABSTRACT FROM AUTHOR]

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]

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called Deutsch's problem. Consider a Boolean function f: {0,1} → {0,1} and suppose that we have a (classical) black box to compute it. The problem asks whether f is constant [that is, f(0) = f(1)] or balanced [f(0) ≠ f(1)]. Classically, to solve the problem seems to require the computation of f(0) and f(1), and then the comparison of results. Is it possible to solve the problem with only one query on f? In a famous paper published in 1985, Deutsch posed the problem and obtained a "quantum" partial affirmative answer. In 1998, a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello and Mosca. Here we will show that the quantum solution can be de-quantized to a deterministic simpler solution which is as efficient as the quantum one. The use of "superposition," a key ingredient of quantum algorithm, is — in this specific case — classically available. [ABSTRACT FROM AUTHOR]

How likely is that a randomly given (non-) deterministic finite automaton recognizes no word? A quick reflection seems to indicate that not too many finite automata accept no word; but, can this intuition be confirmed? In this paper we offer a statistical approach which allows us to conclude that for automata, with a large enough number of states, the probability that a given (non-) deterministic finite automaton recognizes no word is close to zero. More precisely, we will show, with a high degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for both deterministic and non-deterministic finite automata: a) the probability that an automaton recognizes no word tends to zero when the number of states and the number of letters in the alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the number of letters of the alphabet of the automaton tends to infinity, the probability is strictly positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and statistical analysis. The present analysis shows that for all practical purposes the fraction of automata recognizing no words tends to zero when the number of states and the number of letters in the alphabet grow indefinitely. From a theoretical point of view, the result can motivate the search for "certitude" that is, a proof of the fact established here in probabilistic terms. In the last section we critically discuss the result and the method used in this paper. [ABSTRACT FROM AUTHOR]

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]

In this note we present two natural algorithms—one for sorting, and another for searching a sorted list of items. Both algorithms work in O(√ of N) time, N being the size of the list. A combination of these algorithms can search an unsorted list in O(√ of N) time, an impossibility for classical algorithms. The same complexity is achieved by Grover''s quantum search algorithm; in contrast to Grover''s algorithm which is probabilistic, our method is guaranteed correct. Two applications will conclude this note. [Copyright &y& Elsevier]

According to the Algorithmic Coding Theorem, minimal programs of any universal machine are prefix-codes asymptotically optimal (i.e. optimal up to at most an additive, unknown constant) with respect to the machine algorithmic probabilities. A stronger version of this result will be proven for a class of machines, not necessarily universal, and any semi-distribution. Furthermore, minimal programs with respect to universal machines will be shown to be almost optimal (i.e. optimal up to an additive constant less than or equal to 2) for any semi-computable semi-distribution. Finally, a complete characterization of all machines satisfying the Algorithmic Coding Theorem is given. [ABSTRACT FROM AUTHOR]