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.
-
Welcome to Stack Overflow. Please take the tour to learn how Stack Overflow works and read How to Ask on how to improve the quality of your question. Then check the help center to see which questions are on-topic on this site. You might want to delete this question and ask it on cs.stackexchange.com instead, but check the help pages there first.Progman– Progman2022年03月25日 21:57:03 +00:00Commented Mar 25, 2022 at 21:57
1 Answer 1
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.