2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ you need to show that if $M \in L_{non-triv}$ then $M' \in L_{finite}$. What is the language of your $M'$ given $M$ is or is not in $L_{non-triv}$? $\endgroup$ – Ran G. Aug 11 '15 at 1:37
  • 1
    $\begingroup$ And what is your question? $\endgroup$ – Raphael Aug 11 '15 at 6:20
  • $\begingroup$ I thought by saying that if $M$ halts I take an arbitrary fix word $v$ and replace it with the one on the tape, I described the language? $\endgroup$ – Kevin Goedecke Aug 11 '15 at 10:23
  • $\begingroup$ A language of $M$, denoted $L(M)$ is all the inputs $x$ that the machine accepts, $$L(M) = \{ x \mid M \text{ accepts }x\}.$$ The content of the tape is meaningless in this definition. So try to state again what you are doing. $\endgroup$ – Ran G. Aug 11 '15 at 17:58
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think thats pretty much what I just figured out with the TA at school. I like your post way more than mine though. Thank you very much! $\endgroup$ – Kevin Goedecke Aug 12 '15 at 15:29
1
$\begingroup$

Just got back from the teachers assistants office and he came up with the following solution.

We are looking for a mapping that fulfills the following conditions:

Given $L_{non-universal}$ and $L_{finite}$ we want a mapping so that if $\langle M \rangle \in L_{non-universal}$ then the mappings ($f(\langle M \rangle)$, $f: \Sigma^* \rightarrow \Sigma^*$) output $\langle M' \rangle$ should be $\in L_{finite}$.

This can be shown by the following:

$M'$ checks on input $x$ for all $|w| \le |x|$ if $w \in T(M)$.

Now if it finds a $w$ $\not\in T(M)$ then we can say that $\langle M \rangle\in L_{non-universal}$ and $T(f(\langle M \rangle)) = \Sigma^{<|w|} $. In addition we can say if we don't find such a $w$ then $\langle M \rangle \not\in L_{non-universal}$ and thereby $f(\langle M \rangle) \not\in L_{finite}$.

I'm looking forward to comments on this.

$\endgroup$
1
$\begingroup$

Another option would be to use the fact, that $L_{nonuniversal} \leq L_{finite} \Leftrightarrow L_{universal} \leq L_{infinite}$ (i.e. the reducibility of the complement: $A \leq B \Leftrightarrow \overline A \leq \overline B$) and prove it the other way round:

$L_{universal} \leq L_{infinite}$

$L_{universal} = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace ^* \vert ~L(M) = \lbrace 0,1 \rbrace ^* \rbrace$

$L_{infinite} = \lbrace \langle M \rangle \in \lbrace 0,1 \rbrace ^* \vert~ \lvert L(M) \rvert = \infty \rbrace$

The mapping function with input $w'$ could look like this:

$\forall u \in \Sigma^{\leq \lvert w' \rvert}$

$~~$Run $M$ with input $u$.

accept $w'$

In this case $M'$ would run through all the $u$ checking whether they are accepted by $M$. If all those $u$ have been accepted by $M$, the machine $M'$ accepts. In case there is some $u \notin L(M)$ the machine would loop forever and therefor not accept $w'$.

$\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.