Turing-machine decision model

Mathematical statement

Specify finite states, input/tape alphabets, blank, start, accept, reject and deterministic transitions [state,read,next,write,move]. Unlisted tape cells are blank, and configurations are [state,head,sparse nonblank tape]. Exact steps and finite traces concern their supplied input only. A global decider certificate needs an all-input strictly decreasing ranking or explicit step bound and answer correctness. A recognizer may loop on nonmembers. Bounded simulation failure proves neither rejection nor nontermination, and one halting trace does not certify a global decider.

Representative formula (exact TeX)

T(M,w)=h

Assumptions

• Moves are L/R/S, and accept/reject states have no outgoing transitions.
• The global positive family uses the exact scan-decider schema with ranking unscanned input cells plus1.

Symbol scope

• T — Turing execution record
• M — deterministic single-tape machine
• w — input word
• h — halting outcome

Intuition, definition, and misconceptions

Signature qualification and execution semantics are separate.

A finite trace is input-local evidence.

A decider needs global termination and answer-correctness certificates.

One halting trace or a finite budget without halting does not show that the whole machine is a decider or that the input is rejected.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Abstract computational model — Use finite control and explicit step semantics.
• Decision problem — Answers have a yes/no meaning.
• Deterministic finite automaton — Finite-state control supplies background.
• Algorithm correctness — Deciders need total correctness.

Verification boundary

This slice claims no formal Church-Turing-thesis proof, general complexity bound or multitape equivalence.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add many-one reductions, undecidability and complexity.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.