Zobrazeno 1 - 4
of 4
pro vyhledávání: '"ERIC P. ASTOR"'
Publikováno v:
Computability. 8:155-177
This paper concerns algorithms that give correct answers with (asymptotic) density $1$. A dense description of a function $g : \omega \to \omega$ is a partial function $f$ on $\omega$ such that $\left\{n : f(n) = g(n)\right\}$ has density $1$. We def
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c495dc527d67ddf6f27620546d9c1240
https://doi.org/10.3233/com-180231
https://doi.org/10.3233/com-180231
We define the notion of a determined Borel code in reverse math, and consider the principle $DPB$, which states that every determined Borel set has the property of Baire. We show that this principle is strictly weaker than $ATR$. Any $\omega$-model o
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::53d1e27c14efa4cfb125e3cf237d6eb2
Autor:
Eric P. Astor
In a previous paper, the author introduced the idea of intrinsic density --- a restriction of asymptotic density to sets whose density is invariant under computable permutation. We prove that sets with well-defined intrinsic density (and particularly
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::cf377fe99bc334631e008be42f112439
http://arxiv.org/abs/1708.04267
http://arxiv.org/abs/1708.04267
Autor:
Eric P. Astor
In 2012, inspired by developments in group theory and complexity, Jockusch and Schupp introduced generic computability, capturing the idea that an algorithm might work correctly except for a vanishing fraction of cases. However, we observe that their
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d60b42f3a4b57a96282b77fcc738fc17