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.