The Undecidable Turn

A pushdown automaton’s computation alternates between pushing onto and popping from its stack. Each switch from pushing to popping is a turn. Some languages can be accepted with a bounded number of turns — the stack goes up and down a fixed number of times regardless of input length. Others require turns that grow with the input.

Whether the number of turns is bounded by any constant is undecidable. There is no algorithm that, given a pushdown automaton, determines whether it can accept all its strings with at most k turns for some fixed k. The finiteness of the bound — not its value — is the undecidable question.

Between constant turns and linear turns lies an infinite hierarchy. Languages exist requiring sublinear but non-constant numbers of turns, and within the sublinear regime, the hierarchy doesn’t collapse: for every sublinear growth rate, there are languages requiring exactly that many turns and no fewer. The structure is richer than the binary “bounded or unbounded.”

The through-claim: turn complexity measures a fundamentally different resource from time or space. Time and space ask how much computation is needed. Turn complexity asks about the shape of computation — how many times the automaton’s relationship with its memory reverses direction. The undecidability of the bounded question means that this structural property of computation cannot be detected by any computable procedure, even though individual turn counts can be computed. The shape of computation is harder to characterize than its cost.