1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If no machine can guess the values incorrectly, then doesn't that make this a notion of predictability rather than of unpredictability? $\endgroup$ – LSpice Mar 11 at 22:07
  • $\begingroup$ It can feel that way, hence the "I'm predictable" pun. However, you could just as well say "guesses incorrectly" and just think that halting represents not thinking $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 is forced to 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
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sounds amazing. I'll need some time to process this though. $\endgroup$ – Ville Salo Mar 10 at 13:03
  • $\begingroup$ On the face of it this answer is so far beyond my level that I'm afraid to ask anything. I will ask about where I get stuck first, just in case it magically clicks... The first proof seems to use some interpretation of the (Kleene?) recursion theorem I've not heard of, naively it seems to me that machines either halt or not, and I don't get to choose anything. I wonder where I can see it elaborated on? (But maybe I should read a book and get back to this later.) $\endgroup$ – Ville Salo Mar 10 at 14:04
  • 2
    $\begingroup$ @VilleSalo Yes, Kleene's recursion theorem. There must be an example of using it in this manner somewhere in Soare's text, but I'm having trouble finding one at the moment. I've edited more detail into my answer. Hope this helps. $\endgroup$ – Dan Turetsky Mar 11 at 21:58
  • $\begingroup$ I think I understood the first part now, more or less, that's already worth accepting over, so I'll do that and start working on the second part. $\endgroup$ – Ville Salo Mar 12 at 8:41
1
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.