2
$\begingroup$

I tried to prove that the following language is recursive/decidable/in R: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_\text{TM,epsilon}\cap \Sigma^k $$ where $H_\text{TM,epsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on epsilon input}\}$

It is easy to prove because $L_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it. I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject. I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L_k$ being finite)?

$\endgroup$

merged by Raphael Jul 17 '15 at 5:52

This question was merged with Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup because it is an exact duplicate of that question.