# Universality probability
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Universality_probability
> Markdown URL: https://mediated.wiki/source/Universality_probability.md
> Source: https://en.wikipedia.org/wiki/Universality_probability
> Source revision: 1332653149
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{multiple issues|
{{essay-like|date=May 2017}}
{{more footnotes|date=May 2017}}
{{technical|date=May 2017}}
}}
'''Universality probability''' is an abstruse [probability measure](/source/probability_measure) in [computational complexity theory](/source/computational_complexity_theory) that concerns [universal Turing machine](/source/universal_Turing_machine)s.
== Background ==
A [Turing machine](/source/Turing_machine) is a basic model of [computation](/source/computation). Some [Turing machine](/source/Turing_machine)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](/source/multiplication). Another Turing machine might take input which is a list of numbers and then give output which is those numbers [sorted](/source/sorting) in order.
A [Turing machine](/source/Turing_machine) which has the ability to simulate any other Turing machine is called [universal](/source/Computationally_universal) - in other words, a Turing machine (TM) is said to be a [universal Turing machine](/source/universal_Turing_machine) (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](/source/mathematical) and [philosophical](/source/philosophical) question then arises. If a [universal Turing machine](/source/universal_Turing_machine) is given random input (for suitable definition of [random](/source/random)), how probable is it that it remains universal forever?
== Definition ==
Given a [prefix-free](/source/prefix-free_code) [Turing machine](/source/Turing_machine), the '''universality probability''' of it is the [probability](/source/probability) that it remains [universal](/source/universal_Turing_machine) even when every input of it (as a [binary string](/source/binary_string)) is prefixed by a random binary string. More formally, it is the [probability measure](/source/probability_measure) of reals (infinite binary sequences) which have the property that every initial segment of them preserves the [universality](/source/universal_Turing_machine) of the given Turing machine. This notion was introduced by the computer scientist [Chris Wallace](/source/Chris_Wallace_(computer_scientist)) and was first explicitly discussed in print in an article by Dowe[*{{cite journal |author=Dowe, D.L. |title=Foreword re C. S. Wallace |journal=Computer Journal |volume=51 |issue=5 |pages=523–560 |date=5 September 2008 |doi=10.1093/comjnl/bxm117 |url=http://comjnl.oxfordjournals.org/cgi/content/full/51/5/523 |url-access=subscription }} (and [http://www.csse.monash.edu.au/~dld/Publications/2008/DLDowe_ForewordReCSWallace_CompJVol51Num5Sept2008pp523-560.pdf here])] (and a subsequent article[*Dowe, D. L. (2011), "[http://www.csse.monash.edu.au/~dld/Publications/2010/Dowe2010_MML_HandbookPhilSci_Vol7_HandbookPhilStat_MML+hybridBayesianNetworkGraphicalModels+StatisticalConsistency+InvarianceAndUniqueness_pp901-982.pdf 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]). However, relevant discussions also appear in an earlier article by Wallace and Dowe.[Wallace, C. S. & Dowe, D. L. 1999 ''[http://comjnl.oxfordjournals.org/content/42/4/270 Minimum message length and Kolmogorov complexity]'' Computer J. 42, 270–283]
== Universality probabilities of prefix-free UTMs are non-zero ==
Although the universality probability of a [UTM](/source/universal_Turing_machine) (UTM) was originally suspected to be zero, relatively simple proofs exist that the [supremum](/source/supremum) of the set of universality probabilities is equal to 1, such as a proof based on [random walk](/source/random_walk)s[*Hernandez-Orallo, J. & Dowe, D. L. (2013), "On Potential Cognitive Abilities in the Machine Kingdom", [https://www.springer.com/computer/ai/journal/11023 Minds and Machines], Vol. 23, Issue 2, [https://dx.doi.org/10.1007/s11023-012-9299-6 pp179-210]] and a proof in Barmpalias and Dowe (2012).
Once one has one [prefix-free](/source/prefix-free_code) UTM with a non-zero universality probability, it immediately follows that all [prefix-free](/source/prefix-free_code) [UTM](/source/universal_Turing_machine)s have non-zero universality probability.
Further, because the [supremum](/source/supremum) of the set of universality probabilities is 1 and because the set {{math|{ {{sfrac|''m''| 2''n''}} {{!}} 0 < ''n'' & 0 < ''m'' < 2''n''} }}
is [dense](/source/dense_set) in the interval [0, 1],
suitable constructions of UTMs
(e.g., if ''U'' is a UTM, define a
UTM ''U''2 by ''U''2(0''s'') halts for all strings ''s'',
U2(1''s'') = ''U''(''s'') for all s) gives that the set of universality probabilities is
[dense](/source/dense_set) 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.[{{cite journal |author=Barmpalias, G. and Dowe D.L. |title=Universality probability of a prefix-free machine |journal=Philosophical Transactions of the Royal Society A |volume=370 |issue=1 | pages=3488–3511 |date=2012 |doi=10.1098/rsta.2011.0319|pmid=22711870 |bibcode=2012RSPTA.370.3488B |citeseerx=10.1.1.221.6000 |s2cid=2092954 }}]
Seen as [real number](/source/real_number)s, these probabilities were completely characterized in terms of notions in [computability theory](/source/computability_theory)
and [algorithmic information theory](/source/algorithmic_information_theory).
It was shown that when the underlying machine is universal, these numbers are highly [algorithmically random](/source/Algorithmically_random_sequence). More specifically, it is [Martin-Löf](/source/Per_Martin-L%C3%B6f) random relative to the third iteration of the [halting problem](/source/halting_problem). In other words, they are random relative to null sets that can be defined with four quantifiers in [Peano arithmetic](/source/Peano_arithmetic). Vice versa, given such a highly random number{{clarify|date=August 2015}} (with appropriate approximation properties) there is a Turing machine with a universal probability of that number.
== Relation with Chaitin's constant ==
Universality probabilities are very related to the [Chaitin constant](/source/Chaitin's_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 [halting problem](/source/halting_problem). 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](/source/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).
== See also ==
* [Algorithmic probability](/source/Algorithmic_probability)
* [History of randomness](/source/History_of_randomness)
* [Incompleteness theorem](/source/Incompleteness_theorem)
* [Inductive inference](/source/Inductive_inference)
* [Kolmogorov complexity](/source/Kolmogorov_complexity)
* [Minimum message length](/source/Minimum_message_length)
* [Solomonoff's theory of inductive inference](/source/Solomonoff's_theory_of_inductive_inference)
== References ==
{{Reflist}}
== External links ==
*{{cite journal |author=Barmpalias, G. and Dowe D.L. |title=Universality probability of a prefix-free machine |journal=Philosophical Transactions of the Royal Society A |volume=370 |issue=1 |pages=3488–3511 (Theme Issue 'The foundations of computation, physics and mentality: the Turing legacy' compiled and edited by Barry Cooper and Samson Abramsky) |date=2012 |bibcode=2012RSPTA.370.3488B |doi=10.1098/rsta.2011.0319 |pmid=22711870 |citeseerx=10.1.1.221.6000 |s2cid=2092954 }}
*{{cite journal |author=Dowe, D.L. |title=Foreword re C. S. Wallace |journal=Computer Journal |volume=51 |issue=5 |pages=523–560 |date=5 September 2008 |doi=10.1093/comjnl/bxm117 |url=http://comjnl.oxfordjournals.org/cgi/content/full/51/5/523 |url-access=subscription }} (and [http://www.csse.monash.edu.au/~dld/Publications/2008/DLDowe_ForewordReCSWallace_CompJVol51Num5Sept2008pp523-560.pdf here]).
* Dowe, D. L. (2011), "[http://www.csse.monash.edu.au/~dld/Publications/2010/Dowe2010_MML_HandbookPhilSci_Vol7_HandbookPhilStat_MML+hybridBayesianNetworkGraphicalModels+StatisticalConsistency+InvarianceAndUniqueness_pp901-982.pdf 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 ''[http://comjnl.oxfordjournals.org/content/42/4/270 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", [https://www.springer.com/computer/ai/journal/11023 Minds and Machines], Vol. 23, Issue 2, [https://dx.doi.org/10.1007/s11023-012-9299-6 pp179-210] (and [http://users.dsic.upv.es/~flip/papers/MINDS-MACHINES-potential.pdf here])
* Barmpalias, G. (June 2015), [http://math.uni-heidelberg.de/logic/conferences/ccr2015/Slides%20CCR/Barmpalias_CCR_2015.pdf slides from talk] {{Webarchive|url=https://web.archive.org/web/20160107172301/http://math.uni-heidelberg.de/logic/conferences/ccr2015/Slides%20CCR/Barmpalias_CCR_2015.pdf |date=2016-01-07 }} entitled [http://math.uni-heidelberg.de/logic/conferences/ccr2015/Slides%20CCR/Barmpalias_CCR_2015.pdf ``Randomness, probabilities and machines] {{Webarchive|url=https://web.archive.org/web/20160107172301/http://math.uni-heidelberg.de/logic/conferences/ccr2015/Slides%20CCR/Barmpalias_CCR_2015.pdf |date=2016-01-07 }} at the [http://math.uni-heidelberg.de/logic/conferences/ccr2015 Tenth International Conference on Computability, Complexity and Randomness] {{Webarchive|url=https://web.archive.org/web/20150830102230/http://math.uni-heidelberg.de/logic/conferences/ccr2015/ |date=2015-08-30 }} ([http://math.uni-heidelberg.de/logic/conferences/ccr2015 CCR 2015] {{Webarchive|url=https://web.archive.org/web/20150830102230/http://math.uni-heidelberg.de/logic/conferences/ccr2015/ |date=2015-08-30 }}) conference, 22–26 June 2015, Heidelberg, Germany.
* Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. ''[http://www.cs.auckland.ac.nz/~cristian/Calude361_370.pdf Computing a Glimpse of Randomness].''
== Further reading==
* Ming Li and Paul Vitányi (1997). ''An Introduction to Kolmogorov Complexity and Its Applications''. Springer. [http://citeseer.ist.psu.edu/li97introduction.html Introduction chapter full-text].
* Cristian S. Calude (2002). ''Information and Randomness: An Algorithmic Perspective'', second edition. Springer. {{ISBN|3-540-43466-6}}
* R. Downey, and D. Hirschfeldt (2010), ''Algorithmic Randomness and Complexity'', Springer-Verlag.
{{Irrational number}}
Category:Algorithmic information theory
Category:Theory of computation
Category:Real transcendental numbers
---
Adapted from the Wikipedia article [Universality probability](https://en.wikipedia.org/wiki/Universality_probability) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Universality_probability?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.