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