The simple obvious approach
To prove $\mathsf{FIN} \leq_T \mathsf{REGU}$, what we can do is to find a "computable" mapping that maps
- any finite language to a regular language and
- any infinite language to a nonregular language.
The wanted mapping
If words in a regular language are ordered by length, the differences between lengths of adjacent words are bounded. In fact, we can see immediately that they are bounded by the pumping length of that language as in the pumping lemma for regular languages.
The idea to design the mapping is, when the words in the given language become longer, we will ensure the differences between different lengths of the corresponding words become bigger so that they cannot be bounded eventually.
Given a language $L$, we can map it to $$f(L)=\{w\in \Sigma^*\mid w \text{ has a prefix }u\in L\text{ such that } |w|=|u| + |u|^2 \}$$
where $|\cdot|$ is the length of a string. Let us prove $f$ can be the wanted mapping.
Claim. $L$ is finite $\iff$ $f(L)$ is regular.
Proof.
"$\implies$": If $L$ is finite, then $f(L)$ is finite as well. Hence $f(L)$ is regular.
"$\impliedby$": This is an application of the pumping lemma. Suppose $f(L)$ is regular. Let $p$ be a pumping length for $f(L)$. For the sake of contradiction, assume $L$ is not finite. Then there must be a word $u\in L$ with $|u|\ge p$.
Consider $w=uu^{|u|}\in f(L)$. Since $|w|\ge p$, the pumping lemma says $w=xyz$ for some strings $x,y,z$ such that $1\le|y|\le p$ and $xy^2z\in f(L)$. Since $$|xy^2z|=|y| + |w| = |y| + (|u| + |u|^2),$$ we know
$$|u| + |u|^2<|xy^2z|<(|u|+1) + (|u|+1)^2.$$
Since the length of every word in $f(L)$ is of the form $i + i^2$ for some natural number $i$, we must have $xy^2z\not\in f(L)$, which contradicts the fact $xy^2z\in f(L)$. $\quad\checkmark$
From Turing machine $M$ to $M'$
Given a Turing machine $M$, let us construct Turing machine $M'$.
On input string $w$, $M'$ will try searching a prefix $u$ of $w$ such that $|w|=|u| + |u|^2$. This can be done by letting $u$ loop through each prefix of $w$, or just checking whether $|w|=\lfloor\sqrt{|w|}\rfloor+\lfloor\sqrt{|w|}\rfloor^2$.
- If there is no such prefix, $M'$ rejects.
- Otherwise, $M'$ has found $u$ as such. $M'$ will continue to run in the same way as $M$ runs given $u$ as the input.
It is clear that we can construct $M'$ from $M$ algorithmically. A word $w$ is accepted by $M'$ if and only if $w$ has a prefix $u$ such that $\vert w\vert=\vert u\vert+\vert u\vert^2$ and $M$ accepts $u$. That is, $L(M') = f(L(M))$. thanks to the claim above, we know $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$.
A Turing reduction from $\mathsf{FIN}$ to $\mathsf{REGU}$
Given a string $s$, here is how we decide whether $s\in \mathsf{FIN}$ using an oracle that tells whether any given string is in $\mathsf{REGU}$, .
- Check whether $s$ is a valid encoding of a Turing machine. If not, $s\not\in \mathsf{FIN}$.
- Otherwise, $s=\langle M\rangle$ for some Turing machine $M$. Construct $M'$ from $M$ as described above. So, $\langle M\rangle\in\mathsf{FIN}$ $\iff$ $\langle M'\rangle\in\mathsf{REGU}$. Now ask the oracle whether $\langle M'\rangle\in\mathsf{REGU}$.
- If yes, $s\in\mathsf{FIN}$.
- If not, $s\not\in\mathsf{FIN}$. $\quad\checkmark$
An exercise.
Show that $\mathsf{REGU} \leq_T \mathsf{CF}$, where
$$\mathsf{CF} = \{\langle M \rangle \mid M\text{ is a Turing machine, }L(M)\text{ is a context-free language}\}.$$
The simple obvious approach is, similarly, to find a "computable" mapping that maps any regular to a context-free language and any non-regular language to a non-context-free language. If such a mapping is known to you, this exercise is easy; otherwise, it is pretty hard.
