1
$\begingroup$

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)

$\endgroup$
1
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.