Abstract computational model
On this page
This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.
A finite-state computational model describes possible executions through its state set, initial-state set, step relation and halt-state set.
mko-computational-model · definition · v0.10.0
Mathematical statement
The finite abstract model in this entry is (S,Init,Step,Halt), with Init,Halt⊆S and Step⊆S×S. Executions start in Init and follow Step; a stuck state without successors is not automatically a member of Halt.
Representative formula (exact TeX)
R\subseteq S
Assumptions
- S is an explicitly given finite set, and Step is a directed relation that may be nondeterministic.
- Reaching Halt stops execution: truncate all outgoing edges from halts before analysis, even if the raw data contains them.
Symbol scope
R— step relationS— state set
Intuition, definition, and misconceptions
Reachability begins at every initial state and follows zero or more permitted steps, with the declared halt truncation.
A legal trace starts in Init and has adjacent states related by Step. Once it enters Halt, that execution ends and cannot continue.
Failure to see a cycle at finite exploration depth does not prove that all executions terminate. A reachable nonhalting cycle or reachable stuck nonhalt is a termination risk.
A state with no outgoing edge is not automatically a halt, and a finite execution prefix does not establish all-path termination.
Adopted derivation guide
Abstract computational model: truncating halt edges, computing reachability and separating halting, stuck and non-terminating runs in a seven-state modelThe original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.
Prerequisites
- Set — State, initial and halt conditions are represented by sets.
- Binary relations and set projections — Step semantics is a directed relation between states.
- Natural number — Natural numbers index finite trace lengths and step counts.
Verification boundary
The entire reachable structure of a finite state graph can be enumerated; this implies no unspecified Turing completeness or behavior of a real program.
not_formalized
This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.
Next obligation
Develop layered deterministic/nondeterministic, stuck-state, maximal-execution and effective-encoding models.
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.
Canonical MKO JSON · Plain Markdown