0

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

asked Mar 25, 2022 at 21:34
1
  • 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. Commented Mar 25, 2022 at 21:57

1 Answer 1

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.

answered Mar 29, 2022 at 4:35
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.