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 probability space that satisfies measure properties such as ''countable additivity''. The difference between a probability measure and the more gener ...

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

that concerns

universal Turing machine In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simu ...

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 Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm). Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...

. 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 (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...

. 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 Universal is the adjective for universe. Universal may also refer to: Companies * NBCUniversal, a media and entertainment company ** Universal Animation Studios, an American Animation studio, and a subsidiary of NBCUniversal ** Universal TV, a t ...

- 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 an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

philosophical Philosophy (from , ) is the systematized study of general and fundamental questions, such as those about existence, reason, knowledge, values, mind, and language. Such questions are often posed as problems to be studied or resolved. Some ...

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 pattern or predictability in events. A random sequence of events, symbols or steps often has no :wikt:order, order and does not follow an intelligible pattern or combination. Ind ...

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

Definition

Given a prefix-free

, the universality probability of it is the

probability Probability is the branch of mathematics concerning numerical descriptions of how likely an Event (probability theory), event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and ...

that it remains

even when every input of it (as a

binary string In computer programming, a string is traditionally a sequence of characters, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). ...

) 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 50-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; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

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

random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

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 substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...

in the interval

, 1 The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline (t ...

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 distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...

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 e ...

and

algorithmic information theory Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as st ...

. 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, 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 forever. Alan Turing proved in 1936 that a g ...

. 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 nearly u ...

. 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

). 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
''