Return to Question

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.

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.

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.

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.

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

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.