Skip to content

Automata and Turing machines

O(n²)·O(n)

Being read

The machine starts in state start, with the head at the first symbol of 1001.

The machine starts in state start, with the head at the first symbol of 1001.

Playback speed

1Look at the leftmost unmarked symbol: it is a 0, so mark it and remember 0.
2Look at the leftmost unmarked symbol: it is a 1, so mark it and remember 1.
3The leftmost symbol is already marked 0 — skip over it.
4The leftmost symbol is already marked 1 — skip over it.
5No unmarked symbols remain: every pair matched, so accept.
6Scan right, past an unmarked 0, looking for the rightmost unmarked symbol.
7Scan right, past an unmarked 1, looking for the rightmost unmarked symbol.
8Found the right edge: the symbol just left of it, already marked 0, is the rightmost unmarked one — step onto it.
9Found the right edge: the symbol just left of it, already marked 1, is the rightmost unmarked one — step onto it.
10Reached the blank past the end: step back left onto the rightmost unmarked symbol.
11Scan right, past an unmarked 0, looking for the rightmost unmarked symbol.
12Scan right, past an unmarked 1, looking for the rightmost unmarked symbol.
13Found the right edge: the symbol just left of it, already marked 0, is the rightmost unmarked one — step onto it.
14Found the right edge: the symbol just left of it, already marked 1, is the rightmost unmarked one — step onto it.
15Reached the blank past the end: step back left onto the rightmost unmarked symbol.
16The rightmost unmarked symbol is a 0, matching the remembered 0: mark it and scan left to repeat.
17The rightmost unmarked symbol is a 1, but the remembered symbol was 0: reject.
18Only one unmarked symbol remained and it is already marked 0 (the odd-length middle): accept.
19Only one unmarked symbol remained and it is already marked 1 (the odd-length middle): accept.
20The rightmost unmarked symbol is a 1, matching the remembered 1: mark it and scan left to repeat.
21The rightmost unmarked symbol is a 0, but the remembered symbol was 1: reject.
22Only one unmarked symbol remained and it is already marked 0 (the odd-length middle): accept.
23Only one unmarked symbol remained and it is already marked 1 (the odd-length middle): accept.
24Scan left, past an unmarked 0, back toward the start.
25Scan left, past an unmarked 1, back toward the start.
26Scan left, past a symbol already marked 0, back toward the start.
27Scan left, past a symbol already marked 1, back toward the start.
28Reached the start: step back onto the leftmost symbol and look for the next unmarked one.

Steps taken: 0
Symbols marked: 0

Complexity

BestO(n)

AverageO(n²)

WorstO(n²)

Extra spaceO(n)

n² at n=4 predicts 16; this run took 0.

Binary palindrome checker

A Turing machine using the standard mark-and-compare technique: repeatedly mark the leftmost unmarked symbol, scan right to find the rightmost unmarked symbol, compare the two (rejecting the instant they differ), mark the second one too if they match, then scan back left past everything already marked and repeat — until no unmarked symbols remain, which means every pair matched.

When it is the right choice

As the second machine on this tool, immediately after the binary incrementer, because it is noticeably bigger for a noticeably harder kind of task: deciding whether a whole string has a property, rather than computing one new tape from an old one.

How it works

Look at the leftmost unmarked symbol. If none remains, every pair matched: accept.
Mark that symbol (0 becomes X, 1 becomes Y) and remember which it was.
Scan right past the remaining unmarked symbols to find the rightmost one.
Step back onto that rightmost unmarked symbol.
Compare it with the remembered symbol. If they differ, reject immediately.
If they match, mark it too.
Scan back left, past everything already marked, to the leftmost unmarked symbol, and repeat.

Worth noticing

The head genuinely oscillates — right, left, right, left — once per pass, and the number of passes grows with the input length. That is the mechanical reason this machine’s cost is roughly the square of the input length, where the incrementer’s is linear in it.
The reject scenario stops the instant it finds a mismatch, part way through its very first pass — it does not run every pass to completion just because it can.
Eight states and 28 rules against the incrementer’s three and six is the lesson: a slightly harder task costs noticeably more machine, and the cost is visible and countable here rather than asserted.

Cost

Best: O(n)
Average: O(n²)
Worst: O(n²)
Space: O(n)

Worth comparing

All automata and Turing machines