# Question 9586: Partial Correctness, Termination, and Total Correctness [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-0086) 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-09586 · q-20261013-advance-20261019-r05-algorithm-correctness-0086 ## 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], [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. Postcondition set=[]. Give (reachable halts, postcondition, bad halts, partial correctness?, vacuous partial case?, stuck states, nonhalting cycle?, termination?, total correctness?). - 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], [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. Postcondition set=[]. Give (reachable halts, postcondition, bad halts, partial correctness?, vacuous partial case?, stuck states, nonhalting cycle?, termination?, total correctness?). ## 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], [2, 1]] After Init=[0];Halt=[5];canonical raw Step=[[0, 1], [1, 2], [2, 1], [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=[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 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=[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 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=[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=[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 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 reachable Halt state=5;postcondition=[] After postcondition satisfied=No Conditions: none Partial correctness checks the postcondition only at reachable halts.Unreachable halts are not counterexamples,and nonterminated states are not successful results. Step identifiers and dependenciesRule: partial_correctness_each_reachable_halt · Uses: G001, S014 S016 · impliesBefore reachable halts=[5];bad halts=[5] After partial correctness=No;no reachable halt=No Conditions: none With no reachable halt,partial correctness may hold vacuously without establishing termination. Step identifiers and dependenciesRule: partial_correctness_vacuity_not_termination · Uses: G001, S015 S017 · 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, S016 S018 · impliesBefore 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 dependenciesRule: finite_cycle_sink_peeling · Uses: G001, S017 S019 · impliesBefore 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 dependenciesRule: explicit_reachable_cycle_witness · Uses: G001, S018 S020 · 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, S019 S021 · impliesBefore partial=No;all-path termination=No After total correctness=No Conditions: none Total correctness requires both correct reachable halting results and successful termination of every execution.One successful path or vacuous partial correctness is insufficient. Step identifiers and dependenciesRule: total_correctness_requires_both_obligations · Uses: G001, S020 ## Reverse checks - 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 — Check against the original data and this step's premises; a one-way implication is not an equivalence. - 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 — Check against the original data and this step's premises; a one-way implication is not an equivalence. - 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 — Check against the original data and this step's premises; a one-way implication is not an equivalence. - 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 ([5], [], [5], No, No, [], Yes, 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: 8c6be668c6059eba6be3e51de6bf1617e09ffdb140af24f35f0e3929a65b733d - candidate record SHA-256: dc7839e120126b61035e56247789a986ca4e24cbc8c1a9957fd1fe6b4e54c6c4 - 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-0086.json)