Demuth's Path to Randomness

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Demuth's Path to Randomness

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Demuth's Path to Randomness

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název periodika

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Svazek periodika

7160

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

15

Strana od-do

159-173

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—