[Solved]: A concrete example about string w and string x used in the proof of Rice's Theorem

Problem Detail: 

So, in lectures about Rice's Theorem, reduction is usually used to proved the theorem. Reduction usually consists a construction of $M'$, using a TM $M$ which is in the form $\langle M,w \rangle$ to be simulated first, an input $x$ to be simulated if $M$ accepts. $M'$ accepts if x is accepted.

I really want a concrete input about $\langle M,w \rangle$ and $x$. For example:

$L = \{ \langle M\rangle \mid L(M) = \{\text{ stackoverflow }\}\}$, that is L contains all Turing machines whose languages contain one string: "stackoverflow". $L$ is undecidable.

What kind of $\langle M,w \rangle$ to be simulated?

Suppose we have input x = "stackoverflow" or x = "this is stackoverflow" or any x with "stackoverflow" in it.

What if we first simulate a TM $M$ selected from in the possibilities of all TMs, and this TM accepts only a single character $a$ as its language. So, we simulate this $\langle M,w \rangle$ with $w = a$, and surely it will be accepted. And then input $x$ is also accepted according to the definition of $L$.

So, we conclude that $\langle M,w \rangle$ in which language is a single $a$ is reducible to $L$ that accepts all TMs which have "stackoverflow"?

Edit: I've just looked up a brief definition of reduction. A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Given that definition, I think the correct TM $M$ with its description $\langle M,w \rangle$ in my example should be a TM such that it accepts regular languages. This is the harder problem. If this is solvable, then my trivial $L$ with one string is solvable. But apparently, it's not according to the proof. We can effectively say we reduced from language one string problem to regular language problem and try to solve it. Previously, I thought the other way around: $\langle M,w \rangle$ is reduced to one string problem.

Is my thinking correct?

Asked By : Amumu

Answered By : Ben

A reduction is a transformation from an unknown but easier problem to a harder problem but already known. If the harder problem is solvable, so is the easier one. Otherwise, it's not.

Your characterisation of reduction is a bit misleading. You don't start with an "easy" problem and reduce it to a "harder" problem (how can you know it's an easy problem if it's unknown? Often you're attempting the reduction to find out whether your problem is "easy").

A reduction is a computable transformation from one problem to another. It proves that the source problem is no harder (in some sense) than the target problem.

Sometimes we do this because we already know the source problem is impossible to solve; this proves that the target problem is impossible too. Since the source problem is "no harder" than the target problem, and we already know the source is undecidable, the target problem must be undecidable (or the source would in fact be harder). More intuitively, if we can reduce the source to the target and the source is undecidable, then the target must be undecidable or we could use the reduction and the solution to the target in order to solve the source (which we already know can't be done).

Other times we find a reduction because we know the target problem is decidable. This shows that the source problem is decidable too.

So you can use a reduction argument either to a problem that's already known to be decidable, or from a problem that's already known to be undecidable, depending on what you're trying to prove.

---

So, Rice's Theorum. I don't quite understand the questions you're asking, since I haven't seen the particular statement of the proof that's giving you trouble. Instead, here's my quickie explanation of how to prove Rice's Theorum, which I'm pretty sure is similar.

Suppose we have an arbitrary language $L$, consisting of (encodings of) exactly those TMs with some non-trivial semantic property $P$.[1] To prove that there is no algorithm for deciding language $L$, I will reduce the Halting Problem to the decision problem for $L$.

So the Halting Problem (or the particular variant of it I will use here) is: given $\langle M, x\rangle$, an encoding of a Turing machine $M$ and an input $x$, does $M$ halt on $x$?

My reduction must transform the input to the Halting Problem $\langle M, x \rangle$ into the input for the hypothetical decider for $L$, which I will call $ML$. $L$ is a language of Turing machines, so $ML$'s input looks like $\langle M \rangle$.

So my reduction will take $\langle M, x \rangle$ and compute $\langle M' \rangle$. $M'$ is a machine that takes an input $w$ and functions as follows:

1. Simulate $M$ on $x$, ignoring the result
2. Simulate $MP$ on $w$; accept if it accepts and reject if it rejects

Here $MP$ is a machine that whose encoding is in $L$ i.e. it has the property $P$. Since we're considering a non-trivial property $P$, such an $MP$ is guaranteed to exist.

Note that $x$ is part of the machine $M'$ the reduction has produced, while $w$ is the input to that machine whenever it is run. $x$ and $w$ are completely unrelated. We are assuming we've been given a particular $x$ as part of the input to the Halting Problem, but since we haven't proposed running $M'$, there is no specific $w$ at the moment.

Now, if $M$ halts on input $x$, then $M'$ always gets to stage 2 and thus accepts/rejects exactly the same strings as $MP$. Since the property $P$ is semantic, it doesn't depend on the particular TM, only on the language it accepts, so in this case $M'$ also has property $P$. If $M$ doesn't halt on input $x$, then $M'$ never gets to an accept state regardless of input, so its language is the empty language.

So now we don't want to run $M'$ on anything, since it might not even halt, but we could run our hypothetical $ML$ on it to check whether it's in $L$. This will almost tell us whether $M$ halts on $x$; the only thing we're missing is that the empty language might happen to have property $P$, in which case $ML$ will always accept $M'$ whether or not $M$ halts on $x$. But we can easily amend $M'$: if $P$ is true of the empty language (which our reduction could check using $ML$ if $ML$ could actually exist), then we use $MN$ instead of $MP$ - some machine that doesn't have property $P$ (which is also guaranteed to exist by the non-triviality of $P$) - and then our $M'$ has property $P$ if-and-only-if $M$ doesn't halt on $x$.

So now we've shown that a hypothetical decider for $L$, the language of machines with property $P$, could be used to decide the Halting Problem. Since we already know the Halting Problem can't be decided, $ML$ can't exist. Since the only thing I assumed about $P$ was that it was a semantic and non-trivial property, the proof holds for any semantic and non-trivial property.

I cheated a little in my reduction, since I had to use $ML$ to work out whether the empty language has property $P$, which means the reduction is only computable if $ML$ exists. This breaks my earlier definition of a reduction as "a computable transformation from one problem to another", but the proof by contradiction is still perfectly valid; proving a language undecidable by reduction from an undecidable language is really just a special case of a proof by contradiction anyway.

---

[1] A property of a TM is semantic if all TMs that accept the same language share the property, i.e. the property doesn't depend on the particular implementation of the TM but only on the language it accepts. A property is non-trivial if there is at least one TM that has the property and at least one TM that doesn't have the property.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2433