Proof of `The deterministic time hierarchy theorem for exponential time`
groundedproofs/Lax119563Proofs/Hierarchy/ExpMain.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
A diagonal argument. The diagonal machine computes a clock of units on inputs of length by doubling a unary counter times (in time ), and runs the universal stack program under this clock; the universal program answers the negation of the machine whose code is a prefix of the input. So the diagonal language is in . The universal program has cubic overhead: simulating steps on inputs of length costs (with a constant depending on the simulated machine). A machine running within steps is thus simulated within steps on long inputs , where the diagonal machine answers differently.