computation theory - Prove whether this language is decidable or undecidable -

so reviewing notes problem, , cant seem understand how problem works. have m, , m accepts input makes visit every non-halting state.

i convinced myself problem decidable, having trouble proving so. rough outline of answer : assume have tm t has 1 halting state, , if wants go through states needs pass through halt state , somehow need show how cycle through states such.

any beneficial, thanks!

i think you'll find answer it's undecidable. why? let solve halting problem.

you given tm m , input x , oracle q problem describe. can solve halting problem m input x using oracle q?

first, connect new tm n front of m. here's n does: - deletes tape contents - writes x onto tape

m halts on x iff nm halts on inputs. should easy see since n leaves tape m have seen if input had been x. can design n in such way states of n visited.

now, modify m m' adding second tape. second tape used keep track of highest-numbered state of m' have visited. add transitions m' read nth state secondary tape , cause m' transition (n+1)st state. transition highest-numbered state of m' should return initial state of m' , write "finished" on secondary tape. when m' sees "finished" on secondary tape, behaves m did , considers primary tape.

so m' m' does, except first visits states of m , resets after behaves m.

m' halts on x iff m halts on x. nm' halts iff m halts on x.

finally we're ready proof. oracle q accepts nm' iff m halts on x. q accepts nm' if nm' accepts input y causes nm' visit states. but: - inputs y cause nm' visit states (since states of n visited construction, , states of m' visited modification of m); q answering question "does nm' accept strings?" - nm' erases y input tape, writes x , hands off m'. input y doesn't matter; if nm' accepts input, accepts of them. , accepts of them if m' accepts x. - m' accepts same language m.

so q applied nm' indeed tell if m halts on x. q solves halting problem.