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), &quot;proving&quot; 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:

By the recursion theorem, get own description $\langle R \rangle$
Run $D$ on $\langle R \rangle$
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 &quot;foobar&quot;, but $R$ will reject all strings. If $D$ rejects $R$, $R$ should reject &quot;foobar&quot;, 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 &quot;guess&quot; 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:

Given an arbitrary decider for $A_R$, we can construct a TM $R$.
Given $R$, we construct $A_R$.
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.
Your argument "goes backwards."

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&gt;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.