Cheap and Secure Web Hosting Provider : See Now

[Solved]: Reduction from $L_{nonuniversal}$ to $L_{finite}$

, , No Comments
Problem Detail: 

As I'm currently preparing for my Algorithms and Complexity exam, I was facing today an other reduction and I'm not quite sure if I solved it correctly.

Given are two languages $L_{finite}$ and $L_{nonuniversal}$:

$L_{finite} = \{\langle M \rangle \mid \vert L(M) \vert < \infty \}$

$L_{nonuniversal} = \{\langle M \rangle \mid L(M) \neq \{0,1\}^* \} $

I'm trying to proof the following reduction: $ L_{nonuniversal} \le_T L_{finite} $

Given $M$ let $M'$ be the Turing Machine that on input $w$ simulates $w$ on $M$. It then takes $w$ after $M$ halted and removes it from its tape and replaces it with a static word $v$ (let this be "1" for example, anything that is $\neq \{0,1\}^*$).

Give $M$ and $M'$ to the $finite$ oracle and return its answer.

I'm trying to show here that if $w$ can only be a static string, then it's $\in finite$.

Asked By : Kevin Goedecke

Answered By : Rick Decker

For brevity, denote $L_{finite}, L_{nonuniversal}$, respectively, as $L_f, L_n$. To establish a mapping from $L_n$ to $L_f$ we map $\langle\,M\rangle\rightarrow\langle\,N\,\rangle$, where $\langle\,N\,\rangle$ is defined by

N(x) =    for s = epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... //i.e., the standard order       run M on s       if M(s) = accept and s = x          return accept 

Now look at the behavior of this mapping:

  • If $\langle\,M\,\rangle\in L_n$ there will be some string in $\{0,1\}^*$ which is not accepted by $M$. Let $z$ be the first such string in standard order. Then $N$ will accept all and only those strings $y$ which are earlier in order than $z$ so $L(N)$ will consist of only those $y$s and so will be finite, i.e., $\langle\,N\,\rangle\in L_f$.
  • Similarly, if $\langle\,M\,\rangle\notin L_n$, then $L(M)=\{0,1\}^*$ so $M$ will accept every string and consequently $L(N)=\{0,1\}^*$, an infinite language, so $\langle\,N\,\rangle\notin L_f$.

These two observations establish the reduction we need.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback