Is this set semi-decidable? A set of all <M> that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M

Question

$A$ is a set of all $\langle M \rangle$ that $M$ is a TM halting on all input strings $w$ such that $\lvert w \rvert \le q(M)$ where $q(M)$ is the number of states in $M$.

Is $A$ semi-decidable? Is a complement of $A$ semidecidable?

I think $A$ is semi-decidable. We can construct $M1$.

$M1$ = "On input $\langle M \rangle$ where $M$ is a TM

Simulate $M$ on input with all of the string whose length is less than $q(M)$. If it halts for all, accept"

The complement of $A$ is not semi-decidable. But I'm not sure how to prove it.

Answer 1

To show that $\overline{A}\notin RE$ you want to show that another language $B\notin RE$ is reducible to it.

First, the complement of $A$ is the set of all $\left< M \right>$, where $M$ is a Turing machine, and $\exists w$, $|w|<q(M)$ s.t. $M$ doesn't halt on $w$.

Remember that you can add unreachable states to a Turing machine, therefore increasing $q(M)$. The next step would be picking a language who is known to be not decidable (e.g. the complementary of the halting language $\overline{H}$), and think of a reduction to $\overline{A}$.

Answer 2

The logical idea is take $M, w$ for the halting problem (here in the sense halt is accepting), and manufacture $M'$ that only accepts $w$, and has more than $\lvert w \rvert$ states, if $M$ accepts $w$.... but that is easy, just checking that the input is $w$ takes that many states. If we could decide if $M'$ accepts any string of length at most its number of states, we'd be deciding the halting problem.