# Reduction from $L_{nonuniversal}$ to $L_{finite}$

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

• 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}$? – Ran G. Aug 11 '15 at 1:37
• And what is your question? – Raphael Aug 11 '15 at 6:20
• 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? – Kevin Goedecke Aug 11 '15 at 10:23
• 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. – Ran G. Aug 11 '15 at 17:58

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.

• 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! – Kevin Goedecke Aug 12 '15 at 15:29

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.

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