FRACTRAN

Apr 26, 2026 - 22:53
0 0
FRACTRAN

Link suggestions feature: 3 links added.

← Previous revision Revision as of 17:22, 26 April 2026
Line 1: Line 1:
{{short description|Turing-complete esoteric programming language invented by John Conway}}
{{short description|Turing-complete esoteric programming language invented by John Conway}}


'''FRACTRAN''' is a [[Turing-complete]] [[esoteric programming language]] invented by the mathematician [[John Horton Conway|John Conway]]. A FRACTRAN program is an [[sequence|ordered list]] of positive [[fraction (mathematics)|fractions]] together with an initial positive integer input ''n''. The program is run by updating the integer ''n'' as follows:
'''FRACTRAN''' is a [[Turing-complete]] [[esoteric programming language]] invented by the mathematician [[John Horton Conway|John Conway]]. A FRACTRAN program is an [[sequence|ordered list]] of positive [[fraction (mathematics)|fractions]] together with an initial positive [[integer]] input ''n''. The program is run by updating the integer ''n'' as follows:
#for the first fraction ''f'' in the list for which ''nf'' is an integer, replace ''n'' by ''nf''
#for the first fraction ''f'' in the list for which ''nf'' is an integer, replace ''n'' by ''nf''
#repeat this rule until no fraction in the list produces an integer when multiplied by ''n'', then halt.
#repeat this rule until no fraction in the list produces an integer when multiplied by ''n'', then halt.
Line 104: Line 104:
|}
|}


State B is a loop that adds v_3 to v_5 and also moves v_3 to v_7, and state A is an outer control loop that repeats the loop in state B v_2 times. State A also restores the value of v_3 from v_7 after the loop in state B has completed.
State B is a loop that adds v_3 to v_5 and also moves v_3 to v_7, and state A is an outer [[control loop]] that repeats the loop in state B v_2 times. State A also restores the value of v_3 from v_7 after the loop in state B has completed.


We can implement states using new variables as state indicators. The state indicators for state B will be v_{11} and v_{13}. Note that we require two state control indicators for one loop; a primary flag (v_{11}) and a secondary flag (v_{13}). Because each indicator is consumed whenever it is tested, we need a secondary indicator to say "continue in the current state"; this secondary indicator is swapped back to the primary indicator in the next instruction, and the loop continues.
We can implement states using new variables as state indicators. The state indicators for state B will be v_{11} and v_{13}. Note that we require two state control indicators for one loop; a primary flag (v_{11}) and a secondary flag (v_{13}). Because each indicator is consumed whenever it is tested, we need a secondary indicator to say "continue in the current state"; this secondary indicator is swapped back to the primary indicator in the next instruction, and the loop continues.


Adding FRACTRAN state indicators and instructions to the multiplication algorithm table, we have:
Adding FRACTRAN state indicators and instructions to the [[multiplication algorithm]] table, we have:


{| class="wikitable"
{| class="wikitable"
Read More