0

I have the following language:

$$ L=\{ \langle M, n \rangle \mid \forall x\in \Sigma^*\ s.t\ |x|=n, M\ doesn't\ reject\ x\} $$

Where $M$ is a TM with finite $\Sigma$ and $\Gamma$.

I think that $L$ is not in $RE$, but I don't know how to prove it. I am thinking about reduction from $\overline{HP}$, but not sure if this is the right way and if it is, then how to do the reduction.

Daniel
  • 558

1 Answers1

0

I'll assume that $M$ is intended to be a Turing machine (as opposed to, for example, just a finite state automaton). I'll also assume that "$M$ rejects $x$" means that when $M$ runs on input $x$, it enters a rejecting state (as opposed to meaning, for example, just that $M$ doesn't accept $x$). Finally, I'll assume that $\Sigma$ is a finite alphabet.

Under these assumptions your set is r.e. A semi-decision algorithm works as follows: On input $\langle M,n\rangle$, it operates parallel (interleaved) runs of $M$ on all the finitely many inputs $x$ of length $n$. If and when all these runs have rejected, then the algorithm accepts $\langle M,n\rangle$.

Andreas Blass
  • 71,833
  • If, on the other hand, "rejects" means only "doesn't accept", then your set is not r.e.; it's a complete co-r.e. set. – Andreas Blass Jul 25 '21 at 14:12
  • The assumptions are true, but I mistakenly wrote $M\ rejects\ x$ instead of $M\ doesn't\ reject\ x$ ($M$ should accept $x$ or never stop running on input $x$). That's why I thought about reduction from $\overline{HP}$. – Daniel Jul 25 '21 at 14:27
  • @Daniel The situation with "doesn't reject" is the same as with "doesn't accept", since one can easily modify a Turing machine by interchanging acceptance and rejection. So your "doesn't reject" set is complete co-r.e., and there is indeed a reduction from the complement of the halting problem. – Andreas Blass Jul 25 '21 at 18:15