3
$\begingroup$

Here is the document: More Undecidable Problems

For a given property $P$ of languages, define $L_P$ as the set of all Turing machines (resp. their encodings) that accept languages with $P$, that is

$\qquad \displaystyle L_{p} = \{ ⟨M⟩ \mid \mathcal{L}(M) \text{ has property } P \}$

If $P$ is a trivial property, that is if $P$ holds for all or no language, $L_P$ is decidable, too (as $L_P=\emptyset$ or $L_P = \{\langle M\rangle \mid M \text{ Turing machine }\}$. If $P$ is not trivial, $L_p$ is undecidable (by Rice's theorem), which means the strings in this language (or with such property) cannot be determined if it can be halt.

We determine a language $M$ has property $P$ by reduce $M$ to another $M'$, and check that if $M'$ accepts the reduced string $x$ from the initial string $w$, we can conclude that $L(M)$ and $L(M')$ have property $P$.

However, as the title suggests, we only reduce a single string $w$ to $x$ and if $x$ is accepted, but we conclude the whole $L(M')$ has property $P$. Thus, $M'$ is obviously part of $L_p$. What if some random strings in $L(M')$ do not have property $P$?

What if M accepts some string, but the reduction of those strings are not accepted by M'?

A reduction from language $L$ to language $L’$ is an algorithm (TM that always halts) that takes a string $w$ and converts it to a string $x$, with the property that: $x$ is in $L’$ if and only if $w$ is in $L$.

Does this imply the reduced language $L'$ will contain every property $P$ from $L$? Since we can conclude that if $L'$ is decidable, then $L$ is decidable as well and vice verse. Can we conclude the same thing to property $P$?

$\endgroup$
  • $\begingroup$ the question is not clear. What is $L_p$? is it the union of $L(M_0)$, $L(M_1)$, etc? or is it the encodings of those machines? $\endgroup$ – Ran G. Jun 10 '12 at 20:22
  • $\begingroup$ @RanG. Typo error. Fixed. $\endgroup$ – Amumu Jun 11 '12 at 2:19
  • 1
    $\begingroup$ Hmmm... so it is a union? why not writing it as $L(M_0) \cup L(M_1) \cdots$? I am still confused. There is a mix between languages (sets of words) and properties (sets of languages). Check cs.stackexchange.com/q/2293/157 for a similar definition and try to make it clearer. $\endgroup$ – Ran G. Jun 11 '12 at 2:55
  • $\begingroup$ I put it as a set, since according to the definition, Lp is a set of all RE languages from all TMs. Regardless, I answered it myself. Pleas have a look if you're interest. $\endgroup$ – Amumu Jun 11 '12 at 3:32
  • 1
    $\begingroup$ @Amumu: The (informal) definitions on slides 3 and 4 are not even close to what you write. I'll edit that. Now a misunderstanding has appeared: "$L_p$ is undecidable, which means the strings in this language (or with such property) cannot be determined if it can be halt." -- that does not make sense. In general, properties have nothing to do with halting. Please look up what "decidability of a language" means. $\endgroup$ – Raphael Jun 11 '12 at 13:11
1
$\begingroup$

I think I got it. Here is Rice's Theorem (Rice Theorem and Turing machine b ehavior prop erties):

Rice's Theorem

I looked it up here: Decidability for the definition of a problem in the context of Turing Machine (slides 9 and 11):

  • Formally, a problem is a language.
  • Each string encodes some instance.
  • The string is in the language if and only if the answer to this instance of the problem is “yes.”

A problem is decidable if there is an algorithm to answer it.

  • Recall: An “algorithm,” formally, is a TM that halts on all inputs, accepted or not.
  • Put another way, “decidable problem” = “recursive language.”

Otherwise, the problem is undecidable

That answers why I only need one string w and reduced x from w to prove a language L with property P is undecidable.

According to Rice's Theorem, if language L with property P has Turing Machines that does not accept language of L, L is undecidable. Thus:

$$L_{p} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n})\}$$ $$L'_{NotInp} = \{ L(M_{0}), L(M_{1}), L(M_{2}),..., L(M_{n}) \}$$

$$M_{i}\mspace{8mu} \text{is}\mspace{8mu} \text{an}\mspace{8mu} i\text{th}\mspace{8mu} \text{Turing} \mspace{8mu} \text{machine},\mspace{8mu} i ≤ n. $$

If the language L' (which contains TMs not in P) is not an empty set, the above L sub P is undecidable. Recall that language with property P is decidable if and only if it is trivial, which means either it contains every RE languages or not at all. Since if a language L with property P is decidable, every Turing Machines accept every string in L, so we don't need to test the acceptance of input to a given TM.

Also, according to the definition of a problem in the context of Turing Machine, if we have the answer (an algorithm) to every instance of the language L sub P (obviously, since L sub P contains every TM), L sub P is decidable. Otherwise, it's not.

Let's be more concrete with an example from here: More Reduction Examples

Language L3

Aside from the proof given on the page, let's look at it more intuitively. We may have Turing Machine M which accepts the three strings. Other than that, the input w can be anything which is not in M, but belong to other M'. Input w can be "Not UIUC", "Not Iowa", or "Not Michigan" or any other strings which do not belong to M. Since we do not have the answer to every instance of the problem with M (because if we do, M will accept every string since every string has property P. In this case, it's not). The language is not trivial, thus it is undecidable.

This is my reasoning. What do you think?

$\endgroup$

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.