Original question and givens
Use the complete finite, possibly nondeterministic transition model S=Fin(6)={0,…,5}, Init=[0], Halt=[5], Step=[[0, 1], [1, 2], [2, 5], [3, 4], [4, 5], [2, 1]]. Normalize sets and ordered transition pairs. Execution stops at a declared Halt state, ignoring all of its outgoing edges. A stuck nonhalting state is not a successful halt; finite prefixes prove no general termination. Natural ranking vector=[20, 5, 4, 3, 2, 0]. Give (rank vector, reachable nonhalt Step edges failing strict decrease, ranking valid?, reachable stuck states, ranking valid and no stuck states?, actual all-path termination?).
G001 — Use the complete finite, possibly nondeterministic transition model S=Fin(6)={0,…,5}, Init=[0], Halt=[5], Step=[[0, 1], [1, 2], [2, 5], [3, 4], [4, 5], [2, 1]]. Normalize sets and ordered transition pairs. Execution stops at a declared Halt state, ignoring all of its outgoing edges. A stuck nonhalting state is not a successful halt; finite prefixes prove no general termination. Natural ranking vector=[20, 5, 4, 3, 2, 0]. Give (rank vector, reachable nonhalt Step edges failing strict decrease, ranking valid?, reachable stuck states, ranking valid and no stuck states?, actual all-path termination?).
Step-by-step derivation
S001 · implies
Before
n=6;raw Init=[0];raw Halt=[5];raw Step=[[0, 1], [1, 2], [2, 5], [3, 4], [4, 5], [2, 1]]
After
Init=[0];Halt=[5];canonical raw Step=[[0, 1], [1, 2], [2, 1], [2, 5], [3, 4], [4, 5]]
Conditions: none
Type the complete finite data and deduplicate directed edges.Retain raw outgoing halt edges as data,but execution stops at halt.Stuck is not successful halt,and one prefix proves no general program termination.
Step identifiers and dependencies
Rule: finite_transition_normalization · Uses: G001
S002 · implies
Before
Init=[0]
After
zero-step reachable=[0]
Conditions: none
Every initial state is reachable in zero steps,including an initial halt.An empty Init has no reachable states.
Step identifiers and dependencies
Rule: zero_step_reachability · Uses: G001, S001
S003 · implies
Before
depth=0;state=0;halt=No;raw successors=[1]
After
expanded successors=[1];newly reached=[1]
Conditions: none
Expand every successor of a nonhalt state,not just one chosen path.Add unseen states only.A halt is not expanded even when raw outgoing edges exist.
Step identifiers and dependencies
Rule: reachability_halt_truncates_expansion · Uses: G001, S002
S004 · implies
Before
completed frontier=[0];depth=0
After
next frontier=[1];all reached=[0, 1]
Conditions: none
The closure is complete only when the frontier empties.Finitely many states and adding only unseen states ensure enumeration terminates,without sampling a path-length cutoff.
Step identifiers and dependencies
Rule: complete_finite_reachability_layer · Uses: G001, S003
S005 · implies
Before
depth=1;state=1;halt=No;raw successors=[2]
After
expanded successors=[2];newly reached=[2]
Conditions: none
Expand every successor of a nonhalt state,not just one chosen path.Add unseen states only.A halt is not expanded even when raw outgoing edges exist.
Step identifiers and dependencies
Rule: reachability_halt_truncates_expansion · Uses: G001, S004
S006 · implies
Before
completed frontier=[1];depth=1
After
next frontier=[2];all reached=[0, 1, 2]
Conditions: none
The closure is complete only when the frontier empties.Finitely many states and adding only unseen states ensure enumeration terminates,without sampling a path-length cutoff.
Step identifiers and dependencies
Rule: complete_finite_reachability_layer · Uses: G001, S005
S007 · implies
Before
depth=2;state=2;halt=No;raw successors=[1, 5]
After
expanded successors=[1, 5];newly reached=[5]
Conditions: none
Expand every successor of a nonhalt state,not just one chosen path.Add unseen states only.A halt is not expanded even when raw outgoing edges exist.
Step identifiers and dependencies
Rule: reachability_halt_truncates_expansion · Uses: G001, S006
S008 · implies
Before
completed frontier=[2];depth=2
After
next frontier=[5];all reached=[0, 1, 2, 5]
Conditions: none
The closure is complete only when the frontier empties.Finitely many states and adding only unseen states ensure enumeration terminates,without sampling a path-length cutoff.
Step identifiers and dependencies
Rule: complete_finite_reachability_layer · Uses: G001, S007
S009 · implies
Before
depth=3;state=5;halt=Yes;raw successors=[]
After
expanded successors=[];newly reached=[]
Conditions: none
Expand every successor of a nonhalt state,not just one chosen path.Add unseen states only.A halt is not expanded even when raw outgoing edges exist.
Step identifiers and dependencies
Rule: reachability_halt_truncates_expansion · Uses: G001, S008
S010 · implies
Before
completed frontier=[5];depth=3
After
next frontier=[];all reached=[0, 1, 2, 5]
Conditions: none
The closure is complete only when the frontier empties.Finitely many states and adding only unseen states ensure enumeration terminates,without sampling a path-length cutoff.
Step identifiers and dependencies
Rule: complete_finite_reachability_layer · Uses: G001, S009
S011 · implies
Before
reached state=0;declared halt=No;raw successors=[1]
After
status=active-nonhalt
Conditions: none
The halt designation takes precedence.Only a nonhalt with no successor is stuck;one with successors is active.No outgoing edge does not automatically mean successful termination.
Step identifiers and dependencies
Rule: halt_stuck_active_are_distinct · Uses: G001, S010
S012 · implies
Before
reached state=1;declared halt=No;raw successors=[2]
After
status=active-nonhalt
Conditions: none
The halt designation takes precedence.Only a nonhalt with no successor is stuck;one with successors is active.No outgoing edge does not automatically mean successful termination.
Step identifiers and dependencies
Rule: halt_stuck_active_are_distinct · Uses: G001, S011
S013 · implies
Before
reached state=2;declared halt=No;raw successors=[1, 5]
After
status=active-nonhalt
Conditions: none
The halt designation takes precedence.Only a nonhalt with no successor is stuck;one with successors is active.No outgoing edge does not automatically mean successful termination.
Step identifiers and dependencies
Rule: halt_stuck_active_are_distinct · Uses: G001, S012
S014 · implies
Before
reached state=5;declared halt=Yes;raw successors=[]
After
status=halt
Conditions: none
The halt designation takes precedence.Only a nonhalt with no successor is stuck;one with successors is active.No outgoing edge does not automatically mean successful termination.
Step identifiers and dependencies
Rule: halt_stuck_active_are_distinct · Uses: G001, S013
S015 · implies
Before
natural rank vector=[20, 5, 4, 3, 2, 0];reachable=[0, 1, 2, 5];Halt=[5]
After
all active ranking edges=[[0, 1], [1, 2], [2, 1], [2, 5]]
Conditions: none
A natural ranking must strictly decrease on every reachable nonhalt outgoing edge,including edges into halt.Raw outgoing halt edges are not execution steps.
Step identifiers and dependencies
Rule: ranking_reachable_nonhalt_edge_scope · Uses: G001, S014
S016 · calculation
Before
rank decrease on edge0,1 := sub(20, 5)
After
rank decrease on edge0,1 = 15
Conditions: none
Subtract successor rank from predecessor rank;strict decrease requires a value>0.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S015
S017 · implies
Before
edge=[0, 1];ranks=[20, 5];difference=15
After
strictly decreasing=Yes
Conditions: none
Equality is not decrease.Retain every nondecreasing original edge,not just the first.
Step identifiers and dependencies
Rule: ranking_each_strict_decrease · Uses: G001, S016
S018 · calculation
Before
rank decrease on edge1,2 := sub(5, 4)
After
rank decrease on edge1,2 = 1
Conditions: none
Subtract successor rank from predecessor rank;strict decrease requires a value>0.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S017
S019 · implies
Before
edge=[1, 2];ranks=[5, 4];difference=1
After
strictly decreasing=Yes
Conditions: none
Equality is not decrease.Retain every nondecreasing original edge,not just the first.
Step identifiers and dependencies
Rule: ranking_each_strict_decrease · Uses: G001, S018
S020 · calculation
Before
rank decrease on edge2,1 := sub(4, 5)
After
rank decrease on edge2,1 = -1
Conditions: none
Subtract successor rank from predecessor rank;strict decrease requires a value>0.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S019
S021 · implies
Before
edge=[2, 1];ranks=[4, 5];difference=-1
After
strictly decreasing=No
Conditions: none
Equality is not decrease.Retain every nondecreasing original edge,not just the first.
Step identifiers and dependencies
Rule: ranking_each_strict_decrease · Uses: G001, S020
S022 · calculation
Before
rank decrease on edge2,5 := sub(4, 0)
After
rank decrease on edge2,5 = 4
Conditions: none
Subtract successor rank from predecessor rank;strict decrease requires a value>0.
Step identifiers and dependencies
Rule: exact_rational_arithmetic · Uses: G001, S021
S023 · implies
Before
edge=[2, 5];ranks=[4, 0];difference=4
After
strictly decreasing=Yes
Conditions: none
Equality is not decrease.Retain every nondecreasing original edge,not just the first.
Step identifiers and dependencies
Rule: ranking_each_strict_decrease · Uses: G001, S022
S024 · implies
Before
reachable=[0, 1, 2, 5];Halt=[5]
After
reachable nonhalt graph vertices=[0, 1, 2]
Conditions: none
Inspect cycles only in the reachable nonhalt subgraph.Unreachable cycles and outgoing halt edges do not affect this execution question.
Step identifiers and dependencies
Rule: reachable_nonhalt_cycle_scope · Uses: G001, S023
S025 · implies
Before
peeling layer=0;remaining=[0, 1, 2]
After
vertices with no remaining nonhalt successor=[]
Conditions: none
Repeatedly remove vertices with no remaining nonhalt successor.A directed cycle cannot be removed this way.Stuck vertices may be removed too,so keep the separate stuck check.
Step identifiers and dependencies
Rule: finite_cycle_sink_peeling · Uses: G001, S024
S026 · implies
Before
nonempty residual=[0, 1, 2];deterministic walk=[0, 1, 2, 1]
After
reachable nonhalt cycle=[1, 2, 1]
Conditions: none
Every residual vertex has a residual successor.Following the least successor in a finite set repeats a vertex and yields an actual cycle.A path can keep following this cycle,so an available halt exit does not make all paths halt.
Step identifiers and dependencies
Rule: explicit_reachable_cycle_witness · Uses: G001, S025
S027 · implies
Before
reachable stuck=[];reachable nonhalt cycle=Yes
After
all paths reach Halt=No
Conditions: none
In a finite model an infinite nonhalt path repeats a state and forms a cycle;a finite maximal nonhalting path ends stuck.Exclude both to ensure every path reaches Halt.Empty Init is vacuous;this does not establish termination of arbitrary infinite-state programs.
Step identifiers and dependencies
Rule: finite_all_paths_termination_joint_gate · Uses: G001, S026
S028 · implies
Before
ranking valid=No;reachable stuck=[]
After
ranking plus no stuck=No;actual all-path termination=No
Conditions: none
Strict natural descent excludes infinite execution,but stuck states must also be excluded to reach successful halt.A failed ranking candidate does not mean the model fails to terminate;actual termination is independently checked from the full finite graph.
Step identifiers and dependencies
Rule: ranking_candidate_not_actual_termination_identity · Uses: G001, S027