Impredictable subsets of $\mathbb{N}$

Question

(I previously asked a similar question on cstheory.SE; I have simplified the notion, which presumably changes it but does not change the key properties I'm interested in.)

This is about a strange recursion-theoretic notion I encountered, I am unable to make much sense out of it. Some concrete questions below, but I'm also interested in just connections to existing recursion theory notions, I do not recognize these things but I'm no expert on the topic.

Let $P$ be the partial computable functions. Let me be lazy and identify Gödel numbers of partial computable functions with their indices, so actually $P = \mathbb{N}$. I also think of them as Turing machines. Write $T \subset P$ for the total computable functions. If $\psi \in P$, I write $\psi(p){\downarrow}$ for the fact that computation of $\psi$ converges on input $p$, and for a subset $A \subset \mathbb{N}$, I write $A \upharpoonright n = A \cap [0, n]$.

For a total (not necessarily computable) function $\phi : \mathbb{N} \to \mathbb{N}$, a subset $A \subset \mathbb{N}$ is $\phi$-impredictable if $$ \exists \psi \in T: \forall \chi \in P: \exists^\infty p: \psi(p) \in A \iff \chi(p, A \upharpoonright \phi(p)){\downarrow} $$ and impredictable if it is $\phi$-impredictable for all $\phi \in T$. We say $A \subset \mathbb{N}$ is strongly $\phi$-impredictable if $$ \exists \psi \in T: \psi > \phi \wedge \forall \chi \in P: \exists^\infty p: \psi(p) \in A \iff \chi(p, A \upharpoonright (\psi(p)-1))\!\downarrow $$ and strongly impredictable if it is strongly $\phi$-impredictable for all $\phi \in T$.

In words, $\phi$-impredictable means that there is a function $\psi$ that outputs positions $\psi(p)$ on the discrete number line, and these positions have the magical property that if you pick any Turing machine $\chi$, then infinitely many times it happens that $\chi$ guesses correctly whether $\psi(p)$ is in $A$ (in the $\Sigma^0_1$ sense) given access to only $p$ and some initial segment of $A$. The variants of impredictability above are the different ways we may pick this initial segment.

The word "impredictable" of course means roughly the same as "unpredictable", and indeed an impredictable subset must somehow be rather unpredictable (because no machine can guess the values incorrectly). I use it also as a mnemonic for "I'm predictable"; all Turing machines accidentally predict a term infinitely many times, so in some sense these subsets are very predictable.

Some observations that I believe are easily seen to be true:

• If $A$ is strongly impredictable, then it is impredictable.

• If $A$ is $\Pi^0_1$, then $A$ is not impredictable, indeed not $\phi$-impredictable for any $\phi \in T$.

• If you replace $\psi(p)-1$ by $\psi(p)$ in the formula for strong impredictability, then you can just read off whether $\psi(p) \in A$ from the oracle, and thus $\psi(p)-1$ is the maximal number that makes sense in the formula.

A slightly less trivial observation is:

• For every $\phi \in T$, there exists a $\phi$-impredictable $\Sigma^0_1$ subset.

I wrote a proof, but basically you just do it, so I'm not sure it's worth including.

Here are my questions:

Is the halting problem (strongly) impredictable? For some $\phi$? (You may choose your favorite definition of the halting problem.)

and if not...

Is there a (strongly) impredictable recursively enumerable subset of $\mathbb{N}$?

Answer 1

No, the halting set is not impredictable. By the recursion theorem, there is an infinite computable sequence of values such that I control their entry into $K$ (the halting problem). Number these values as $(x_{e, p})_{e < p \in \omega}$. Let $\phi$ be such that $\phi(p) > x_{e, p}$ for all $e < p$. The point is that I can change $K\upharpoonright \phi(p)$ by enumerating various $x_{e,p}$, and I have enough that I can do this $n$ times. Then I claim $K$ is not $\phi$-impredictable.

For each $\psi_e$, we'll build a $\chi_e$ defeating it. We only consider $p > e$. As long as we see $\psi_e(p)\!\uparrow$ or $\psi_e(p) \not \in K_s$, we define $\chi_e(p, K_s\upharpoonright \phi(p))\!\downarrow$. As soon as we see $\psi_e(p)\!\downarrow \in K_s$, we enumerate $x_{e,p}$ into $K$ and make $\chi_e(p,K\upharpoonright \phi(p))\!\uparrow$.

Edit: Adding detail about the use of the recursion theorem. First, $K$ is uniformly 1-complete, so there is a total computable $f$ such that for all $i$ and $n$, $n \in W_i \iff f(i,n) \in K$, where $(W_i)_{i \in \omega}$ is the usual listing of r.e. sets, and also $n \mapsto f(i,n)$ is injective for each $i$.

Now, run infinitely many copies of the above construction, indexed by $i$. Each copy builds its own $\phi$ and $\psi_e$. Each also builds an r.e. set $D_i$. The $i$th copy assumes that $\{f(i,n) : n \in \omega\}$ is the sequence of $x$ that it controls. The instruction "enumerate $f(i,n)$ into $K$" actually means: if $f(i,n)$ has already entered $K$, halt the construction; otherwise, enumerate $n$ into $D_i$ and pause the construction (possibly forever) until $f(i,n)$ enters $K$.

For each $i$, there is a $g(i)$ such that $D_i = W_{g(i)}$. Further, $g$ is computable. So by the recursion theorem, there is a $j$ with $W_j = W_{g(j)}$. So $D_j = W_j$, and $n \in D_j \iff n \in W_j \iff f(j, n) \in K$. So the $j$th copy of the construction is correct about its assumptions: it can cause $f(j, n)$ to enter $K$ by enumerating $n$ into $D_j$ and then waiting; also, no $f(j, n)$ it cares about will enter $K$ before the construction enumerates $n$, because if that happened the construction would halt, and in particular we would have $n \not \in D_j$, contradicting $n \in D_j \iff f(j, n) \in K$.

So the $j$th copy of the construction succeeds.

$\square\square\square$

Yes, there's a strongly impredictable r.e. set. For each $\phi_e$, you have a mother strategy that waits for $\phi_e(p)$ to converge, then chooses a large $x > \phi_e(p)$ and defines $\psi_e(p) = x$. This pair $(p,x)$ is then handed to one of its daughter strategies.

There's a daughter for each $\chi_i$. The basic module is to wait for $\chi_i(p,A_s\upharpoonright (x-1))\!\downarrow$, then enumerate $x$ into $A$, if it's not restrained from doing so. Assuming $x$ was enumerated, also restrain $A\upharpoonright (x-1)$. Give this action priority $e+i+n$, where $n$ is the number of prior restraints imposed by this daughter which are still being respected. The enumeration is permitted provided no restraint created by an action with smaller priority applies.

Then one argues by induction that every daughter succeeds infinitely often.

Answer 2

This is not an answer, this is just an attempt at explaining and elaborating @DT's amazing use of the recursion theorem in my own words (though in the end it's pretty close to what they said). This is orthogonal to the impredictability issue, and perhaps everyone knows this stuff and it's a standard way to think of KRT, but still it was eye-opening for me so I figured I'd share. (And also I'll know if I misunderstood.)

So, suppose we write a program parametrized by $i$, which (in addition to whatever its main duty is) on the side enumerates some set $D_i$, in some arbitrary way. We think of this as having output access to the $i$th recursively enumerable set $W_i$, i.e.\ our program pretends that $D_i = W_i$. Of course, $W_i$ is a fixed object, chosen by the great Turing in the sky, and we do not get to modify it.

Or do we?

Let us do a trick. We modify our program program enumerating $D_i$ as follows: whenever we notice $n \in W_i$ and have not yet output $n \in D_i$, we throw a fit, and stop enumerating numbers altogether. Whenever we enumerate $n \in D_i$, right after that we step into a loop and wait for $n \in W_i$, possible forever. (This modification is really just checking that the equality $D_i = W_i$ that we want seems to hold so far.)

Let $E_i$ be the new set that we enumerate with this modified program. Observe that if $D_i \neq E_i$, then this can only happen because either we throw a fit, implying $n \in W_i \setminus E_i$, or we wait forever for some $n \in W_i$ right after enumerating $n$ into our set, implying $n \in E_i \setminus W_i$. In other words, $D_i \neq E_i$ implies $E_i \neq W_i$. Equivalently, $E_i = W_i \implies D_i = E_i$.

Now, observe that we have described just another program that enumerates a set $E_i$ given a parameter $i$, and so we can easily find a computable function $g$ such that $E_i = W_{g(i)}$. By the recursion theorem, $W_j = W_{g(j)} = E_j$ for some $j$. By the previous paragraph, we must have $D_j = E_j = W_j$. This means that at least on one parameter $j$, we indeed paradoxically get to choose the sequence $W_j$.

(Of course, we don't get to choose $j$, and it's not so paradoxical once you realize that for free we have "free output access" to e.g. some $W_{h(j)}$ for computable $h$, by just making $W_{h(j)}$ follow our construction. Still this is pretty magical.)