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$.
Reduction from $L_{nonuniversal}$ to $L_{finite}$
computability;turing machines;reductions
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 byN(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 acceptNow 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.