A is a set of all < M > that M is a TM halt on all input strings w such that w <= 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 M*.

M1 = “On input < M > where M is TM

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

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