Slides for "Theoretically cheating at your A-levels"
I recently gave a presentation on a previous blog post, [[FRACTRAN and theoretically cheating at your A-levels]]B, about how you could theoretically cheat in an exam by fitting a universal Turing machine into your A-level calculator. These are the slides that I made for that talk.
While creating the slides, I found some more interesting things that I couldn’t fit in the original post or in the talk.
A quick primer
The main idea behind [[FRACTRAN and theoretically cheating at your A-levels]]B is based around “fraction games”, an incredibly simple model of computation invented by John Conway in 1987.
\[f _ 1, f _ 2, \ldots, f _ k\](Conway ‘87): To play the fraction game corresponding to a given list
of fractions and starting integer $N$, you repeatedly multiply the integer you have at any state (initially $N$) by the earliest $f _ i$ in the list for which the answer is integral. Whenever there is no such $f _ i$, the game stops.
Computational universality and catalogue numbers
To show that it is computationally universal, for every computable function you need to find some list of fractions and some starting integer $N$ such that “playing” that fraction game corresponds to calculating a particular value of that computable function. Conway proves that it is computationally universal like so:
\[\begin{aligned}\frac{583}{559}&,\frac{629}{551},\frac{437}{527},\frac{82}{517},\frac{615}{329},\frac{371}{129},\frac{1}{115},\frac{53}{86},\frac{43}{53},\frac{23}{47},\frac{341}{46},\\\\ \frac{41}{43}&,\frac{47}{41}, \frac{29}{37}, \frac{37}{31}, \frac{37}{29}, \frac{299}{23}, \frac{47}{15}, \frac{161}{19}, \frac{527}{7}, \frac{159}{17}, \frac{1}{13}, \frac{1}{3}\end{aligned}\]Define $f _ c(n) = m$ if POLYGAME:
when started at $c 2^{2^n}$, stops at $2^{2^m}$ and otherwise leave $f _ c(n)$ undefined. Then every computable function appears among $f _ 0, f _ 1, f _ 2, \ldots$.
Not only does this show that FRACTRAN is computationally universal, it also creates a breathtakingly simple enumeration of all computable functions. Conway himself describes this fact like so:
Works that develop the theory of effective computation are often written by authors whose interests are more logical than computational, and so they seldom give elegant treatments of the essentially computational parts of this theory. Any effective enumeration of the computable functions is probably complicated enough to spread over a chapter, and we might read that “of course the explicit computation of the index number for any function of interest is totally impracticable.” Many of these defects stem from a bad choice of the underlying computational model.
Suppose you wanted to create an explicit enumeration of all computable functions using the standard description of a Turing machine like the following from [[Course - Models of Computation MT23]]U:
\[(Q, \Sigma, \Gamma, \vdash, \sqcup, \delta, q _ 0, q _ \text{acc}, q _ \text{rej})\]A Turing machine is a A 9-tuple
where
- $Q$ finite set, states
- $\Sigma \subseteq \Gamma$ finite set, input alphabet
- $\Gamma$ finite set, tape alphabet
- $\vdash \, \in \Gamma \setminus \Sigma$, left end marker
- $\sqcup \in \Gamma \setminus \Sigma$, blank symbol
- $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$, transition function
- $q _ 0, q _ \text{acc}, q _ \text{rej} \in Q$, start, accept and reject states with $q _ \text{acc} \ne q _ \text{rej}$
This would be enormously complicated! You’d have to somehow encode the explicit description of any Turing machine all into one integer $N$. But the enumeration using FRACTRAN is simple enough that you can actually compute the catalogue numbers for simple functions, and likewise compute the functions corresponding to small values of $c$.
| $c$ | All defined values of $f _ c$ |
|---|---|
| 0 | none |
| 1 | $n \mapsto n$ |
| 2 | $0 \mapsto 1$ |
| 4 | $0 \mapsto 2$ |
| 8 | $1 \mapsto 2$ |
| 16 | $2 \mapsto 3$ |
| 64 | $1 \mapsto 3$ |
| 77 | $n \mapsto 0$ |
| 128 | $0 \mapsto 3$ |
| 133 | $0 \mapsto 0$ |
| 255 | $n+1 \mapsto n+1$ |
| 256 | $3\mapsto4$ |
| 847 | $n \mapsto 1$ |
| 37485 | $0 \mapsto 0$, $n+1 \mapsto n$ |
| 2268945 | $n \mapsto n+1$ |
| $2^k$ | $a \mapsto b$ if $2^b - 2^a = k$ |
| $7 \cdot 11^{2^k}$ | $n \mapsto k$ |
| $\frac{15}{7} \cdot 1029^{2^{k-1}}$ | $n \mapsto n+k$ |
The name “catalogue numbers” is apt: it like you can flip through all the computable functions in a book and have a look at any that take your fancy.
Hilbert’s 10th problem
As hopefully made clear by both [[FRACTRAN and theoretically cheating at your A-levels]]B and the slides, actually using FRACTRAN in an exam is firmly in the realm of extreme impracticability. But suppose the exam board were legitimately concerned by this. What could they do?
If you suspend your disbelief for a moment, one approach would be to only ask questions on the exam which were instances of undecidable problems. One type of problem that would work for this is determining whether a Diophantine equation with rational coefficients has a solution among the rational numbers.
At the turn of the 19th century, David Hilbert proposed a list of 23 problems he thought were of great importance. One of these was as follows:
Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.
For example:
- $3x^2 - 2xy - y^2 z - 7 = 0$ has an integer solution, but
- $x^2 + y^2 + 1 = 0$ has no solutions.
Much later in 1970, it was proven that this problem is actually undecidable. So if the exam board were to only set questions on whether Diophantine equations had solutions, then having an extra Turing machine in the exam would be useless, you’d also need to sneak some sort of oracle into the exam (which would be even more impractical!).
References and links
- “Hilbert’s 10th Problem” on Wikipedia.
- FRACTRAN: A simple universal programming language for arithmetic, Conway’s original paper.