Abstract computational model

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 relation
• S — 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

The 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.