(I previously asked a similar question on [cstheory.SE](https://cstheory.stackexchange.com/questions/46422/apredictable-sets); 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](https://wikidiff.com/unpredictable/impredictable) "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}$?
> 
> 
> 



Impredictable subsets of $\mathbb{N}$
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.


