Explore related knowledge and questions →
← Question derivation index · Original question batch
R0018-09538 · q-20261013-advance-20261019-r05-algorithm-correctness-0038
Use the complete finite, possibly nondeterministic transition model S=Fin(6)={0,…,5}, Init=[0], Halt=[5], Step=[[0, 1], [1, 2], [2, 5], [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. Postcondition set=[]. Give (reachable halts, postcondition, bad reachable halts, partial correctness?, no reachable halt?).
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], [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. Postcondition set=[]. Give (reachable halts, postcondition, bad reachable halts, partial correctness?, no reachable halt?).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.
Before
n=6;raw Init=[0];raw Halt=[5];raw Step=[[0, 1], [1, 2], [2, 5], [4, 5], [2, 1]]
After
Init=[0];Halt=[5];canonical raw Step=[[0, 1], [1, 2], [2, 1], [2, 5], [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.
Rule: finite_transition_normalization · Uses: G001
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.
Rule: zero_step_reachability · Uses: G001, S001
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.
Rule: reachability_halt_truncates_expansion · Uses: G001, S002
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.
Rule: complete_finite_reachability_layer · Uses: G001, S003
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.
Rule: reachability_halt_truncates_expansion · Uses: G001, S004
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.
Rule: complete_finite_reachability_layer · Uses: G001, S005
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.
Rule: reachability_halt_truncates_expansion · Uses: G001, S006
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.
Rule: complete_finite_reachability_layer · Uses: G001, S007
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.
Rule: reachability_halt_truncates_expansion · Uses: G001, S008
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.
Rule: complete_finite_reachability_layer · Uses: G001, S009
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.
Rule: halt_stuck_active_are_distinct · Uses: G001, S010
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.
Rule: halt_stuck_active_are_distinct · Uses: G001, S011
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.
Rule: halt_stuck_active_are_distinct · Uses: G001, S012
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.
Rule: halt_stuck_active_are_distinct · Uses: G001, S013
Before
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.
Rule: partial_correctness_each_reachable_halt · Uses: G001, S014
Before
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.
Rule: partial_correctness_vacuity_not_termination · Uses: G001, S015
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.([5], [], [5], No, No)
The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.
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.
input commit: 0f7be61e2c22317a4075561dc822c87d881a50dboriginal question SHA-256: 25c99fb5eb17fb413754c2ac9233cdf566ce68b79c374bb726f92b8ea9c6a60fcandidate record SHA-256: bcf60664f44ec213f6e218616bfb8c89143f2f51b818c93f06992868c04877c9semantic review receipt SHA-256: bd35da62087a15d6b89b45585dc46e89b9efbe097cba7b3c707b5030496f013cquestion-first witness SHA-256: fab45a10d8ac95c7d61d32e47d1bdd3ca862c17c3289a6bf4b01d4dc9492fbb6Lean: NOT_RUN · human review: NOT_PERFORMED