Return to 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 $M^*$.

$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.

$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.

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

$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 $M^*$.

$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.

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 can I prove it

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