FRACTRAN and theoretically cheating at your A-levels

Created: September 22, 2024
Updated: October 04, 2024

A-levels are the most common exam students will take before going to university in the UK, similar in level to AP exams in the US.

The late John Conway was perhaps best known for his Game of Life – a set of 4 simple rules governing how cells on a grid evolve, which unexpectedly give rise to complex and beautiful patterns. In fact, these patterns can be so complex that if you wield them in just the right way, you can use them to build a Turing machine, and therefore do arbitrary computation. All from 4 simple rules!

In considering generalisations of the Collatz conjecture, Conway also invented something else with the surprising emergence of complexity from simplicity, which he dubbed FRACTRAN.


FRACTRAN: Start with a list of fractions $F$ and an initial whole number $N$.

\[F = (f_1, f_2, \ldots, f_n)\]

Find the first fraction $f _ i$ in the list such that $f _ i \times N$ is a whole number. Then set $N$ to $f _ i \times N$ and go back to the beginning of the list. Repeat this process indefinitely or until you reach a situation where $f _ i \times N$ isn’t a whole number for any $i$. In that case, halt.


When Conway would introduce FRACTRAN in a lecture, he would start with reciting from memory the following list of fractions, which he called “PRIMEGAME”:

\[F = \left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right)\]

Starting with $N = 2$, this produces the following sequence of $N$ (A007542 in the OEIS):

\[2, 15, 825, 725, 1925, 2275, 425, 390, \ldots\]

For example, here’s how you get the first three numbers in that list. Initially, $N = 2$ and the first fraction above such that $2 \times f _ i$ is a whole number is $15/2$, near the end of the list. This means $N$ becomes $2 \times 15/2 = 15$. Now going back to the start of the list, the first fraction where $15 \times f _ i$ is a whole number is $55/1$, which is at the very end of the list. This means you map $N$ to $15 \times 55 = 825$. Continuing in this way will produce the rest of the numbers in the sequence.

But there is something special about the list of $N$ that these fractions produce. If you restrict your attention to just the powers of two, you get the following subsequence:

\[2, 4, 8, 32, 128, 2048, 8192, \ldots\]

Or, writing them more explicitly:

\[2^1, 2^2, 2^3, 2^5, 2^7, 2^{11}, 2^{13}, 2^{15}, 2^{17}, \ldots\]

It turns out that the exponents are the prime numbers, in order of magnitude! (except $1$, which is not a prime).

Euclid’s computer

How can a list of fractions generate prime numbers? Like the Game of Life, FRACTRAN is “computationally universal”. This means that an appropriate list of fractions can be used to simulate an arbitrary Turing machine. Really every list of fractions is a program, and the list of fractions in PRIMEGAME make up a program that generates prime numbers.

I won’t prove that PRIMEGAME generates prime numbers here, but it effectively does so by trial division. An easier to understand FRACTRAN program is this one:

\[F = \left(\frac{5}{2}, \frac{5}{3}\right)\]

This is an addition program. When started with $N = 2^a 3^b$, this will terminate with $5^{a+b}$. Why? Each of the two fractions above eat up powers of $2$ or $3$ and multiply by $5$ each time they do. It’s reasonably simple to come up with more programs for operations like $2^a 3^a \mapsto 5^{ab}$, or $2^a 3^b \mapsto 5^{a \text{ div } b} 7^{a \text{ mod } b}$. In the original paper where he introduced FRACTRAN, Conway gives the monstrously obfuscated 39-fraction PIGAME:

\[\left( \frac{365}{46}, \frac{29}{161}, \frac{79}{575}, \cdots, \frac{1}{11}, \frac{1}{1024}, \frac{1}{97} \right)\]

When started with $N = 2^n \cdot 89$, this will terminate with $2^{\pi(n)}$ where $\pi(n)$ is the $n$-th digit of $\pi$!

After some time coming up with FRACTRAN programs, you might be intuitively convinced that it is computationally universal. But to actually prove that it can definitely do all the things that your favourite universal model of computation can do, you use a reduction. This involves showing that a “base” model of computation already shown to be Turing-complete can be simulated by an appropriate FRACTRAN program. Although it would be possible in theory, you could directly convert the description of any Turing machine to an equivalent FRACTRAN program, but this would be a bit unwieldy. Instead, a simpler approach is to show that FRACTRAN can simulate a register machine, which itself can simulate an arbitrary Turing machine.

What I find interesting about FRACTRAN is that it is such a conceptually simple model – there no need for a set of states, an alphabet, a finite set, a transition function, a tape, and all the other baggage that comes with the standard definition of a Turing machine. It relies only on concepts that existed in Euclid’s time, although their combination in this way might have been unnatural (for example, I’ve included a FRACTRAN-flavoured proof of the undecidability of the Halting problem in an appendix).

Cheating in your exams?

At first glance, it might not seem like this has anything to do with the Joint Council for Qualifications (JCQ) who oversee A-level exams in the United Kingdom. One responsibility of the JCQ is to provide regulations on what calculators must not be able to do in A-level mathematics exams. This is a portion of their specification:

spec

When I sat my A-levels, most people used a calculator called the Casio FX-991EX which supposedly met all the criteria of the JCQ calculator specification. Although it can integrate and differentiate, it does so numerically rather than symbolically. It also definitely doesn’t have any language translation features, nor is it advertised to do symbolic algebra manipulation.

It is also advertised as “non-programmable”. This is important, otherwise in theory you could download (or memorise) a program which implemented symbolic solutions to specific problems in the exam spec, and printed out all the workings so that you didn’t have to do them.

However! Under a strict interpretation of the guidelines above, this calculator should actually be banned. Despite being very limited in the operations it does provide, it does implement two features that can be combined together in unexpected ways: variable assignment and separating expressions with a :.

Variable assignment works like this: you type an expression, press STO (for store) and then the name of the variable you wish to store the result in. Then that variable can be used in all the ways you expect.

(This does mean that assignment is backwards compared to what might be familiar in Python, where you would write x = 3 rather than 3 = x).

A colon can be used to separate expressions. Pressing equals will compute one after the other, and once all the expressions have been calculated, the calculator loops back around to the first expression in the list. This cycle will continue until you press AC or an error occurs (like a division by zero, or taking the square root of a negative number).

These two features are useful together since they let you compute recurrences without having to remember all the intermediate values. You can just repeatedly press equals and the numbers in the sequence will appear one by one. For example, you can compute the Fibonacci sequence by first setting $A$ and $B$ to $1$, and then repeatedly executing $A + B \to A : A + B \to B$:

But how complex can the sequences you generate be?

The CALC language

To make this question precise, I’ll introduce CALC, a toy “programming” language which emulates the calculator’s functionality. A CALC program consists of three sections, which are delimited by a triple colon:

<init section>

:::

<loop section>

:::

<final section>

Each section can contain any number of calculator expressions separated by either a newline or a colon (where a newline is just shorthand for a colon). For example, the following CALC program estimates $\sqrt 2$ via ten iterations of Newton’s method, and then outputs the result:

# Store initial inputs
10 -> maxiter
1 -> iter
1.2 -> guess

:::

# Update the current guess using an iteration of Newton's method
guess - (guess * guess - 2) / (2 * guess) -> guess

# Increment iter, and if iter is more than maxiter, exit by
# causing an error
iter + 1 -> iter
sqrt(maxiter - iter)

:::

# Show a guess
guess

The initialisation section is run once, and corresponds to expressions you type into your calculator before the a loop section. All the expressions in the loop section are repeated until an error occurs, which corresponds to repeatedly pressing equals like in the Fibonacci example above. Then all the expressions in the final section are run once, these are the calculations you might do after your calculator has finished.

So the question becomes, how powerful is this language?

At this point, it might not come as a surprise that it is actually Turing-complete. For example, through a nauseating combination of these two features and other normal calculator features (taking absolute value, rounding, exponentiation), you can implement something that prints out the primes in a similar way to PRIMEGAME.

(The initial values of the variables are: $E = 10^{-99}$, $A = 2$, $B = 0$, $C = 2$, $100 = D$, and the calculator has its number format set to FIX 0. The initial closing bracket is only used for writing the program and is removed when it is actually run).

Now press equals repeatedly. Rather than looking out for powers of two, look out for the negative numbers: these will be the primes. But be warned that you may be waiting a while!

Here’s the corresponding CALC program, which will print all primes less than one hundred.

1e-99 -> E
2 -> A
0 -> B
A -> C
100 -> D

:::

A * -E^(Abs(B))
B + (1 - B)E^(Abs(B)) -> B
A + E^(Abs(B-1)) -> A
C + (A - C - 1)E^(Abs(B-1)) -> C
B + (2 - B)E^(Abs(B-1)) -> B
B - BE^(Abs(C-1)) * E^(Abs(B-2)) -> B
B + (1 - B) * (1-Rnd(Abs(A/C-Rnd(A/C))^(0.0001))) * E^(Abs(B-2)) -> B
C - E^(Abs(B-2)) -> C
sqrt(D-A)

I’ve written a more formal specification of this language in [[The CALC esoteric programming language]]B and as a wiki page on Esolangs.org. On that page is also a full interpreter for CALC programs, more examples, and an explanation of how the prime generating program works.

A proof of universality

This language is Turing-complete because it can implement any FRACTRAN program. If you have the FRACTRAN program $F$ given by:

\[F = \left( \frac{a_1}{b_1}, \cdots, \frac{a_k}{b_k} \right)\]

Then you can create the corresponding CALC program:

a_1/b_1 -> frac1
a_2/b_2 -> frac2
# ...
a_k/b_k -> fracK

<start_value> -> n

:::

P(n)
n -> start

# Multiply by first fraction a_i/b_i such that the result is an integer
n + (n * frac1 - n) * delta(n * frac1, floor(n * frac1)) * delta(start, n) -> n
n + (n * frac2 - n) * delta(n * frac2, floor(n * frac2)) * delta(start, n) -> n
# ...
n + (n * fracK - n) * delta(n * fracK, floor(n * fracK)) * delta(start, n) -> n

# Exit if n is unchanged, otherwise loop
sqrt(-delta(n, start))

However! This doesn’t quite prove that the calculator is universal because I’ve used two functions above, delta and floor, which aren’t directly available on the calculator.

Emulating delta

delta is a shorthand for Kronecker delta function,

\[\mathbf{delta}(x, y) = \begin{cases} 1 &\text{if }x = y \\ 0 &\text{otherwise} \end{cases}\]

This can be emulated on the calculator like so:

E^(2*Abs(x - y))

where E is set to $10^{-99}$. Because the calculator will treat any numbers smaller in magnitude than $10^{-100}$ as $0$, if Abs(x - y) is positive then E^(2*Abs(x - y)) will evaluate to $0$, otherwise it will be $0$ and E^(2*Abs(x - y)) will evaluate to $1$ (assuming x and y are integers).

Why is this useful? It allows you to implement what are effectively if-statements. Since there is no branching, every expression you separate with a colon is run every time you loop through all the expressions by pressing equals. This means control flow is difficult: say you want to write a program like

count = 0

if count != 10:
  count += 1
else:
  count = 0

You end up with something like this:

0 -> count

:::

# How to make sure only one of these is executed?
count+1 -> count  # Only do this when count != 10
0 -> count        # Do this when count == 10

This can be achieved with delta by modifying the expressions so that they have no effect if the conditions aren’t met.

0 -> count

:::

# If count == 10, this just becomes
#   count -> count
# Otherwise it is
#   count+1 -> count
count + 1 * (1 - delta(count, 10)) -> count

# If count == 10, this becomes:
#  0 -> count
# Otherwise it is
#  count -> count
count + (-count * delta(count, 10)) -> count

Emulating floor

floor is the standard function for rounding down:

\[\mathbf{floor}(x) = \lfloor x \rfloor\]

This is harder to implement, but can be done with the following expression. A function called Rnd is available on the calculator, and implements rounding to the nearest integer rather than rounding down (although to get it to work the way you expect, you have to be in FIX 0 display mode).

Rnd(Abs(x-Rnd(x))^(0.0001))

floor is useful because, together with delta, it lets you express the condition that a variable is an integer:

\[\mathbf{delta}(x, \mathbf{floor}(x)) = \begin{cases} 1 &\text{if }x \text{ is an integer} \\\\ 0 &\text{otherwise} \end{cases}\]

This is an important part of running FRACTRAN programs, since you need to be able to check whether $f _ i \times N$ is an integer.

Since both delta and floor can be implemented on the calculator, this proves that the calculator is Turing-complete.

Implications for your A-levels

So your A-level calculator can in principle run arbitrary programs. What are the implications?

The theoretical implications are huge! You could in theory write a program which was like an “A-level mathematics toolkit”, and could implement a symbolic algebra system and which would solve all the kinds of problems described in the syllabus and print out all the workings. And you could even build in a language translator for optimal non-compliance with the JCQ specification.

Even better, there’s actually nothing in the specification that prevents you from taking in two or more calculators into an exam. In fact, there’s even guidance that says this is allowed. So not only could you solve all the problems in your A-level maths test, you could solve them in parallel!

…but these are only theoretical implications. Unfortunately, the practical implications are very small. There are myriad reasons for this:

  • The calculator has a very limited amount of memory. You can only give it small inputs before the calculator will prevent you from typing any more characters; the prime generating program above is just small enough that it can fit on the screen.
  • There are only 10 variables available for you to use. Each of these have to be numbers, and only use only a finite number of bits – no chance of sneaking complicated programs into their decimal expansions.
  • Writing programs is incredibly slow. If you have to clear the calculator before taking it into an exam, then you’d have to memorise the program beforehand and then regurgitate all the symbols into the calculator once the exam starts. Frantically tapping away on the calculator might look a bit suspicious.
  • The programs themselves are also incredibly slow to execute. The prime program takes about 30 seconds to reveal that the 3rd prime number is 5.
  • Input/output is very limited. You can only make inputs at the very start, and because the calculator loops over all the expressions you type rather than jumping from one to another, you see everything. That’s why the prime numbers above are negative, to distinguish them from the noise generated by all the other expressions getting generated.
  • If you try to carry an armful of calculators into an exam, you will unfortunately get stopped. And saying “but according to the precise wording of the A-level specification…” isn’t going to get you anywhere.

These together mean that it’s actually very difficult to think of any type of program that would actually be practically useful in an A-level exam. Ideally, you’d want to write a program that does something complex to take the burden of doing something complex off of you. But complex programs are precisely the programs you can’t write!

Conclusion

I wanted to finish this post with a punchline where something actually complicated being run on the calculator, like Doom (whatever “running it” would actually mean if the outputs are just numbers). But writing complex programs on the calculator is really difficult and I’ve already dedicated enough time to this practically useless topic. The program for generating primes is the best I can manage.

Maybe there is a program out there which would actually be legitimately useful to an A-level student, but I can’t think of it, and don’t want to imagine the difficulty actually writing it – hopefully this is enough to convince anyone from JCQ that they shouldn’t revoke my A-levels. Actually cheating using this technique would be impossible.

But, nonetheless, it is a fun idea that under a very strict interpretation of the JCQ specification, the calculator almost all A-level students use should not be allowed. Despite not being actually useful, I think it’s still interesting enough to warrant talking about. It’s just one example of many where something simple ends up being accidentally Turing-complete.

Appendix: A FRACTRAN-flavoured proof of the undecidability of the halting problem

The halting problem asks whether there exists a program which can take another program as input, and output whether it will halt or loop forever on a given input. It’s a famous result of Turing that this is actually impossible, i.e. there exists no such program which can achieve this task. This is my attempt to put one proof into FRACTRAN-only terms.

Start by considering a table of all FRACTRAN programs, listed in a fixed order. This is possible to do since FRACTRAN programs are finite sequences of rational numbers $\mathbb Q$, which itself is a countable set.

Then, by counting rows, assign each possible FRACTRAN program an integer $k \ge 0$. For example, program $110$ might be the program $\left(\frac{5}{2}, \frac{5}{3}\right)$, and program $5092375$ might be PIGAME.

Now suppose, for a contradiction, that there does exist a “decider” FRACTRAN program $D = ( \cdots )$ that solves the Halting problem: when started with $N = 2^k 3^M$, it will:

  • Terminate with $N = 5$ if the FRACTRAN program $k$ will halt on input $M$, and
  • Terminate with $N = 7$ if the FRACTRAN program $k$ will not halt on input $M$.

Given the decider $D$, a FRACTRAN program $X$ can be constructed which does the following: when started with $N = 2^k 3^M$, it will:

  • Enter a loop if the FRACTRAN program $k$ will halt on input $M$, and
  • Halt if the FRACTRAN program $k$ will not halt on input $M$.

One way to construct this from $D$ is by appending $\left( \frac p 5, \frac 5 p\right)$ where $p$ is a prime not used in any of the fractions in $D$.

But now you get into a big mess if you give $X$ its own encoding! If $X$ halts, this means the program it was given must actually go on forever, but since it has itself as input, this is impossible. If it does goes on forever, this means it must also halt, which is also nonsense.

Therefore the initial assumption that a decider $D$ exists is not true, and hence the halting problem is undecidable.

References



Related posts