# Why doesn't the recursion theorem prove there is an undecidable finite set?

I created something similar to Sipser's proof for the undecidability of $$A_{TM}$$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't figure out why for the life of me.

$$A_R := \{\langle M \rangle | M = R \land M \text{ accepts "foobar"}\}$$

Assume $$D$$ decides $$A_R$$. $$R:=$$ On any input:

1. By the recursion theorem, get own description $$\langle R \rangle$$
2. Run $$D$$ on $$\langle R \rangle$$
3. Do the opposite of what $$D$$ says. If it rejects, accept. If it accepts, reject.

$$R$$ contradicts what $$D$$ says about $$R$$. So $$D$$ can't be a decider. (i.e. If $$D$$ accepts $$R$$, $$R$$ should accept "foobar", but $$R$$ will reject all strings. If $$D$$ rejects $$R$$, $$R$$ should reject "foobar", but $$R$$ will accept all strings).

But because $$A_R$$ can only contain $$R$$, $$A_R = \emptyset \lor A_R = \{\langle R \rangle\}$$. Either way, it's finite, so $$A_R$$ is decidable.

So what's wrong with the first argument? A few ideas cross my mind:

• I'm losing an important detail by making an informal argument.
• Something odd in the recursive relationship between building $$A_R$$ and referencing $$D$$. (this could possibly be avoided by narrowing it to the subset of TMs with the length of R, which we could "guess" before R is created - and it would still be finite)
• Logic shenanigans (a la the Liar Paradox)

But I just don't see exactly what the problem is.

Elaborating on my interpretation of the error for additional reference:

The argument looks like this:

1. Given an arbitrary decider for $$A_R$$, we can construct a TM $$R$$.
2. Given $$R$$, we construct $$A_R$$.
3. Then we can obtain a contradiction. So there is no decider for $$A_R$$.

That's circular, and hopefully more obviously wrong. And guessing the length of $$R$$, as previously suggested, doesn't work either - because an arbitrary decider has an arbitrary length.

Note that your definition of $$R$$ depends on $$D$$ (step $$2$$). This means you can't conclude that no machine decides $$A_R$$, merely that $$D$$ specifically doesn't.

Basically, what you've written looks like this:

• CLAIM: there is some $$x$$ such that no $$y$$ does [task involving $$x$$].

• PROOF: picking some $$y$$, we build an $$x$$ such that $$y$$ does not do [task involving $$x$$].

And this isn't valid.

It may help to consider an argument of the same "shape" but about a more concrete topic.

• CLAIM: there is a natural number $$n>1$$ which isn't divisible by any prime $$p$$.

• PROOF: fixing a prime $$p$$, let $$n=p+1$$. Then $$n$$ isn't divisible by $$p$$.

The subtle nature of decidability often makes questions about it appear more complicated than they are, and I think this is such a situation.

It's worth noting that the recursion theorem can be applied here to show something - specifically, that the $$A_R$$s are not uniformly decidable.

Specifically, suppose I have some total computable function $$f$$. By the recursion theorem I can whip up a machine $$R$$ such that $$R$$ behaves as you describe for $$D=f(R)$$, and so $$f(R)$$ cannot decide $$A_R$$. This means:

While for each $$R$$ there is some $$D$$ which decides $$A_R$$, there is no computable way to find such a $$D$$ given $$R$$.

This isn't surprising - the same result follows more simply from the unsolvability of the halting problem - but it is an important example of how the recursion theorem can be used to prove non-uniform decidability results even when each of the languages in question is decidable.

It's your second bullet point - something odd in the recursive relationship.

The argument is trying to show a contradiction by exhibiting a finite language that is undecidable.

In other words, the argument needs to show that there exists a finite language $$L$$ such that for every decider $$D$$, there is some input $$w$$ such that $$D$$ incorrectly decides whether $$w \in L$$.

The problem is that you are switching quantifiers: you are picking a decider $$D$$ first, and then you are exhibiting a language (by specifying $$R$$ that depends on $$D$$) and saying that $$D$$ does not decide $$A_R$$ correctly. To obtain a contradiction, your language cannot know in advance the decider it will be tried on.

I'd like to add that while $$A_R$$ is decidable for every fixed $$R$$ (as it is a finite set), if you make $$R$$ an input parameter, the resulting set is no longer decidable.