Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedverified 2026-09-26 (gpt-6-sol)
How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

  • Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
  • AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
  • AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A constructible time bound yields a uniformly clocked simulator

Statement

Let t:N→N be time-constructible, and assume n≤t(n) for all sufficiently large n. Then for every coded deterministic machine e=⌜M⌝ there exists a deterministic machine Clock⁡e,t such that, on each input x:

  • if M halts within at most t(∣x∣) steps, then Clock⁡e,t halts with the same output;
  • if M has not halted by time t(∣x∣), then Clock⁡e,t halts and rejects.

Facts & Assumptions

Given: A time-constructible function t and a coded deterministic machine e=⌜M⌝.

[L1]

Time-constructibility means that a machine can compute the binary numeral of t(n) within O(t(n)) time on input 1n, by Time-constructible and space-constructible functions.

[L2]

A universal simulator reproduces the halting outputs and divergence of the coded machine on the coded input, by A universal Turing machine relative to a fixed machine encoding.

[L3]

The machine code e is an effective binary description of M, by A fixed effective binary encoding of deterministic one-tape Turing machines.

[L4]

Any machine that must fully read an input of length n needs at least linear time, by Any machine that fully reads every input of length n needs at least linear time.

Proof

technique · direct
1.1L1L4givenconstruct

On input x, the machine Clock⁡e,t first scans the whole input once to learn ∣x∣. The lower bound hypothesis n≤t(n) together with [L4] ensures that this preliminary scan fits inside the intended asymptotic budget. It then runs the constructor from [L1] on unary input 1∣x∣ to obtain the binary numeral of t(∣x∣) and writes a counter of that size on a work tape.

2.1L2L3step 1.1construct

Next, using the fixed code e from [L3], the machine initializes the simulated configuration of M on x. It first checks whether that configuration is already halting. Otherwise, while the counter is positive it simulates one transition, decrements the counter, and checks whether the new configuration is halting. If so, it outputs exactly what M outputs, including when this was the t(∣x∣)-th transition. If the counter is zero and the simulated configuration is still nonhalting, it rejects. This is the standard clocked simulation built from the effective transition table [L3] and universal behavior in [L2].

3.1step 2.1∎

Step 2.1 proves the two clauses of the statement: runs of M halting in at most t(∣x∣) transitions are preserved, and overlong runs are cut off by a halting reject state.

Depends on

Used by

Dependency tree · two levels

10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources