Accepting and Rejecting States
What you'll learn: How Turing machines use special halting states to definitively accept or reject input strings.
The Need for Decision States
When a Turing machine processes input, it must eventually communicate its verdict: Does this input belong to the language or not? Just like a judge must render a final decision, a Turing machine needs a clear way to signal its conclusion.
Two Special Halting States
A Turing machine designates two special states that cause the machine to halt (stop executing):
The Accept State (q_accept)
When the machine enters this state, it immediately halts and accepts the input string. This means "Yes, this string belongs to the language I recognize."
The Reject State (q_reject)
When the machine enters this state, it immediately halts and rejects the input string. This means "No, this string does not belong to my language."
How They Work
Think of these states like exit doors in a building:
- The accept state is the "Success Exit" — reaching it means you've completed the task correctly
- The reject state is the "Failure Exit" — reaching it means the input failed the test
Once the machine enters either state, computation stops. No further transitions occur. The machine has made its decision.
Why We Need Both
You might wonder: why have a dedicated reject state? Couldn't we just say "anything that doesn't accept is rejected"? Having an explicit reject state allows the machine to actively reject input, which is crucial for recognizing when an input definitely fails, rather than just running forever without deciding.
Key Takeaway: Accept and reject states are special halting states that allow a Turing machine to make definitive decisions about whether an input string belongs to its language.