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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.