language-icon Old Web
English
Sign In

Demuth's path to randomness

2012 
Osvald Demuth (1936---1988) studied constructive analysis in the Russian style. For this he introduced notions of effective null sets which, when phrased in classical language, yield major algorithmic randomness notions. He proved several results connecting constructive analysis and randomness that were rediscovered only much later. We give an overview in mostly chronological order. We sketch a proof that Demuth's notion of Denjoy sets (or reals) coincides with computable randomness. We show that he worked with a test notion that is equivalent to Schnorr tests relative to the halting problem. We also discuss the invention of Demuth randomness, and Demuth's and Kucera's work on semigenericity.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    42
    References
    10
    Citations
    NaN
    KQI
    []