# Showing that a language is not recursive

I was given the next function CH(x) that is defined like this:

$CH(<M>)$ outputs the computation history of the run of M on epsilon if M halts on epsilon. If it doesn't the function returns epsilon. I was asked to prove that the language

{$M, CH(<M>) |$ M is a turing machine } is in co-RE\R

I can't seem to understand why the language isn't recursive enumerable I do see why it's not in R (The halting problem becomes decidable)

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.