Timeline for Antirandom reals
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2019 at 19:22 | vote | accept | Noah Schweber | ||
| Sep 29, 2015 at 1:47 | comment | added | Jason Rute | Also, I doubt your question is true---whether using NCR or the Schnorr version. NCR corresponds to universal measure zero sets (sets which are measure zero in every continuous Borel measure). It is known that there are uncountable universal measure zero sets. On the other hand, it is consistent with ZFC that strong measure zero sets (which as you showed, as universal measure zero) can be countable. Then again, maybe something strange is happening the effective world which makes these two notions collapse. (This all comes from a quick Google search, so it is possible I misread something.) | |
| Sep 29, 2015 at 1:40 | comment | added | Jason Rute | @JoeMiller, in your final edit, your proof shows that every anti-random is not $\mu$-Schnorr random for any continuous measure $\mu$. New question: If $A$ is Schnorr NCR is it antirandom? Also, it is not obvious off hand to me how to show that NCR and Schnorr NCR are different---if they even are. Last, there are subtleties about what I mean by Schnorr randomness relative to a noncomptuable measure. I think in this case, you need to have the test depend on the oracle, but it can depend in a uniform way. (I really need to finish my paper on SR for noncomptuable measures!) | |
| Sep 28, 2015 at 20:49 | history | edited | Joe Miller | CC BY-SA 3.0 |
Antirandom -> NCR
|
| Sep 28, 2015 at 4:01 | history | edited | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |
edited body
|
| Sep 27, 2015 at 21:26 | comment | added | Joe Miller | The notion was introduced by Reimann and Slaman. They say that $A$ is never continuously random (NCR) if there is no continuous measure $\mu$ such that $A$ is Martin-Löf random with respect to $\mu$, where $\mu$ is used both as an oracle for the test and to measure the size of the test elements. To be precise, we don't use $\mu$ as an oracle, but discrete "names" of $\mu$; if for every name $m$ of $\mu$ there is a $\mu$-ML test relative to $m$ that covers $A$, then $A$ is not Martin-Löf random with respect to $\mu$. | |
| Sep 27, 2015 at 21:15 | history | edited | Joe Miller | CC BY-SA 3.0 |
added 478 characters in body
|
| Sep 27, 2015 at 21:15 | comment | added | Ashutosh | Hi Joe, can you tell me the definition of "never continuously random". | |
| Sep 27, 2015 at 21:06 | history | edited | Joe Miller | CC BY-SA 3.0 |
added 478 characters in body
|
| Sep 27, 2015 at 20:43 | history | edited | Joe Miller | CC BY-SA 3.0 |
Added the improved example and the question.
|
| Sep 27, 2015 at 20:06 | comment | added | Joe Miller | In the $\Delta^0_2$ case, it may not be enough to assume that $A_s\upharpoonright s$ is correct (for infinitely many $s$). That's not clear to me. It would be enough to assume that $A_s\upharpoonright s = A_t\upharpoonright s$ for all $t>s$. | |
| Sep 27, 2015 at 19:52 | comment | added | Noah Schweber | Very nice! This works for $\Delta^0_2$-approximations, too, right? (If $A=\lim a(x, s)$ with $a$ computable, then call $s$ "strongly true" if $A\upharpoonright s=\{x<s: a(x, s)=1\}$ - then everything still checks out.) But it seems to stop there. Can we get a non-$\Delta^0_2$ antirandom real? | |
| Sep 27, 2015 at 16:53 | history | edited | Joe Miller | CC BY-SA 3.0 |
I was confusing $f$ with $-\log(f)$ in my first post. Adding $g$ solved the problem.
|
| Sep 27, 2015 at 16:46 | review | First posts | |||
| Sep 27, 2015 at 17:16 | |||||
| Sep 27, 2015 at 16:43 | history | answered | Joe Miller | CC BY-SA 3.0 |