ExampleConstruction: AI-generatedVerification: 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.

Replacing a stay-put transition by a right-left macro

Example

Consider the one-tape machine with tape alphabet ${0, 1, ⊔}$ and one transition $δ (q_{0}, 1) = (q_{1}, 0, S) .$ On a configuration whose scanned cell contains 1, this machine writes 0, enters state $q_{1}$ , and leaves the head on that same tape cell.

Introduce a fresh state $r$ and replace that transition by $δ^{'} (q_{0}, 1) = (r, 0, R), δ^{'} (r, a) = (q_{1}, a, L) for every a \in {0, 1, ⊔} .$

Facts & Assumptions

Given: The source transition and the replacement macro displayed above.

[L1]

Stay-put moves can be replaced by an equivalent machine using only left and right moves, by Stay-put moves can be eliminated from fixed-tape Turing-machine models.

[L2]

A configuration records the current state, head position, and tape contents, so two machines agree on one next configuration exactly when those three pieces of data agree, by Configurations of a deterministic one-tape Turing machine.

Verification

technique · direct

1.1

Let $C = (q_{0}, h, t)$ be any configuration with $t (h) = 1$ . The original transition sends $C$ in one step to the configuration $(q_{1}, h, t^{'})$ , where $t^{'}$ agrees with $t$ away from $h$ and satisfies $t^{'} (h) = 0$ .

given

2.1

Under the replacement macro, the first step writes 0 at cell $h$ and moves the head to $h + 1$ , entering state $r$ . The second step leaves the symbol at cell $h + 1$ unchanged, moves the head back to $h$ , and enters state $q_{1}$ . So after the two-step macro the transformed machine is also in configuration $(q_{1}, h, t^{'})$ .

givenstep 1.1

3.1

Thus the concrete macro produces exactly the same next configuration as the stay-put transition. This is the local pattern asserted abstractly by [L1], and [L2] explains why matching state, head position, and tape contents is enough.

L1L2step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 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

Charles Brubaker and Lance Fortnow, Church-Turing Thesis lesson notes (standard reference, not scraped)