Skip to content

NF + AxCount in 200 states

Choose a tag to compare

@wlad-svennik wlad-svennik released this 19 Nov 13:40
· 10 commits to main since this release
43ba3de

This two-symbol Turing machine has 200 working states and 400 transitions. On a blank tape it halts exactly when the original ten-row NF + AxCount calculus derives numeral 3. The reduction replaces 38 decoder states with 37.

NF_AxCount_200.tm is the literal transition table. NF_AxCount_200_Verification.zip contains the register source, reconstruction instructions, independent full-tape tests, and the Lean 4.35.0 proofs. Counting200.halts_iff_original_goal connects the table to the original calculus. Counting200.halts_iff_reference proves equivalence with the archived 201-state table on blank-tape halting. The direct proof uses one finite native_decide check for carry propagation.

Download SHA-256
NF_AxCount_200.tm 9f81e490032332528097c5ccba853f4d8813184989bad73ea095dc1f61c35904
NF_AxCount_200_Verification.zip e30ab019ac471059efc5d69dc0e153fd0d1d9b3c1beece5d946427aedc5eff6c