# How to recognize all halting states of a turing machine?

Given a turing machine with some states, how can I recognize all halting states of that machine?

I think that I should go over each state and check if there is a transition that is not defined for that state with one (or more) of the tape alphabet symbols (also containing the blank symbol).

Would this be a good approach?

• Halting states are defined as such in the definition of the Turing machine. See (here)[en.wikipedia.org/wiki/Turing_machine#Formal_definition] for the formal definition. Commented Aug 28, 2022 at 17:59
• @Ronald: It's undecidable whether for a given machine $M$ and a state $s$ there is an input for which $M$ will reach $s$ (halting or not, it doesn't matter). Also, there is some confusion with terminology here, because sometimes the "halting state" are defined to be a set of states, such that if the machine reaches one of them, it immediately halts – by design. Commented Aug 31, 2022 at 7:56
• @AndrejBauer Thank you, so my problem is actually undecidable. Commented Aug 31, 2022 at 10:04

A turing machine is defined as a 7-tuple $$M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$$. The set $$F$$ in the tuple is the set of final states or accepting states. So any other states other than the ones in $$F$$ are the rejecting states. You can consider the language that $$M$$ covers as $$L$$. So $$L'$$ will be the language (set of phrases) that $$M$$ never accepts. If you create another Turing machine $$M'$$ for $$L'$$, then the set of final states for $$M'$$ in combination with $$F$$ is the answer you are looking for.