# Final tribute to John Conway: FRACTRAN self-interpreter

It's time to conclude the series of John Conway challenges of mine.

## Background

A FRACTRAN program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

You can find some tips and tricks for writing FRACTRAN programs in the previous challenge Collatz in FRACTRAN.

## Challenge

Write a FRACTRAN program that

• takes a FRACTRAN program P and its input number N encoded as an integer, and
• halts if and only if the program P halts with the input N.

Use the following procedure for encoding P to get a single positive integer f(P):

• Write down the numerator and denominator of each fraction in P in base b, using the value b as a separator.
• Read the whole thing as a single number in base b+1.

You can choose the value of b, whether to put a separator at either end or not, and which number (numerator/denominator, first fraction/last fraction) comes first in the representation. One possible encoding is:

[455/33, 11/13, 1/11, 3/7, 11/2, 1/3]
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657


The input value must be in the form of $$\p^{f(P)} q^N n\$$, where $$\p, q\$$ are two distinct primes and $$\n\$$ is a number coprime to $$\pq\$$. You can choose the values of $$\p,q,n\$$. (This format is consistent with the 84-fraction answer on SO and the 48-fraction one linked below.)

The shortest program in terms of the number of fractions wins.

The best record available is 48 30 fractions by our very own m90!

• I think you need a more careful restriction than “you can freely choose how you encode the input”—what stops me from “encoding” the input as 1 if P(N) halts and 2 if P(N) does not halt? You should at least require the encoding to be computable. Be aware that if that’s the only requirement, the challenge can be solved by interpreting programs in any Turing-complete language, with the conversion from FRACTRAN programs handled by the encoding function. May 15 '20 at 3:56
• “it must be possible to reconstruct the original P and N from the input number through computation”—that’s the wrong direction to restrict. I can still “encode” the input as 1 · 3^P · 5^N if P(N) halts and 2 · 3^P · 5^N if P(N) does not halt. May 15 '20 at 4:54
• @AndersKaseorg I guess I should settle with the encoding already used... May 15 '20 at 5:07
• @Leo The encoding of Collatz in FRACTRAN is either 1 · 3^P · 5^N or 2 · 3^P · 5^N for each N. It exists. There’s currently no stipulation that I need to be able to compute which one it is. Such a stipulation is what I was proposing when I said “you should at least require the encoding to be computable”. (The important direction is that (P, N) ↦ input should be required to be computable; it makes no difference whether input ↦ (P, N) is required to be computable.) May 15 '20 at 5:16
• Just want to point out three brilliant people have already done this, so the current goal to beat is 48 fractions. I don't want to benefit from their ingenuity so I won't post it below, but here are the links to their work: 48-Lomont, 84-Amadeus, 1779-Beder, 1779-Beder-CodeGolf May 15 '20 at 17:25

# 30 fractions

37^1/41^1
43^1/47^1
41^10*31^1*13^1/37^10*29^1
1/37^10
47^9*5^1/43^9*7^1
47^9/43^9*17^1
47^9/43^9*13^1
47^9/43^9*23^1
41^1*47^8/37^1*43^8*29^1
41^6*47^3/37^1*43^8*53^2
41^2*47^7*23^1*7^1/37^2*43^7*13^1*5^1
47^9*53^2/37^2*43^7*13^1
41^3*47^6*13^1/37^3*43^6*23^1
41^2*47^7*23^1*7^1*29^1/37^3*43^6*13^1*5^1
41^3*47^6/37^3*43^6*13^1
41^4*47^5*11^1/37^4*43^5*17^1
41^5*47^4*5^1/37^5*43^4*13^1
41^5*47^4/37^5*43^4*7^1
41^5*47^4/37^5*43^4*29^1
41^5*47^4*3^1/37^5*43^4*2^1
41^6*47^3*17^1/37^6*43^3*13^1
41^7*47^2*23^1/37^7*43^2*3^1
41^8*47^1*3^1*2^3/37^8*43^1*23^4
41^1*47^8*2^3*53^1/37^8*43^1*23^3
41^8*47^1*11^1*2^1/37^8*43^1*23^1
41^9*31^3/37^9*29^1
41^7*47^2*23^1*29^2/37^9*3^1
29^1/31^1
37^10*13^1/11^1
37^1/43^1


p = 2, q = 5, n = 37^5 * 43^4 * 53^1

b = 3, denominators first, last fraction first, separator at start and not at end

## How does this work?

To make it easier to understand, assign meaningful names to the primes used:

ifracs=2 ifracsw=3 inum=5 inum_r=7 multiplicand=11 products=13 denominator=13 numerator=17 temp=23 multiplier=29 multiplier_r=31 stateA=37 stateA_r=41 stateB=43 stateB_r=47 p_indicator=53


Convert denominators to negative exponents, and then we can omit the ^ and * symbols (always including exponents even if 1). This produces a notation similar to Subtractpocalypse (which, as the linked page notes, becomes equivalent to FRACTRAN with a single change). Together with this, we use the name of a prime to refer to the exponent of that prime in the current number.

### The state mechanism

stateA and stateB together form a state. 10 standard states (0,9), (1,8), (2,7), ..., (9,0) are chosen such that none has both components greater than or equal to another's; this way, an instruction can single out one state that it will execute only in, by subtracting the appropriate values from stateA and stateB.

To restore the state (same or different), we can't simply add back to stateA and stateB, as that would give the numerator and denominator a common factor. Instead, we add values corresponding to the new state to stateA_r and stateB_r, and the first two instructions transfer those values back to stateA and stateB:

# At the start
stateA_r -1  stateA +1
stateB_r -1  stateB +1


We use an abbreviated notation for these common parts:

State[M -> N] = stateA -M  stateB -(9-M)  stateA_r +N  stateB_r +(9-N)
State[N] = State[N -> N]


Also, the last instruction is used to automatically advance from one state to the next when nothing else executes:

# At the end
stateA +1  stateB -1


### Parsing f(P)

# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1


We start in state 5. There are some other instructions in state 5, but they do nothing at the start.

First, the value of f(P) is transferred from ifracs to ifracsw. The instruction in state 6 does nothing at the start.

The value is transferred from ifracsw to temp next. Then, in state 8, divide by 4 by repeatedly subtracting 4 from temp and adding 1 to ifracsw; simultaneously, 'refill' ifracs by adding the difference, which is 3, to it. After this finishes, the remainder will be left in temp.

The next instruction tests for the separator (3), changing to state 1 and also incrementing p_indicator and 'refilling' ifracs.

Suppose we haven't reached a separator. To reconstruct the base-3 number, we need to multiply the digits by 1, 3, 9, etc. This uses...

### The multiplication subroutine

Multiplication happens automatically whenever the end of a state is reached, before moving on to the next state, with multiplicand nonzero. It adds to products the product of multiplicand and (multiplier+1), for a few reasons. It is implemented by these instructions:

# Multiplication (near the start)
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10

# Multiplication (near the end)
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1


The fourth of these instructions executes first. It decrements multiplicand, increments products (for the 1 added to multiplier), and adds 10 to stateA, enabling the upper two instructions. Then the first instruction runs repeatedly, transferring multiplier to multiplier_r while adding to products. The second instruction subtracts the added 10 from stateA, exiting this section, then the third instruction transfers multiplier_r back to multiplier, and this repeats until multiplicand is zero.

### Back to parsing f(P)

State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2


To activate multiplication, the last instruction of state 8 transfers temp to multiplicand, while 'refilling' ifracs. Multiplication occurs before the transition to state 9, adding the appropriate value for this digit to products.

Finally, we need to triple the effective multiplier, which means tripling multiplier and adding 2 to it. The instructions in state 9 accomplish that; the second one duplicates the instruction in state 7 as a way of testing whether we have reached the end of f(P), ending the program (since this is the last state) if so. (Note that, because we specified that f(P) begins with a separator, the end always happens after only one digit 0 is read, with multiplier=0, avoiding an infinite loop.)

Changing state immediately after filling multiplier_r from multiplier avoids a similar infinite loop. Going to state 7, the process repeats to read the next digit of f(P).

### Handling the fraction

State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1


p_indicator is initialised to 1, and incremented upon changing from state 8 to state 1. Thus, after reading the first (in this process; the last in the base-4 expansion) of each pair of numbers, which we have specified to be the numerator, multiplier is reset to 0, and since p_indicator is now 2, it becomes 0 with a change to state 6, where the value is transferred from products to numerator.

After reading the denominator, state 1 ends with p_indicator=1.

(Note that denominator is an alias for products -- they refer to the same prime.)

In state 2, the first instruction transfers denominator to temp and inum to inum_r simultaneously. This ends when denominator or inum reaches zero.

The second instruction checks for denominator being nonzero, which indicates that the number (original value of inum) was not divisible by the (original) denominator; it changes to state 0 while increasing p_indicator to 3. Then, the instructions in state 0 transfer inum_r back to inum, clear several values, and then continue to state 1 to clear multiplier and proceed to state 6 to resume reading f(P), with p_indicator reduced back to 1.

In state 3, temp is transferred back to denominator, and the second instruction returns to state 2 while repeating its first instruction (as before, this checks for completion) and incrementing multiplier.

If the loop exits here, then the number (original value of inum) was divisible by the (original) denominator, and multiplier contains the quotient minus 1 (for each iteration except the last).

State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1


The final instruction of state 3 clears denominator (which is product). Then, in state 4, we transfer numerator to multiplicand, and with the transition to state 5, that value is multiplied by the quotient (recall that the multiplication subroutine uses multiplier+1). In state 5, we transfer products to inum, clear some values, and continue to repeat from the start.

## The whole program with the updated notation

# Initialise: ifracs, inum; p_indicator=1, stateA=5, stateB=4
stateA_r -1  stateA +1
stateB_r -1  stateB +1

# Multiplication
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10

State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1

State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1

# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1
State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2

# Multiplication
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1

stateA +1  stateB -1

• Well done. Is this now the world champion FRACTRAN self-interpreter? Jul 9 at 14:51

Here are a few solutions not written by me! If one of these is yours, please feel free to post it separately and I'll remove it from this answer. These have all been in this comment for a while, but I'm converting it to an answer for greater visibility.