Demuth's Path to Randomness

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10126353" target="_blank" >RIV/00216208:11320/12:10126353 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007%2F978-3-642-27654-5_12" target="_blank" >http://link.springer.com/chapter/10.1007%2F978-3-642-27654-5_12</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-27654-5_12" target="_blank" >10.1007/978-3-642-27654-5_12</a>

Result language
angličtina
Original language name
Demuth's Path to Randomness
Original language description
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 Kučera's work on semigenericity.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)