[Math] Using Rice’s theorem to prove undecidability of $A_{TM}$

computabilitycomputer sciencelogic

Can you use Rice's theorem to prove that the acceptance problem is undecidable? Wikipedia says that it can be used to solve the Halting problem too but I can't see how that works either.
Here is the version of Rice's theorem I use:

Rice's first Theorem: For every non-trivial, language invariant property
$P$ of a set of Turing machines it holds that the set
$$\{M | P(M) \}$$
is undecidable.

One of the major problems seems to be that $A_{TM}$ is not a set of
Turing machines -but rather encoded couples of Turing machines and strings-, but obviously I'm missing something here.
Unfortunately, I did not come up with anything besides this rather silly objection…

For those wondering: by language invariant I mean the following:
A property $P$ of Turing machines is called language invariant if
$$L_{M1} = L_{M_2} \Rightarrow P(M_1) = P(M_2).$$
Thanks!

Best Answer

You can.

I assume your definition of the acceptance problem is something like this: given a tuple $(M, x)$ decide if $M$ accepts when run on $x$.

To get around the fact that our inputs are not Turing machines but tuples, you can use this trick: given $(M, x)$, construct another machine $M_x$ which does the following on input $y$:

  1. Wipe the input tape clean, leaving a blank tape.
  2. Write $x$ onto the tape ($x$ is a finite string and so can be encoded into the DFA within the machine.)
  3. Simulate $M$. Accept if $M$ accepts, reject if $M$ rejects.

So, this machine does the same thing regardless of its input. If $M$ accepts/rejects/halts on $x$, $M_x$ accepts/rejects/halts on any input $y$.

"Whether this machine accepts on any input" is a non-trivial, language-invariant property of a Turing machine, so Rice's Theorem applies.

Related Question