The difference between halting and accepting in a Turing machine

1.4k Views Asked by At

I use the textbook "an introduction to formal languages and automata", 6th edition by Peter Linz.

In Definition 11.2, it seems that a Turing machine "M accepts language L" and "M halts on string w" are different things? I mean, why does the author specifically distinguish these two concepts?

But if we check Definition 9.3, it says that if M accepts L then it eventually reaches a final state qf. For a final state, my understanding is that it means M halts on w, right? In this regard, aren't accepting and halting the same idea?

Are accepting and halting different concepts? Or is there an example that it arrives in qf but does not halt? Thanks.

enter image description here

enter image description here

1

There are 1 best solutions below

0
On

Halting and accepting in Turing Machine are different. Acceptance in Turing Machine means the machine halts in an accept state, which means the machine terminates. In contrast, halting can happen in any states of the machine because there is no proper input symbol in the input string to follow any transition.