# Question 9569: Ranking Decrease, Stuck States, and Actual Termination [Return to catalogue page 48](https://ocme.evemisslab.com/en/questions/page/48/) [← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261013-advance-20261019-r05-algorithm-correctness-foundations/#q-20261013-advance-20261019-r05-algorithm-correctness-0069) This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth. R0018-09569 · q-20261013-advance-20261019-r05-algorithm-correctness-0069 ## 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], [1, 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=[24, 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], [1, 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=[24, 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?). ## Definition and scope Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate. - [mko-algorithm-correctness](https://ocme.evemisslab.com/en/mko/mko-algorithm-correctness/) ## Step-by-step derivation S001 · impliesBefore n=6;raw Init=[0];raw Halt=[5];raw Step=[[0, 1], [1, 2], [2, 5], [3, 4], [1, 1]] After Init=[0];Halt=[5];canonical raw Step=[[0, 1], [1, 1], [1, 2], [2, 5], [3, 4]] 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 dependenciesRule: finite_transition_normalization · Uses: G001 S002 · impliesBefore 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 dependenciesRule: zero_step_reachability · Uses: G001, S001 S003 · impliesBefore 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 dependenciesRule: reachability_halt_truncates_expansion · Uses: G001, S002 S004 · impliesBefore 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 dependenciesRule: complete_finite_reachability_layer · Uses: G001, S003 S005 · impliesBefore depth=1;state=1;halt=No;raw successors=[1, 2] After expanded successors=[1, 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 dependenciesRule: reachability_halt_truncates_expansion · Uses: G001, S004 S006 · impliesBefore 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 dependenciesRule: complete_finite_reachability_layer · Uses: G001, S005 S007 · impliesBefore depth=2;state=2;halt=No;raw successors=[5] After expanded successors=[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 dependenciesRule: reachability_halt_truncates_expansion · Uses: G001, S006 S008 · impliesBefore 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 dependenciesRule: complete_finite_reachability_layer · Uses: G001, S007 S009 · impliesBefore 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 dependenciesRule: reachability_halt_truncates_expansion · Uses: G001, S008 S010 · impliesBefore 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 dependenciesRule: complete_finite_reachability_layer · Uses: G001, S009 S011 · impliesBefore 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 dependenciesRule: halt_stuck_active_are_distinct · Uses: G001, S010 S012 · impliesBefore reached state=1;declared halt=No;raw successors=[1, 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 dependenciesRule: halt_stuck_active_are_distinct · Uses: G001, S011 S013 · impliesBefore reached state=2;declared halt=No;raw successors=[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 dependenciesRule: halt_stuck_active_are_distinct · Uses: G001, S012 S014 · impliesBefore 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 dependenciesRule: halt_stuck_active_are_distinct · Uses: G001, S013 S015 · impliesBefore natural rank vector=[24, 5, 4, 3, 2, 0];reachable=[0, 1, 2, 5];Halt=[5] After all active ranking edges=[[0, 1], [1, 1], [1, 2], [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 dependenciesRule: ranking_reachable_nonhalt_edge_scope · Uses: G001, S014 S016 · calculationBefore rank decrease on edge0,1 := sub(24, 5) After rank decrease on edge0,1 = 19 Conditions: none Subtract successor rank from predecessor rank;strict decrease requires a value>0. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S015 S017 · impliesBefore edge=[0, 1];ranks=[24, 5];difference=19 After strictly decreasing=Yes Conditions: none Equality is not decrease.Retain every nondecreasing original edge,not just the first. Step identifiers and dependenciesRule: ranking_each_strict_decrease · Uses: G001, S016 S018 · calculationBefore rank decrease on edge1,1 := sub(5, 5) After rank decrease on edge1,1 = 0 Conditions: none Subtract successor rank from predecessor rank;strict decrease requires a value>0. Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S017 S019 · impliesBefore edge=[1, 1];ranks=[5, 5];difference=0 After strictly decreasing=No Conditions: none Equality is not decrease.Retain every nondecreasing original edge,not just the first. Step identifiers and dependenciesRule: ranking_each_strict_decrease · Uses: G001, S018 S020 · calculationBefore 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 dependenciesRule: exact_rational_arithmetic · Uses: G001, S019 S021 · impliesBefore 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 dependenciesRule: ranking_each_strict_decrease · Uses: G001, S020 S022 · calculationBefore 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 dependenciesRule: exact_rational_arithmetic · Uses: G001, S021 S023 · impliesBefore 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 dependenciesRule: ranking_each_strict_decrease · Uses: G001, S022 S024 · impliesBefore 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 dependenciesRule: reachable_nonhalt_cycle_scope · Uses: G001, S023 S025 · impliesBefore peeling layer=0;remaining=[0, 1, 2] After vertices with no remaining nonhalt successor=[2] 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 dependenciesRule: finite_cycle_sink_peeling · Uses: G001, S024 S026 · impliesBefore peeling layer=1;remaining=[0, 1] 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 dependenciesRule: finite_cycle_sink_peeling · Uses: G001, S025 S027 · impliesBefore nonempty residual=[0, 1];deterministic walk=[0, 1, 1] After reachable nonhalt cycle=[1, 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 dependenciesRule: explicit_reachable_cycle_witness · Uses: G001, S026 S028 · impliesBefore 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 dependenciesRule: finite_all_paths_termination_joint_gate · Uses: G001, S027 S029 · impliesBefore 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 dependenciesRule: ranking_candidate_not_actual_termination_identity · Uses: G001, S028 ## Reverse checks - S029 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S028 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S027 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S026 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S025 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S024 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S023 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S022 · premise_and_result_audit — Recompute rank decrease on edge2,5 with exact rational arithmetic, not rounded decimals. - S021 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S020 · premise_and_result_audit — Recompute rank decrease on edge1,2 with exact rational arithmetic, not rounded decimals. - S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S018 · premise_and_result_audit — Recompute rank decrease on edge1,1 with exact rational arithmetic, not rounded decimals. - S017 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S016 · premise_and_result_audit — Recompute rank decrease on edge0,1 with exact rational arithmetic, not rounded decimals. - S015 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S013 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S009 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S007 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S005 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S003 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. - S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence. ## Result ([24, 5, 4, 3, 2, 0], [[1, 1]], No, [], No, No) The full substitutions and premise checks give the original answer; source identity,format and status are unchanged. ## This question review and source binding Review date: 2026-10-26 Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof. Source hashes and review receipts - input commit: 0f7be61e2c22317a4075561dc822c87d881a50db - original question SHA-256: 0499b17205a5bfa70db28aee981a18cd0a2bba0e8ab374c5430fb1e711a47fe1 - candidate record SHA-256: 433f6d03217b89d40a1701904c51e49bd855ae7efb44162cbf235b2caf6c98b0 - semantic review receipt SHA-256: bd35da62087a15d6b89b45585dc46e89b9efbe097cba7b3c707b5030496f013c - question-first witness SHA-256: fab45a10d8ac95c7d61d32e47d1bdd3ca862c17c3289a6bf4b01d4dc9492fbb6 - Lean: NOT_RUN · human review: NOT_PERFORMED [Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261013-advance-20261019-r05-algorithm-correctness-0069.json)