Algorithmically random sequence
Intuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR.
- Comment
- enIntuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR.
- Date
- enJune 2021
- DifferentFrom
- Randomized algorithms
- Has abstract
- enIntuitively, an algorithmically random sequence (or random sequence) is a sequence of binary digits that appears random to any algorithm running on a (prefix-free or not) universal Turing machine. The notion can be applied analogously to sequences on any finite alphabet (e.g. decimal digits). Random sequences are key objects of study in algorithmic information theory. As different types of algorithms are sometimes considered, ranging from algorithms with specific bounds on their running time to algorithms which may ask questions of an oracle machine, there are different notions of randomness. The most common of these is known as Martin-Löf randomness (K-randomness or 1-randomness), but stronger and weaker forms of randomness also exist. When the term "algorithmically random" is used to refer to a particular single (finite or infinite) sequence without clarification, it is usually taken to mean "incompressible" or, in the case the sequence is infinite and prefix algorithmically random (i.e., K-incompressible), "Martin-Löf–Chaitin random". It is important to disambiguate between algorithmic randomness and stochastic randomness. Unlike algorithmic randomness, which is defined for computable (and thus deterministic) processes, stochastic randomness is usually said to be a property of a sequence that is a priori known to be generated by (or is the outcome of) an independent identically distributed equiprobable stochastic process. Because infinite sequences of binary digits can be identified with real numbers in the unit interval, random binary sequences are often called (algorithmically) random real numbers. Additionally, infinite binary sequences correspond to characteristic functions of sets of natural numbers; therefore those sequences might be seen as sets of natural numbers. The class of all Martin-Löf random (binary) sequences is denoted by RAND or MLR.
- Hypernym
- Sequence
- Is primary topic of
- Algorithmically random sequence
- Label
- enAlgorithmically random sequence
- Link from a Wikipage to an external page
- www.mcs.vuw.ac.nz/math/papers/bullSep12.ps
- web.archive.org/web/20160202145649/http:/www.mcs.vuw.ac.nz/math/papers/bullSep12.ps
- www.cs.bu.edu/~gacs/papers/Gacs-every-seq.pdf
- homepages.cwi.nl/~paulv/kolmogorov.html
- nbn-resolving.de/urn/resolver.pl%3Furn:nbn:de:hebis:30-20812
- Link from a Wikipage to another Wikipage
- Algorithmic information theory
- Arithmetical hierarchy
- Betting
- Cantor space
- Category:Algorithmic information theory
- Category:Randomness
- Chaitin's constant
- Church–Turing thesis
- Claus-Peter Schnorr
- Complement (set theory)
- Computable
- Computably enumerable
- Concatenation
- Countable
- Data compression
- Decidability (logic)
- Gambling
- G-delta set
- Gregory Chaitin
- Halting problem
- Independence (probability theory)
- Kolmogorov complexity
- K-trivial set
- Lebesgue measure
- Leonid Levin
- Martingale (probability theory)
- Measure (mathematics)
- Michiel van Lambalgen
- Monte Carlo method
- Normal number
- Oracle machine
- Per Martin-Löf
- Péter Gács
- Prefix (computer science)
- Probability
- Probability distribution
- Randomness test
- Random sequence
- Recursively enumerable
- Richard von Mises
- Sequence
- Statistical randomness
- Stochastics
- Theory of computation
- Turing degree
- Turing reducible
- Turing reduction
- Universality probability
- Universal Turing machine
- Reason
- enSimilar in what way? In that both theorems concern Turing machines and/or computability?
- SameAs
- 4o7hB
- m.0bsr3d
- Q55731673
- Q612552
- Secuencia algorítmicamente aleatoria
- Sequência algoritmicamente aleatória
- アルゴリズム的ランダムな無限列
- 알고리즘 난수열
- Subject
- Category:Algorithmic information theory
- Category:Randomness
- WasDerivedFrom
- Algorithmically random sequence?oldid=1108975092&ns=0
- WikiPageLength
- 21256
- Wikipage page ID
- 4257548
- Wikipage revision ID
- 1108975092
- WikiPageUsesTemplate
- Template:Cite book
- Template:Cite conference
- Template:Cite journal
- Template:Distinguish-redirect
- Template:Explain
- Template:More footnotes
- Template:Reflist
- Template:Su