I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the first non-recursive language.

I have 2 languages I would like to show it for. These are:

  1. $L_{AC}$ - the pairs $\left<M,w\right>$ such that $M$ accepts $w$.
  2. $L_{HL}$ - the pairs $\left<M,w\right>$ such that $M$ halts on $w$ (doesn't go into a non-ending loop).

Its obvious both are in $RE$, simply simulate them by using a universal TM. But apart from a logical argument, I'm not sure how to approach this, considering I do not allow reductions (more as, I am trying to discover the first language or two in $R$, so its as if I don't have any previous knowledge on $R$).

  • 1
    $\begingroup$ Are you familiar with the usual proof that the halting problem is not recursive? Try replicating it. $\endgroup$ Commented May 8, 2022 at 13:06
  • $\begingroup$ Hi, actually I am not. Do you have a source? $\endgroup$ Commented May 8, 2022 at 16:12
  • $\begingroup$ There are many sources on the web, including Wikipedia. $\endgroup$ Commented May 8, 2022 at 17:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.