Line 21: Line 21:
  
  
 
+
{{Template:FB}}
<div class="fb-like"  data-layout="standard" data-action="like" ></div>
 
 
 
 
 
<div class="fb-send"></div><div class="fb-share-button"  data-type="button_count"></div>
 
  
  

Revision as of 10:49, 11 December 2013

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma → \Sigma$ be a polynomial time computable bijection such that $(\forall x) [x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following CANNOT be true ?

(A) <math>L_1</math> Image not present P and <math>L_2</math> is finite

(B) <math>L_1</math> Image not present NP and <math>L_2</math> Image not present P

(C) <math>L_1</math> is undecidable and <math>L_2</math> is decidable

(D) <math>L_1</math> is recursively enumerable and <math>L_2</math> is recursive

Solution

A language <math>L</math> is recursively enumerable (partially decidable), iff there is a Turing Machine <math>M</math>, which can enumerate all the strings of <math>L</math>.

So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math>, using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, we are getting a <math>TM</math> which is enumerating all strings of <math>L_1</math>, which means <math>L_1</math> should also be recursively enumerable (partially decidable).

Thus, if <math>L_2</math> is decidable, <math>L_1</math> will at-least be partially decidable.





blog comments powered by Disqus

Consider two languages $L_1$ and $L_2$ each on the alphabet $\Sigma$. Let $f : \Sigma → \Sigma$ be a polynomial time computable bijection such that $(\forall x) [x\in L_1$ iff $f(x) \in L_2]$. Further, let $f^{-1}$ be also polynomial time computable.

Which of the following CANNOT be true ?

(A) <math>L_1</math> Image not present P and <math>L_2</math> is finite

(B) <math>L_1</math> Image not present NP and <math>L_2</math> Image not present P

(C) <math>L_1</math> is undecidable and <math>L_2</math> is decidable

(D) <math>L_1</math> is recursively enumerable and <math>L_2</math> is recursive

Solution[edit]

A language <math>L</math> is recursively enumerable (partially decidable), iff there is a Turing Machine <math>M</math>, which can enumerate all the strings of <math>L</math>.

So, suppose <math>L_2</math> is decidable. Now we have a <math>TM</math> <math>T</math>, which can enumerate all strings of <math>L_2</math>. For each of these strings <math>w</math>, we can find <math>x</math>, such that <math>f(x) = w</math>, using the function $f^{-1}$. Since $f^{-1}$ is bijective, it ensures that for each of the string <math>w</math> enumerated by <math>T</math>, we are getting a unique $f^{-1}(w)$ (because of one-one property of bijection) and we are guaranteed that we'll generate all strings of $L_1$ (because of "co-domain = range" property of bijection),. i.e.; we are actually enumerating all strings of <math>L_1</math>. Thus, we are getting a <math>TM</math> which is enumerating all strings of <math>L_1</math>, which means <math>L_1</math> should also be recursively enumerable (partially decidable).

Thus, if <math>L_2</math> is decidable, <math>L_1</math> will at-least be partially decidable.




blog comments powered by Disqus