Showing that a language is not recursive

In order to prove $L \in coRE$ you could prove that $\overline{L} = \{\langle M,w \rangle | M \text{ is a TM and } w \neq CH\left( \langle M \rangle \right) \}$ is r.e.

Given input $\langle M,w \rangle$

• reject if input is not well-formed including $\epsilon$

• if $w \neq \epsilon$. Then $w$ must be a history. If it is not a legal history, just accept since $CH(\langle M \rangle) \neq w$. Otherwise inspect the history, and assume it runs for $k$ steps. Then simulate $M$ for $k$ steps and compare its history with $w$. If they are NOT equal then accept, otherwise reject/loop forever.

• if $w = \epsilon$. Then run $M$ until it halts. If it halts then accept since $CH(M)$ must be a legal history different from $\epsilon$ which means $CH(\langle M \rangle) \neq w = \epsilon$. Otherwise, i.e. $M$ does not halt. But our TM which simulates $M$ also runs forever which means that $CH(M) = \epsilon = w$, but it will never halt and so never accept.

Note that $M$ diverges on $\epsilon$ iff $\langle M, \epsilon \rangle$ belongs to your language. This provides a reduction from a non RE problem to yours.