Universality probability is an abstruse

probability measure In mathematics, a probability measure is a real-valued function defined on a set of events in a σ-algebra that satisfies Measure (mathematics), measure properties such as ''countable additivity''. The difference between a probability measure an ...

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

that concerns

universal Turing machine In computer science, a universal Turing machine (UTM) is a Turing machine capable of computing any computable sequence, as described by Alan Turing in his seminal paper "On Computable Numbers, with an Application to the Entscheidungsproblem". Co ...

Background

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

is a basic model of

computation A computation is any type of arithmetic or non-arithmetic calculation that is well-defined. Common examples of computation are mathematical equation solving and the execution of computer algorithms. Mechanical or electronic devices (or, hist ...

. Some

s might be specific to doing particular calculations. For example, a Turing machine might take input which comprises two numbers and then produce output which is the product of their

multiplication Multiplication is one of the four elementary mathematical operations of arithmetic, with the other ones being addition, subtraction, and division (mathematics), division. The result of a multiplication operation is called a ''Product (mathem ...

. Another Turing machine might take input which is a list of numbers and then give output which is those numbers sorted in order. A

which has the ability to simulate any other Turing machine is called universal - in other words, a Turing machine (TM) is said to be a

(or UTM) if, given any other TM, there is a some input (or "header") such that the first TM given that input "header" will forever after behave like the second TM. An interesting

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

philosophical Philosophy ('love of wisdom' in Ancient Greek) is a systematic study of general and fundamental questions concerning topics like existence, reason, knowledge, Value (ethics and social sciences), value, mind, and language. It is a rational an ...

question then arises. If a

is given random input (for suitable definition of

random In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. ...

), how probable is it that it remains universal forever?

Definition

Given a prefix-free

, the universality probability of it is the

probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...

that it remains universal even when every input of it (as a binary string) is prefixed by a random binary string. More formally, it is the

of reals (infinite binary sequences) which have the property that every initial segment of them preserves the universality of the given Turing machine. This notion was introduced by the computer scientist

Chris Wallace Christopher Wallace (born October 12, 1947) is an American broadcast journalist. He is known for his tough and wide-ranging interviews, for which he is often compared to his father, ''60 Minutes'' journalist Mike Wallace. Over his 60-year care ...

and was first explicitly discussed in print in an article by Dowe (and a subsequent article). However, relevant discussions also appear in an earlier article by Wallace and Dowe.

Universality probabilities of prefix-free UTMs are non-zero

Although the universality probability of a UTM (UTM) was originally suspected to be zero, relatively simple proofs exist that the

supremum In mathematics, the infimum (abbreviated inf; : infima) of a subset S of a partially ordered set P is the greatest element in P that is less than or equal to each element of S, if such an element exists. If the infimum of S exists, it is unique, ...

of the set of universality probabilities is equal to 1, such as a proof based on

random walk In mathematics, a random walk, sometimes known as a drunkard's walk, is a stochastic process that describes a path that consists of a succession of random steps on some Space (mathematics), mathematical space. An elementary example of a rand ...

s and a proof in Barmpalias and Dowe (2012). Once one has one prefix-free UTM with a non-zero universality probability, it immediately follows that all prefix-free UTMs have non-zero universality probability. Further, because the

of the set of universality probabilities is 1 and because the set is

dense Density (volumetric mass density or specific mass) is the ratio of a substance's mass to its volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' (or ''d'') can also be use ...

in the interval

, 1 The comma is a punctuation mark that appears in several variants in different languages. Some typefaces render it as a small line, slightly curved or straight, but inclined from the vertical; others give it the appearance of a miniature fille ...

suitable constructions of UTMs (e.g., if ''U'' is a UTM, define a UTM ''U''₂ by ''U''₂(0''s'') halts for all strings ''s'', U₂(1''s'') = ''U''(''s'') for all s) gives that the set of universality probabilities is

in the open interval (0, 1).

Characterization and randomness of universality probability

Universality probability was thoroughly studied and characterized by Barmpalias and Dowe in 2012. Seen as

real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

s, these probabilities were completely characterized in terms of notions in

computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

and algorithmic information theory. It was shown that when the underlying machine is universal, these numbers are highly algorithmically random. More specifically, it is Martin-Löf random relative to the third iteration of the

halting problem In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...

. In other words, they are random relative to null sets that can be defined with four quantifiers in

Peano arithmetic In mathematical logic, the Peano axioms (, ), also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nea ...

. Vice versa, given such a highly random number (with appropriate approximation properties) there is a Turing machine with universality probability that number.

Relation with Chaitin's constant

Universality probabilities are very related to the Chaitin constant, which is the halting probability of a universal prefix-free machine. In a sense, they are complementary to the halting probabilities of universal machines relative to the third iteration of the

. In particular, the universality probability can be seen as the non-halting probability of a machine with oracle the third iteration of the halting problem. Vice versa, the non-halting probability of any prefix-free machine with this highly non-computable oracle is the universality probability of some prefix-free machine.

Probabilities of machines as examples of highly random numbers

Universality probability provides a concrete and somewhat natural example of a highly random number (in the sense of algorithmic information theory). In the same sense, Chaitin's constant provides a concrete example of a random number (but for a much weaker notion of algorithmic randomness).

References

External links

* * (an
here
. * Dowe, D. L. (2011),
MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness"
Handbook of the Philosophy of Science - (HPS Volume 7) Philosophy of Statistics, P.S. Bandyopadhyay and M.R. Forster (eds.), Elsevier, pp901-982. * Wallace, C. S. & Dowe, D. L. 1999
Minimum message length and Kolmogorov complexity
'. Computer J. 42, 270–283. * Hernandez-Orallo, J. & Dowe, D. L. (2013), "On Potential Cognitive Abilities in the Machine Kingdom"
Minds and Machines
Vol. 23, Issue 2
pp179-210
(an
here
* Barmpalias, G. (June 2015)
slides from talk
entitle
``Randomness, probabilities and machines
at th
Tenth International Conference on Computability, Complexity and RandomnessCCR 2015
conference, 22–26 June 2015, Heidelberg, Germany. * Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu.
Computing a Glimpse of Randomness
''