4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Note that $\langle M,w \rangle$ is not an encoding of a machine -- that is $\langle M \rangle$ -- but of a machine and an input. $\endgroup$ – Raphael Jun 21 '12 at 8:54
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for clarification. So, in the context of reduction we are talking, which is Rice's Theorem, our two languages can be reduced to each other because it's in the same class of difficulty, and the source problem is proved to be no harder or easier before the transformation. What I am still struggle is, the way how reduction is performed in the proof. I still can't escape the thought of string transformation without mutating it. It's weird to see our string w to be transformed passed into the machine, and reduced string x is elsewhere but not mutated from w. $\endgroup$ – Amumu Jun 21 '12 at 15:07
  • $\begingroup$ For example: we feed the input < M,w > into a machine S which decide language with property P. We will construct a TM M', simulate < M,w > and if w is accepted, we simulate M'' with x. The input < M,w > can be all possible TMs, each TM M will be combined with each of its string in its language into S. My only concern is, after each input < M,w >, M is successfully simulated and w is accepted, where does x come from when its not "reduced", or "transform" from w? I read on the UIUC page, and it is said that x is from user input. So confusing. $\endgroup$ – Amumu Jun 21 '12 at 15:24
  • $\begingroup$ Here is the page: cs.uiuc.edu/class/fa07/cs273/Handouts/reductions . You can search using the phrase "user to input" (without quote). $\endgroup$ – Amumu Jun 21 '12 at 15:26
  • $\begingroup$ I don't quite understand what you don't understand, so I've just written an explanation of a proof of Rice's Theorum. If there are any particular parts of this that you don't understand, please let me know. $\endgroup$ – Ben Jun 22 '12 at 2:47
  • $\begingroup$ Great Ben, thanks for you dedicated post. My initial problem is, since I heard "reduction" in my lecture, which takes w and convert to x, I confused with string mutation i.e. if you got w = "aaa", by some reduction, w will be mutated to become some x = "a", and let some other machine simulates on x. This is the major confusion about the reduction we talk about. Reduction is not string mutation. We simply use other problem to solve other problem. Oh well, I start talking the same thing as the proof. $\endgroup$ – Amumu Jun 22 '12 at 17:27
2
$\begingroup$

Your "proof sketch" contains almost no information; you need to note the special reduction partner. Usually, the halting problem is reduced to deciding the given, arbitrary non-trivial encoding set $L$. If $L$ was decidable, so would be HP but we know HP is undecidable; therefore $L$ is undecidable. So there is no concrete $\langle M,w \rangle$ that "breaks" decidability; we need to deal with any $\langle M,w \rangle$ (as HP does¹).

In your edit, you commit a common fallacy: $L = \{\text{ stackoverflow }\}$ is a regular language and thus decidable. However, Rice's Theorem deals not with $L$ but with

$\qquad \displaystyle L' = \{ \langle M \rangle \mid \mathcal{L}(M) = L \}$,

a very different beast. In particular, $L'$ is infinite. The "harder"

$\qquad \displaystyle L'' = \{ \langle M \rangle \mid \mathcal{L}(M) \in \mathrm{REG} \}$

is not decidable, either, so there is no paradoxon here.


  1. That is for the general halting problem; often a version restricted to the diagonal, i.e. $\{ \langle M, \langle M \rangle \rangle \mid M \text{ Turing machine }\}$, is used.
$\endgroup$
  • $\begingroup$ You are right. Rice's Theorem deals with TM (a.k.a. algorithm), not with the language. However, I really don't understand how you would implement the machine using in the proof for Rice's Theorem. I just don't understand what's the input for w, since the only input from outside is x. Let's have an example. On this page, it is said that the TM M' "has w "hardcoded" into it" such as "w="Bob the Builder"", and "Mw will ask the user to input a value for x" (you can copy and paste to search on the page without quote). $\endgroup$ – Amumu Jun 21 '12 at 9:21
  • $\begingroup$ "The Turing machine Mw is typically designed so it accepts one set of strings x (call the set X) if M accepts w, and a totally different set of strings x (call the set Y) if M doesn't accept w". Since w is hardcoded, the only input is string x from user, and according to the proof for the theorem, x is in L with property P iff w is in L. But w is hardcoded, and at the same time, we "reduce" (only) a single string w to x. I thought that this reduction must be a transformation, i.e. the characters of w are replaced (insert/delete/update) to create a new string x. $\endgroup$ – Amumu Jun 21 '12 at 9:25
  • $\begingroup$ Well, I can just follow the proof template (similar to UIUC), prove a language undecidable by using an undecidable language, derives a contradiction then concludes. Mindlessly. But I really want to understand what it is. $\endgroup$ – Amumu Jun 21 '12 at 9:28
  • $\begingroup$ Alright. I get the reduction now. Simply, instead of testing whether a machine M has a property P, we construct a machine M' which simulates M with input w. If M accepts w, this means M is reducible to the language of x, then we simulate M'' which has property P against input x. If M''` accepts, M' is eligible to be in language Lp. The point of the proof is, since M can't decide, M' can't decide as well, but we assumed Lp is decidable. At least it makes sense to me now. My flaw is as you said, the common fallacy between language and TM. $\endgroup$ – Amumu Jun 21 '12 at 11:44
  • $\begingroup$ @Amumu: Do you still need input from me or have you answered your questions in the meantime? $\endgroup$ – Raphael Jun 21 '12 at 21:37
1
$\begingroup$

Finally I found my answer in this video about reduction which gives a clear explanation for my struggle.

This video and this are about the regular expression example to demonstrate reduction.

But that doesn't mean the other answers are not helpful. They helped me to clear my misconceptions, so thanks for that.

To summarize, I didn't quite understand about the reduction written in the lecture notes or listening to my lecture, since in all the lecture notes, we construct a big TM S which takes < M,w > as input, and later reduce it to machine M' which accepts input x. I didn't get the part where < M,w > is the input, and suddenly x becomes the input and being "entered by a user".

In the lecture video, Professor Shai Simonson does not use the notation w and x. Instead, he use only x. This is well demonstrated in the regular expression example in video 4 (or 5, I am busy now but I will verify later). Instead of solving whether x is in a regular set or not, we solve whether x is not in the regular set. In other words, if x is not in regular set, it's in context free language. So we reduce from the regular language problem to a context free language problem. The same input x is used.

I guess the notion w is meant to be the string to be accepted by the original problem and x is the new problem. This is just a logical classification in our mind. In the practice, there should be one input.

$\endgroup$
  • $\begingroup$ Please summarise the solution here. The video might vanish some day. $\endgroup$ – Raphael Jun 21 '12 at 21:38
  • $\begingroup$ Sure your answer will help. I would still listen to you. $\endgroup$ – Amumu Jun 22 '12 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.