(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}$?

incorrectly, then doesn't that make this a notion ofpredictabilityrather than of unpredictability? $\endgroup$ – LSpice Mar 11 at 22:07notthinking $n \in A$. But I'm thinking mainly of recursively enumerable languages so in this context I prefer to think "halting equals one"; I've considered many notions like this and if I keep flipping the conventions I can't keep track of them. Also, as explained in the question, if every machine isforcedto guess correctly (or incorrectly), then the language is rather unpredictable, for example necessarily undecidable (and much more). $\endgroup$ – Ville Salo Mar 12 at 5:42