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
