$$L =\left \{ \langle M \rangle \mid \exists x\in \Sigma^* \left(\left | x \right |\leq 10000 \wedge H(M, x\right) \right \}$$

Where $H(M, x)$ denotes whether Turing machine $M$ halts on input $x$.

My guess is neither $R$ or $Re$ because I would have to run infinite TM's in order to find out if every TM halts on x or is not halting on x. Is my intuition correct?


The language is in RE: simply generate all inputs $x$ with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs in parallel. Whenever one simulation halts, accept.

The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem. Indeed, to decide whether a Turing machine $T$ halts on empty input, we could create a new machine $M$ that simulates $T$ if $x=\varepsilon$ and does not halt otherwise. Then $M \in L$ if an only if $T(\varepsilon)$ halts.


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.