Timeline for Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 12 at 3:00 | comment | added | Dan Turetsky | @JoelDavidHamkins Imagine $h$ is defined as follows: Attempt to diagonalize using $\phi_{a_0(0)}$. For every $s$, simulate $\phi_{a_0(0)}$ for $a_{2s}(0)$ steps; if this is enough to see convergence of $\phi_{a_0(0)}$ up to length $s$, and to see diagonalizations with all $a_i$ for $i < s$, then output $\phi_{a_0(0)}$ up to length $s$. Otherwise, discard $\phi_{a_0(0)}$ and begin diagonalizing the normal way. If $g_e$ in the definition of $h^*$ enumerates the list in the correct order, we can get any computable $b$ we want out of this. | |
| Aug 12 at 0:05 | comment | added | Joel David Hamkins | @DanTuretsky I'm not quite following you. (But also, for James: I am thinking that the problem also makes perfect sense in Cantor space, where it seems even more natural. Probably equivalent though.) | |
| Aug 11 at 23:30 | comment | added | Dan Turetsky | @JoelDavidHamkins I think we can fix that problem if we can control $g_e$. Make it so that if $g_e$ shows us $a_s$, then $a_s$ differs from $b$ within the first $s$ positions. | |
| Aug 9 at 12:33 | comment | added | Joel David Hamkins | My proposal amounts to: given a list of sequences $a_0,a_1,\ldots$ and a given computable sequence $b$, can we enumerate a sequence that is $b$, if $b$ does not occur amongst the $a_n$, but otherwise is some new sequence $b'$, if it does? If so, we could answer your question affirmatively. But unfortunately, I now think that this proposal isn't possible, since we can make a bad $a_n$ sequence by the Kleene recursion theorem that pretends to put $b$ as $a_0$ and waits until a non-$b$ bit appears in the answer, but then prevents $b$ from appearing. So my idea is not helpful. | |
| Aug 9 at 1:19 | comment | added | Joel David Hamkins | Can't we arrange a path through $\mathcal{O}$ by specifying a cofinal $\omega$-sequence, such that the $n$th element of it is a simple limit in $\mathcal{O}$ that will ensure that a particular computable sequence is hit? That is, I want to reduce from the question of a path to the question of showing that a particular sequence arises at a given trivial kind of limit. Then, we can put them together to make a path on which every computable sequence will arise. | |
| Aug 8 at 21:54 | comment | added | Joel David Hamkins | Very nice revision. I think it is much cleaner now. | |
| Aug 8 at 21:42 | history | edited | James E Hanson | CC BY-SA 4.0 |
deleted 103 characters in body
|
| Aug 8 at 21:38 | comment | added | James E Hanson | @JoelDavidHamkins Well the ultimate application I have in mind involves $\mathbb{R}$ specifically, but it seems rather likely that a construction for the Baire space version won't be too hard to adapt to an $\mathbb{R}$ version, so I'll edit the question. | |
| Aug 8 at 21:36 | comment | added | Joel David Hamkins | Isn't it more natural to forget about $f$ and just think about diagonalizing directly in Baire space? It would simplify the question, but keep the essence, no? Or is there something important in that for your question? That is, you want a path through $\mathcal{O}$ such that iteratively applying the diagonalization to sequences over $\mathbb{N}$ you will get all the computable elements of Baire space. Is this right? | |
| Aug 8 at 21:15 | history | asked | James E Hanson | CC BY-SA 4.0 |