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