Timeline for Is DNC/DNR stronger than "prompt" non-computability?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 24, 2015 at 18:10 | comment | added | Bjørn Kjos-Hanssen | If memory serves it is in Jockusch's 1989 paper on DNR functions. | |
| Sep 24, 2015 at 18:09 | comment | added | Eric Astor | Huh. I can't seem to get my hands on a copy of that proof, actually... and I'm not sure I've seen it cited before. Can you suggest a text or paper? | |
| Sep 24, 2015 at 7:03 | comment | added | Bjørn Kjos-Hanssen | @EricAstor I guess if you trace through the proof that effectively immune computes DNR, the DNR function $g$ ends up being something like $g(x)=\langle f(0),\dots,f(h(x))\rangle$ for a certain $h$. So maybe one can get that a computably bounded $\mathsf{PNC}$ function computes a computably bounded $\mathsf{DNC}$ function, and study the computable growth rates. | |
| Sep 24, 2015 at 6:27 | vote | accept | Eric Astor | ||
| Sep 24, 2015 at 6:14 | comment | added | Eric Astor | I see - thanks! I do wonder if there's a nice direct construction, though, taking us from "PNC" to DNR. | |
| Sep 24, 2015 at 6:13 | vote | accept | Eric Astor | ||
| Sep 24, 2015 at 6:17 | |||||
| Sep 23, 2015 at 21:19 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |