Extracting randomness within a subset is hard (Q2663792)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Extracting randomness within a subset is hard |
scientific article |
Statements
Extracting randomness within a subset is hard (English)
0 references
20 April 2021
0 references
The authors prove that every 1-random set \(A\) contains an infinite subset \(G\) that does not compute any set with positive effective Hausdorff dimension. The result is surprising because it does not rely on subset co-subset combinatorics.
0 references
computability theory
0 references
algorithmic randomness
0 references
Mathias forcing
0 references
0 references
