0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Aug 28, 2022 at 17:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – Andrej Bauer
    Aug 31, 2022 at 7:56
  • $\begingroup$ @AndrejBauer Thank you, so my problem is actually undecidable. $\endgroup$
    – Ronald
    Aug 31, 2022 at 10:04

1 Answer 1

Reset to default
2
$\begingroup$

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.

But determining whether or not your Turing machine ever reaches these states is another question overall. It is generally impossible to know whether or not a Turing machine will halt beforehand. So if you could count the number of ways that a Turing machine will halt (not could halt), you are basically raising a serious contradiction with the halting problem.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the answer. I do however not really get why the set of final states for 𝑀′ (from a totally different machine than M) in combination with 𝐹 could be of any use? I am interested in the states of M where we can possibly end up after reading a word, even though that state is maybe not a final state. $\endgroup$
    – Ronald
    Aug 30, 2022 at 18:33
  • $\begingroup$ @Ronald Well, the machine can halt at any state given the input. If it halts at all. $\endgroup$
    – ARK1375
    Aug 30, 2022 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.