Universality probability
Universality probability is an abstruse probability measure in computational complexity theory that concerns universal Turing machines.
Background
A Turing machine is a basic model of computation. Some Turing machines 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. Another Turing machine might take input which is a list of numbers and then give output which is those numbers sorted in order.A Turing machine which has the ability to simulate any other Turing machine is called universal - in other words, a Turing machine is said to be a universal Turing machine if, given any other TM, there is a some input such that the first TM given that input "header" will forever after behave like the second TM.
An interesting mathematical and philosophical question then arises. If a universal Turing machine is given random input, how probable is it that it remains universal forever?
Definition
Given a prefix-free Turing machine, the universality probability of it is the probability that it remains universal even when every input of it is prefixed by a random binary string. More formally, it is the probability measure of reals 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 and was first explicitly discussed in print in an article by Dowe. 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 was originally suspected to be zero, relatively simple proofs exist that the supremum of the set of universality probabilities is equal to 1, such as a proof based on random walks and a proof in Barmpalias and Dowe.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 supremum of the set of universality probabilities is 1 and because the set
is dense in the interval,
suitable constructions of UTMs
halts for all strings s,
U2 = U gives that the set of universality probabilities is
dense in the open interval.
Characterization and randomness of universality probability
Universality probability was thoroughly studied and characterized by Barmpalias and Dowe in 2012.Seen as real numbers, these probabilities were completely characterized in terms of notions in computability theory
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 other words, they are random relative to null sets that can be defined with four quantifiers in Peano arithmetic. Vice versa, given such a highly random number there is a Turing machine with a universal probability of that number.