Alphabeta Math
False statementConstruction: Literature-sourcedVerification: AI-generatedprecheck passaudited 2026-09-12
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.

FALSE: machine invariance means equivalent models perform exactly the same number of steps

Statement

False claim: whenever one translates a computation between standard machine models with the same computability power, the translated computation takes exactly the same number of steps.

Facts & Assumptions

Given: The false claim above.

[A1]

Whenever one translates a computation between standard machine models with the same computability power, the translated computation takes exactly the same number of steps.

[L1]

Polynomial-time and polynomial-space computation are model-invariant only up to asymptotic overhead, by Polynomial-time and polynomial-space computation are invariant across standard machine models.

[L2]

A one-tape machine is the k=1 case of the deterministic multitape model, whose transitions read, write, and move each tape head once per step (Multitape and nondeterministic Turing machine variants).

Refutation

technique · direct
1.1

Let M be a one-tape scanning machine, regarded by [L2] as a multitape machine with one tape. Translate it to an equivalent one-tape machine S by inserting, before every original transition, a two-step right-then-left excursion that changes no tape symbol and records the finitely many encountered symbols in the control state. The third step performs the original transition. Thus S has exactly the same behavior as M but uses three steps for every nonhalting step of M.

L2givenconstruct
2.1

On every input for which M takes a positive number of steps, the translated computation takes three times as many, contradicting [A1]. This is consistent with [L1]: robustness preserves asymptotic complexity classes, not literal equality of running times.

A1L1step 1.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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