Jump to content

FRACTRAN

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Tea2min (talk | contribs) at 05:09, 21 May 2020 (Undid revision 957788641 by Anilped (talk): ?). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows:

  1. for the first fraction f in the list for which nf is an integer, replace n by nf
  2. repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt.

Conway 1987 gives the following formula for primes in FRACTRAN:[note 1]

Starting with n=2, this FRACTRAN program generates the following sequence of integers:

  • 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (sequence A007542 in the OEIS)

After 2, this sequence contains the following powers of 2:

(sequence A034785 in the OEIS)

which are the prime powers of 2.

Understanding a FRACTRAN program

A FRACTRAN program can be seen as a type of register machine where the registers are stored in prime exponents in the argument n.

Using Gödel numbering, a positive integer n can encode an arbitrary number of arbitrarily large positive integer variables.[note 2] The value of each variable is encoded as the exponent of a prime number in the prime factorization of the integer. For example, the integer

represents a register state in which one variable (which we will call v2) holds the value 2 and two other variables (v3 and v5) hold the value 1. All other variables hold the value 0.

A FRACTRAN program is an ordered list of positive fractions. Each fraction represents an instruction that tests one or more variables, represented by the prime factors of its denominator. For example:

tests v2 and v5. If and , then it subtracts 2 from v2 and 1 from v5 and adds 1 to v3 and 1 to v7. For example:

Since the FRACTRAN program is just a list of fractions, these test-decrement-increment instructions are the only allowed instructions in the FRACTRAN language. In addition the following restrictions apply:

  • Each time an instruction is executed, the variables that are tested are also decremented.
  • The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them.
  • It is not possible for a FRACTRAN instruction to directly test if a variable is 0 (However, an indirect test can be implemented by creating a default instruction that is placed after other instructions that test a particular variable.).

Creating simple programs

Addition

The simplest FRACTRAN program is a single instruction such as

This program can be represented as a (very simple) algorithm as follows:

FRACTRAN
Instruction
Condition Action
v2 > 0 Subtract 1 from v2
Add 1 to v3
v2 = 0 Stop

Given an initial input of the form , this program will compute the sequence , , etc., until eventually, after steps, no factors of 2 remain and the product with no longer yields an integer; the machine then stops with a final output of . It therefore adds two integers together.

Multiplication

We can create a "multiplier" by "looping" through the "adder". In order to do this we need to introduce states into our algorithm. This algorithm will take a number and produce :

Current State Condition Action Next State
A v7 > 0 Subtract 1 from v7
Add 1 to v3
A
v7 = 0 and
v2 > 0
Subtract 1 from v2 B
v7 = 0 and
v2 = 0 and
v3 > 0
Subtract 1 from v3 A
v7 = 0 and
v2 = 0 and
v3 = 0
Stop
B v3 > 0 Subtract 1 from v3
Add 1 to v5
Add 1 to v7
B
v3 = 0 None A

State B is a loop that adds v3 to v5 and also moves v3 to v7, and state A is an outer control loop that repeats the loop in state B v2 times. State A also restores the value of v3 from v7 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 v11 and v13. Note that we require two state control indicators for one loop; a primary flag (v11) and a secondary flag (v13). 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:

FRACTRAN
Instruction
Current State State
Indicators
Condition Action Next State
A None v7 > 0 Subtract 1 from v7
Add 1 to v3
A
v7 = 0 and
v2 > 0
Subtract 1 from v2 B
v7 = 0 and
v2 = 0 and
v3 > 0
Subtract 1 from v3 A
v7 = 0 and
v2 = 0 and
v3 = 0
Stop
B v11, v13 v3 > 0 Subtract 1 from v3
Add 1 to v5
Add 1 to v7
B
v3 = 0 None A

When we write out the FRACTRAN instructions, we must put the state A instructions last, because state A has no state indicators - it is the default state if no state indicators are set. So as a FRACTRAN program, the multiplier becomes:

With input 2a3b this program produces output 5ab. [note 3]

The above FRACTRAN program, computing 3 times 2 (so that its input is and its output should be because 3 times 2 equals 6.

Subtraction and division

In a similar way, we can create a FRACTRAN "subtracter", and repeated subtractions allow us to create a "quotient and remainder" algorithm as follows:

FRACTRAN
Instruction
Current State State
Indicators
Condition Action Next State
A v11, v13 v2 > 0 and
v3 > 0
Subtract 1 from v2
Subtract 1 from v3
Add 1 to v7
A
v2 = 0 and
v3 > 0
Subtract 1 from v3 X
v3 = 0 Add 1 to v5 B
B v17, v19 v7 > 0 Subtract 1 from v7
Add 1 to v3
B
v7 = 0 None A
X v3 > 0 Subtract 1 from v3 X
v3 = 0 Stop

Writing out the FRACTRAN program, we have:

and input 2n3d11 produces output 5q7r where n = qd + r and 0 ≤ r < d.

Conway's prime algorithm

Conway's prime generating algorithm above is essentially a quotient and remainder algorithm within two loops. Given input of the form where 0 ≤ m < n, the algorithm tries to divide n+1 by each number from n down to 1, until it finds the largest number k that is a divisor of n+1. It then returns 2n+1 7k-1 and repeats. The only times that the sequence of state numbers generated by the algorithm produces a power of 2 is when k is 1 (so that the exponent of 7 is 0), which only occurs if the exponent of 2 is a prime. A step-by-step explanation of Conway's algorithm can be found in Havil(2007).

Other examples

The following FRACTRAN program:

calculates the Hamming weight H(a) of the binary expansion of a i.e. the number of 1s in the binary expansion of a.[1] Given input 2a, its output is 13H(a). The program can be analysed as follows:

FRACTRAN
Instruction
Current State State
Indicators
Condition Action Next State
A v5, v11 v2 > 1 Subtract 2 from v2
Add 1 to v3
A
v2 = 1 Subtract 1 from v2
Add 1 to v13
B
v2 = 0 None B
B None v3 > 0 Subtract 1 from v3
Add 1 to v2
B
v3 = 0 and
v7 > 0
Subtract 1 from v7
Add 1 to v2
A
v3 = 0 and
v7 = 0 and
v2 > 0
Subtract 1 from v2
add 1 to v7
B
v2 = 0 and
v3 = 0 and
v7 = 0
Stop

Notes

  1. ^ In The Book of Numbers, John Conway and Richard Guy gave a slightly different sequence:
  2. ^ Gödel numbering cannot be directly used for negative integers, floating point numbers or text strings, although conventions could be adopted to represent these data types indirectly. Proposed extensions to FRACTRAN include FRACTRAN++ and Bag.
  3. ^ A similar multiplier algorithm is described at the Esolang FRACTRAN page.

References

  1. ^ John Baez, Puzzle #4, The n-Category Café
  • Conway, John H. (1987). "FRACTRAN: A simple universal programming language for arithmetic". Open Problems in Communication and Computation. Springer-Verlag New York, Inc.: 4–26. doi:10.1007/978-1-4612-4808-8_2. ISBN 978-1-4612-9162-6. {{cite journal}}: Invalid |ref=harv (help)
  • Conway, John H.; Guy, Richard K. (1996). The Book of Numbers. Springer-Verlag New York, Inc. ISBN 0-387-97993-X.
  • Havil, Julian (2007). Nonplussed!. Princeton University Press. ISBN 0-691-12056-0.
  • Roberts, Siobhan (2015). "Criteria of virtue". Genius At Play - The Curious Mind of John Horton Conway. Bloomsbury. pp. 115–119. ISBN 978-1-62040-593-2.

See also