Proof of `The deterministic time hierarchy theorem`
groundedproofs/Lax119563Proofs/Hierarchy/Main.lean · lax-119563
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
The proof uses translation (padding) to reduce the claim to a coarse hierarchy: is not contained in . The coarse hierarchy follows from a diagonal argument. A universal stack program simulates the machine whose code is a prefix of the input, with polynomial overhead, under a clock of steps. The case is handled directly: a machine running in time cannot read the last input bit.