ChatDiagram
COMPUTABILITY THEORY

Turing machine for a to the n b to the n

This Turing machine recognizes strings formed by n copies of a followed by n copies of b. It repeatedly finds the leftmost unmarked a, changes it to X, moves right to find an unmarked b and changes that symbol to Y. It then returns left to begin the next pair. Once no a remains, qCheck scans the marked b symbols and accepts only when it reaches the blank at the end of the tape. The X and Y markers are the machine's working memory: they let it remember which symbols have already been paired. This is a standard example of why Turing machines can recognize languages that finite automata cannot.

UPDATED 2026-09-24
TYPEState
EXAMPLETuring machine for a to the n b to the n
Make this diagram your own.

Open it in the AI editor with a prompt pre-filled — keep what works, change what doesn't.

CASE ANALYSIS

Scenario

Matching equal-length blocks

Key decisions

  • First marker: qFindA selects one unmarked a at a time.
  • Paired marker: qFindB changes one corresponding b to Y.
  • Completion check: qCheck accepts only after the remaining b block has all been marked.

When to reuse this

Use a marking-and-return machine to recognize a non-regular language that requires matching counts.

FAQ

Frequently asked questions

What language is being recognized?01
Strings with the same number of a symbols followed by b symbols, such as ab, aabb and aaabbb.
Why are X and Y needed?02
They mark symbols already paired, preventing the machine from counting the same a or b twice.
Why is this not a finite automaton task?03
The machine must compare an unbounded number of a and b symbols, which requires more memory than finite states provide.
Open this example in the editor →

Tweak it with chat, export PNG/SVG, or fork it for your own use case.