Martin-Löf randomness
E700156
Martin-Löf randomness is a rigorous mathematical notion of randomness for infinite binary sequences, defined via effectively null sets and closely connected to algorithmic information theory.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Martin-Löf randomness canonical | 4 |
| Martin-Löf test of randomness | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7906518 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Martin-Löf randomness Context triple: [Kolmogorov complexity, relatedTo, Martin-Löf randomness]
-
A.
Kolmogorov complexity
Kolmogorov complexity is a measure of the amount of information in an object, defined as the length of the shortest computer program that can produce it.
-
B.
Randomness and Computation
"Randomness and Computation" is Shafi Goldwasser's influential doctoral thesis that helped lay the foundations of modern complexity theory and cryptography by rigorously exploring the role of randomness in efficient computation.
-
C.
Turing degrees
Turing degrees are an abstract classification of sets of natural numbers or decision problems according to their relative level of algorithmic unsolvability or computational complexity under Turing reducibility.
-
D.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
E.
Blum axioms
Blum axioms are a set of formal conditions introduced by Manuel Blum that rigorously define what constitutes a valid complexity measure in computational complexity theory.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Martin-Löf randomness Target entity description: Martin-Löf randomness is a rigorous mathematical notion of randomness for infinite binary sequences, defined via effectively null sets and closely connected to algorithmic information theory.
-
A.
Kolmogorov complexity
Kolmogorov complexity is a measure of the amount of information in an object, defined as the length of the shortest computer program that can produce it.
-
B.
Randomness and Computation
"Randomness and Computation" is Shafi Goldwasser's influential doctoral thesis that helped lay the foundations of modern complexity theory and cryptography by rigorously exploring the role of randomness in efficient computation.
-
C.
Turing degrees
Turing degrees are an abstract classification of sets of natural numbers or decision problems according to their relative level of algorithmic unsolvability or computational complexity under Turing reducibility.
-
D.
Blum complexity measures
Blum complexity measures are a formal framework in computational complexity theory that rigorously define and compare the resource usage (such as time or space) of algorithms via axiomatic conditions.
-
E.
Blum axioms
Blum axioms are a set of formal conditions introduced by Manuel Blum that rigorously define what constitutes a valid complexity measure in computational complexity theory.
- F. None of above. chosen
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
mathematical concept
ⓘ
notion of randomness ⓘ |
| appliesTo |
Cantor space
NERFINISHED
ⓘ
infinite binary sequences ⓘ |
| assumes | computable measure on the space of sequences ⓘ |
| basedOn | computable enumerability of tests ⓘ |
| characterizedBy |
incompressibility with respect to prefix-free Kolmogorov complexity
ⓘ
measure-theoretic typicality relative to computable measures ⓘ passing all effective statistical tests ⓘ |
| definedBy |
Martin-Löf tests
NERFINISHED
ⓘ
effectively null sets ⓘ |
| equivalentTo |
being random with respect to all computable martingales
ⓘ
having high prefix-free Kolmogorov complexity for all initial segments up to a constant ⓘ passing all Martin-Löf tests ⓘ |
| field |
algorithmic information theory
NERFINISHED
ⓘ
algorithmic randomness ⓘ computability theory ⓘ probability theory ⓘ |
| formalizedIn | Cantor space with the fair-coin measure ⓘ |
| generalizedTo |
Martin-Löf randomness for arbitrary computable probability measures
ⓘ
Martin-Löf randomness relative to an oracle ⓘ |
| hasAlternativeName |
ML-randomness
ⓘ
Martin-Löf algorithmic randomness NERFINISHED ⓘ |
| hasProperty |
almost every sequence (Lebesgue measure) is Martin-Löf random
ⓘ
invariant under computable measure-preserving isomorphisms ⓘ set of Martin-Löf random sequences has measure one ⓘ set of non-Martin-Löf random sequences is effectively null ⓘ there exists a universal Martin-Löf test ⓘ |
| introducedBy | Per Martin-Löf NERFINISHED ⓘ |
| introducedInYear | 1966 ⓘ |
| relatedTo |
Chaitin randomness
ⓘ
Kolmogorov complexity NERFINISHED ⓘ Levin–Schnorr theorem NERFINISHED ⓘ effective descriptive set theory ⓘ effective null sets ⓘ |
| strongerThan |
Schnorr randomness
ⓘ
computable randomness ⓘ |
| usedIn |
analysis of random sequences in computation
ⓘ
foundations of probability ⓘ study of typical behavior in dynamical systems ⓘ |
| usesConcept |
effectively open sets
ⓘ
measure zero sets ⓘ prefix-free Kolmogorov complexity ⓘ universal Martin-Löf test NERFINISHED ⓘ |
| weakerThan | 2-randomness ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Martin-Löf randomness Description of subject: Martin-Löf randomness is a rigorous mathematical notion of randomness for infinite binary sequences, defined via effectively null sets and closely connected to algorithmic information theory.
Referenced by (5)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Martin-Löf test of randomness