2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

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

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.

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