Let $A = (\delta_A, Q, q_0, F)$ be a DFA for $L$ (in some alphabet $\Sigma$).
Then define $B$ as follows:
- The states $Q_B$ of $B$ are of the form $[q,S]$ where $q \in Q$ and $S \subseteq Q$.
- The initial state of $B$ is $[q_0, F]$.
- $\delta_B([q,S],a) = [\delta_A(q,a), T]$ where $T = \{p \in Q: \exists b \in \Sigma: \exists p' \in S: \delta_A(p,b) = p' \}$
- The accepting states of $B$ are $F_B = \{[q,S] : q \in S \}$.
Then we have the following invariant by construction: all reachable states $[q,S]$ after some input are such that $q$ is the state that $A$ would be in after reading that input, and the states in $S$ are all those states such that there is a path from that state to an accepting state (in $A$) that has the same length as the input that was read.
This holds for the initial state (no input, so the only state $A$ could be in is $q_0$ and the only accepting states on no input are those in $F$).
The way the transition rule is defined also upholds the relation: the first part just does what $A$ would have done on that extra letter, and we update the states so that there is a path to an accepting state that is 1 step longer. We could formally prove it by induction on the length of the input.
And when we are in a state $[q,S]$ with $q \in S$ after reading some input $w_1$, we know that $q$ is the state of $A$ after reading $w_1$ and as $q \in S$ there is some input $w_2$ with $|w_1| = |w_2|$ that induces a path from $q$ to an accepting state, which means that $w_1w_2 \in L$, and so $w_1 \in \operatorname{half}(L)$.
(source: this solution, a bit reformulated)
A language $L$ is said to be recursively enumerable if there exists a Turing Machine $M$ satisfying the following conditions:
-For every $\omega \in L$, simulating $M$ on $\omega$ (which we denote $M(\omega)$) results in $M$ halting and accepting $\omega$.
-For every $\omega \in \Sigma^{*} \setminus L$, $M$ does not accept $\omega$.
Note that for a recursively enumerable language, any TM accepting $L$ need not halt on inputs outside of the language.
If $L$ is decidable, there must exist some TM that halts on all inputs in addition to the conditions for $L$ being recursively enumerable.
What about languages that aren't recognizable?
No such decider or recognizer would exist. Consider the following language: $L_{NOT-HALT} = \{ \langle M_{i} \rangle, \omega_{i} : M_{i}$ is the $i$th TM and $\omega_{i}$ is the $i$th string in $\Sigma^{*}$ and $M_{i}$ does not halt on $\omega_{i} \}$.
The language $L_{NOT-HALT}$ is not recursively enumerable. No TM can accept every string in $M_{i}$. For some TMs in $L_{NOT-HALT}$, it may be possible to recognize an infinite loop by checking the states and transition function. However, there is no general procedure to do this for all TMs in $L_{NOT-HALT}$. A Cantor diagonal argument proves this. See the undecidability of the halting problem.
Does this clear things up?
Best Answer
Hint: Note that in order to check whether $u\in\text{half}({\mathscr L})$ the search space for the other 'half' $v$ is bounded in length.
Also, note the similarity between this and the relation between the complexity classes ${\mathsf P}$ and ${\mathsf N}{\mathsf P}$.