The obvious answer is yes: there are only so many atoms in the universe to make paper and ink out of, so of course it will have to end at some point. But questions of this ilk, like so many apparently simple questions, can spark an interesting discussion. The more interesting question is this:

The first half of the question is clearly false, think about paradoxes like ‘Is the sentence “This sentence is false” true?’. For further discussion, please go talk to your favourite philosopher (mine is Nick Bostrom). The second half is something we will be looking into in more detail; more precisely, how such a question led to the creation of modern computer science. To rephrase the previous question with a bit more formality and clarity:

Formal logic is the logic used by mathematicians and logisticians (see How can we tell that $2\neq 1$?). Further discussion is well outside the scope of this article, but it is just there to make sure that the question the algorithm would try to solve doesn’t produce paradoxes like the one above. This question, or one very similar but in German and itself written in the language of formal logic, was posed by one of the most famous mathematicians of the 20th century—David Hilbert. It is called the decision problem, or Entscheidungsproblem in German. We can clearly see that this is an important question. Almost any question in mathematics can be posed in terms of formal logic and mathematics can be used almost anywhere. So being able to show that there will always be an algorithm to compute the answer to any question would be of incredible use. It would mean that there would always be a clear method to solve any problem that can be reduced to mathematics.

Before we can dig our teeth into this problem though, we must first properly define what we mean by an algorithm. Since we live in a world built by, and upon, algorithms, we intuitively know that it is something that takes in some information, does something to it, and then gives us some sort of ‘useful’ answer. This is a very nebulous definition, clearly, as I used the term ‘does something’. That and the idea of utility is a heavily contextual notion (if I’m stuck and dehydrated in a desert, a proof to the Riemann hypothesis isn’t going to be very useful to me). A slightly more formal definition of an algorithm in plain English would be the definition from Marshall H Stone and Donald Knuth:

Or in layman’s terms, a finite sequence of well-defined operations. But as any mathematician knows, writing something in plain English is usually much easier than doing so in mathematics.

This is where Alan Turing comes into the picture. Turing was one of the greatest mathematicians of the 20th century—if not of all time—and was a key figure in the foundation of theoretical computer science and artificial intelligence; he is often called the father of both fields. Turing did a whole host of wonderful and amazing work in his short career. Unfortunately, despite the revolutionary work that he did both academically and in breaking Nazi codes during the second world war, his work was not truly recognised until long after his passing. This was, of course, partly to do with the secretive work of codebreaking, but also because he was gay at a time when homosexual acts were illegal. In 1952, he was convicted of ‘gross indecency’ and given the option between a prison sentence or chemical conversion therapy; the chemical injections he chose led to depression, and later, his premature death by suicide. Turing died at the age of only 41, and we can only wonder what astonishing work he would have done if the prejudices of the time hadn’t caused his premature death.

Turing’s first groundbreaking work was solving Hilbert’s problem and defining what was meant by an algorithm in formal mathematics using his elegant concept of the Turing machine. A definition and answer had been given a few months earlier by another mathematician called Alonzo Church—a pioneer in his own right and someone who Turing would later study under for his PhD. However, not only was Turing’s solution a greater conceptual leap than Church’s proof, but it was also a more intuitive and pragmatic idea than the heavy formal logic of Church’s approach, called lambda calculus. But enough beating around the bush, let us talk about the Turing machine.

The Turing machine and the Church–Turing thesis

Turing’s idea of how to formalise an algorithm in a mathematical framework was to design a machine that would be similar to the concepts proposed by Ada Lovelace and Charles Babbage, two more pioneering mathematicians and founders of the field of computer science. This was a mathematical construction composed of an infinite tape, a box (normally called a head) that could read what’s written on the tape and write new things onto the tape, a motor to move the head left or right, a set of numbers/symbols to read, and a processor full of instructions. The idea is that the input for the algorithm is written on the tape, the Turing machine then reads this and performs a sequence of simple actions dictated by the processor, perhaps using the tape to temporarily store information, and then writes the output of the algorithm on the tape. We’ll look at an explicit example of a Turing machine working in a minute, but first all the components of a Turing machine fit and work together like so:

• The processor can have (finitely) many different configurations of its internal settings: we shall call these states.
• The Turing machine itself doesn’t have any memory. But we can encode what it previously read by switching into one of many different states.
• The Turing machine is fully deterministic and well-defined. Given the current state and the symbol the head is reading, we know exactly what the machine will do.
• In a given state, the Turing machine can do any combination of the following: read the tape, write to the tape, move the head left or right, and (depending on what was read from the tape) change the state that the processor is in.
• There has to be at least one state in the processor that will stop the Turing machine and signal the end of the computation: this is usually called a halt state for the Turing machine. This is typically done when the head has printed the output of the algorithm.

Turing’s great insight was not only the simplicity of his construction but the notion that perhaps any form of computation could be represented as a Turing machine. This was later expanded upon during his study under Church for his PhD, leading to a groundbreaking theory which is now the cornerstone of computer science and a branch of logic and mathematics called computability theory. The Church–Turing thesis states that any computable function (a function computable by a machine or any formal algorithm that solves a problem) can be translated into an equivalent computation model involving a Turing machine. There is still some ambiguity about what exactly a computable function is and if every possible computation is represented as a computable function. But as these questions are still being discussed by academics all over the world, we will sidestep this thorny issue.

The Church–Turing thesis quickly leads to the conclusion that since our brain can compute mathematics and all algorithms that have been developed thus far can be computed by our brains, every algorithm ever computed is equivalent to a Turing machine! Because of this fact, the modern definition of an algorithm is based around Turing machines.

Now that we have a mathematical definition of a general algorithm, can we answer Hilbert’s question? Yes, we can, but first let’s get a little more comfortable with Turing machines.

Example Turing machine: how to build a dam in three easy steps

Like most things in mathematics, the best way to get some familiarity with an idea is to see a worked through example. The toy machine I will use to illustrate Turing machines is one from a rather famous family of Turing machines created by Tibor Radó called busy beavers s (Radó also
discovered a general solution to Plateau’s problem, see The birth of the Fields medal). They are very simple machines that are fed an infinite tape full of 0s and their aim in life is to write as many 1s as possible on the tape; but it can’t just print 1s forever, it has to stop eventually. The example we will look at is the 3-state busy beaver.

Starting in state A, the Turing machine reads a 0, so it erases this and writes a 1 in its place. Then it moves the head so that it is positioned over the next symbol, and the processor transitions into state B. The next symbol the head reads is again 0, but this time because it’s in a different state the Turing machine leaves this 0 as it is, moves the head again, and transitions into state C. The machine just keeps repeating this process until it enters its halt state.

Although we don’t see it here, where the Turing machine derives its main source of power is its ability to switch state depending on the information on the tape and encoded information from its previous state. If you are familiar with a bit of programming, this is very similar to jumping to a memory location in assembly language or conditional statements and loops that are found in higher-level languages like Python. If you want to write one out for yourself in full—I recommend you don’t. Even a simplified binary number checker takes more than a page of explanation of explicit states and even longer if you wanted to show it all working—I know from painful experience. But if you’re feeling very proactive, try to play out the beaver from above: you could use it on a row of coins to represent the tape with $\text{tails}=0$ and $\text{heads}=1$. Extra credit for making a 4-state beaver.

The Turing machine and the decision problem or: how I learned to stop worrying and love the halting problem

Now, finally, back to Hilbert’s Entscheidungsproblem. How did Turing solve it? Turing’s own paper and full technical proof isn’t too hard to read or understand. I will, however, provide a truncated version of the proof and try to provide an alternate method while keeping the core intuition.

In the paper, Turing proposes a method to encode a Turing machine, the states, and inputted symbols, into what he coins a description number. Similar to what we do to with text and Unicode—uniquely representing some text with a binary number. This description number describes the machine, and therefore the computation that it represents, completely! He then asks the obvious next question.

If we could, then we would show that any yes/no statement has at least one corresponding Turing machine (which Turing showed was equivalent to a computable algorithm) and so the answer to Hilbert’s question would be yes! Unfortunately, this is not the case; so, the answer to Hilbert’s question is a resounding no.

Turing was able to show this by using an idea from another Titan in the world of mathematics and logic, Kurt Gödel. Gödel is famous for a lot of important results from the fields of logic, mathematics, and philosophy, and is an interesting person in his own right. However, the key Turing used—and therefore the thing we will be looking at—is Gödel’s incompleteness theorem. This is a wonderfully mind-bending theorem that deserves its own article, and I highly recommend you go read into it (try Gödel’s Proof by E Nagel and JR Newman), but the important piece of logic that Turing adapted was the idea of using something being self-referential to reach a contradiction. We can see this in the paradox I mentioned at the start: ‘Is the sentence “This sentence is false” true?’. Gödel’s idea was very similar, but to formalise it in the realm of formal logic was his great achievement.

To use this insight, Turing proposed a Turing machine, and therefore a computable algorithm, that I’m sure anyone who has ever written code wishes they had in their back pocket: a Turing machine to see if another Turing machine, with a given input, will halt. Or in other words, a computable algorithm which can tell you whether an algorithm, together with an input, would eventually stop and give you an answer, or whether it would just keep cranking through calculations forever.

As an aside, an algorithm that could do this would not only be a boon for any budding programmer wishing to debug their code—but also an incredibly useful tool in pure mathematics. You could solve Goldbach’s conjecture by applying this mystical Turing machine to a simple program to search for the first counterexample! (What would the program look like?) Unfortunately, like most things that are too good to be true, this doesn’t exist. Let’s see why!

Let’s suppose we have this amazing halt-deducing Turing machine and call it $H$ (for $H$alt). If Hilbert’s decision problem has a positive answer, this machine will exist—as asking if a Turing machine halts can be written in formal logic—so let’s not get bogged down in the details of how it would hypothetically work. But, on a high level, if we give $H$ a description of a Turing machine and its input, $H$ will either halt and print ‘halts’ onto the tape if the inputted Turing machine halts: or it will halt and print ‘loop’ onto the tape if the inputted Turing machine loops forever. In particular, note that $H$ itself will always halt.

We can then modify this machine a little bit. To $H$ we attach an inverter which will flip its output: if $H$ outputs ‘halts’, the inverter will go into a loop and not halt; if $H$ outputs ‘loop’, the inverter will halt and output a picture of a scorpion. As mentioned before, $H$ needs two inputs: the Turing machine itself and its input. We wish to check if $H$ terminates when we apply it to itself, so we need to put $H$ into both of its input slots. To do this, we can attach a device to copy the input into it, which we can call a cloner. We can call this new Turing machine $H^*$:

Now that we have $H^*$, and the idea from Gödel of self-application, all we need to do is input $H^*$ into itself. When we input $H^*$ we have two possibilities. If $H^*$ does halt, then the inverter means that $H^*$ doesn’t halt. But if $H^*$ doesn’t halt, then $H^*$ does halt. We have reached a contradiction!

But the only thing we assumed is that $H$, and therefore $H^*$, exists. But as the existence of $H$ leads to a contradiction, we must conclude that a Turing machine like $H$ cannot exist. However, as a Turing machine is a mathematical object and asking if it will halt can be phrased in terms of formal logic, a yes to Hilbert’s question would mean that $H$ does exist! Therefore Hilbert’s question has negative answer: not all yes/no questions can be answered by an algorithm.

This argument is the same as the one Turing presented in his original paper, albeit simplified: there he shows that the description number of $H$ and $H^*$ can’t be calculated as the computation would go on forever. This is what we call an uncomputable number as no finite algorithm could ever compute it.

Typically, the numbers we are use every day ($\pi$, $\mathrm{e}$, $5$, $3/4$, etc) only require a finite amount of information to represent them. This can be the number itself if it is an integer, or a quotient of integers, but some numbers with infinite non-repeating decimal expansions can also be represented with a finite amount of information, like $\pi$ and $\mathrm{e}$. This is because $\pi$ and $\mathrm{e}$ both have finite generating formulae that can produce every digit. In other words, if you give me a position in $\pi$ or $\mathrm{e}$, like the 1737th position, the formula can find the 1737th digit of the number after a finite number of steps. This isn’t always the case: if I have an infinitely long number whose digits are random, you wouldn’t expect to be able to compute its decimal expansion using a finite algorithm. These numbers are uncomputable as they cannot be computed or represented in any finite sense.

The legacy of Turing and his machines

The legacy of the Turing machine and the ideas Turing put forward during his lifetime are hard to quantify. It is always hard to know what the world would be like without certain people and their ideas in it. Just limiting Turing’s body of work down to his idea of the Turing machine, we can imagine that the world would perhaps be almost unrecognisable. The concept of computers and their programs that were pioneered by Ada Lovelace and Charles Babbage had been around for about 93 years before Turing’s own paper on the matter. Despite Church developing his lambda calculus to solve Hilbert’s problem, it is quite difficult to imagine whether the modern computer would be around today, and if so, what it would look like. Perhaps the best view on the importance of Turing’s work comes from a sentiment put forward by John von Neumann, another intellectual juggernaut of the 20th century, to Stan Frankel. Frankel, writing in a letter to Brian Randell, says,

This was in reference to Von Neumann architecture, the modern framework of the stored program computer, which almost every computing device in the world, past 1945, can draw its direct heritage from. That, and the wider body of work credited to Turing, is why we call him the father of theoretical computer science. There is much more to talk about relating to Turing and his work, but as I said at the beginning, this article must end.

Probability has found itself a comfortable position amongst industry mathematics. And now, with the advancement of the computer age, a 100-year-old piece of maths has jumped to the forefront, namely Markov chains. These can be used for an awe-inspiring range of ideas including predicting the weather, mapping the probability distribution of a Monopoly properties, and even Donald Trump tweet generation. But what exactly are Markov chains, and why are they so unique?

Understanding Markov chains

Let’s say we are having a very nice day and are happy as a result, and that for some reason unknown to us, we only posses the emotional capacity to either be happy or sad. Can we predict what our feelings will be tomorrow? We know that our feelings tomorrow will be dependent on our feelings today; that is, a probabilistic function where the input is today’s mood and only today’s mood. Or in other words, a Markov chain!

So how do we do this? Let a happy day and a sad day each be states. We will represent these as nodes on a graph. Now we need some probabilities for the changing of states. Suppose we consider ourselves optimistic people: let’s say there’s a 5/6 chance that if we are happy today, we will be happy tomorrow, and a 1/2 chance if we are sad today, we will be happy tomorrow. Since something must happen tomorrow (all apocalyptic events excluded), then the sums of the probabilities leaving each state must add to 1.

This is an example of a two-state Markov chain, and while simple, it presents a useful visual aid to help our understanding. Much more formal and rigorous definitions can be found online, but in a nutshell, a Markov chain consists of a set of states where the probability of transitioning to any state is solely dependent on the current state. This dependence is called the Markov property and is what makes this neat piece of maths unique.

We can even use this Markov chain to predict how many happy days we’re going to have over the next week. One way we can do this is by following the chain by hand. Take a fair six-sided die and put a finger on the happy state: let’s say today was a good day. Now roll the die and if 1–5 is rolled, follow the looped arrow back to the happy state, else follow the arrow to the sad state. If we were unfortunate enough to find ourselves on the sad state, let even rolls—2, 4 and 6—send us down the arrow to the happy state; and odd—1, 3 and 5—loop back round to the sad state. If we make seven rolls where each roll is a new day, our finger will conclude on the prediction for how we’ll be feeling a week today. If we note the state after each roll, we’ll have predictions for each of the seven days. Now we can plan our week accordingly!

What about in a month then? Or a year? Following this diagram for 365 days, the rolling becomes a bit tedious. Instead, we can speed this up by taking ideas from linear algebra, and creating a transition matrix. Let each column of the matrix represent the current state and the rows represent the probabilities of transitioning to each state. For this example, the transition matrix is given by where $H$ = happy and $S$ = sad. We can use this representation to make a prediction for any number of days in the future. It should be noted that this could equally work with the columns and rows swapped, but as long as we’re conscious of which way we’re doing it, it simply becomes context. We can check whether the matrix has been created properly; the columns (in this case) should add to 1. If they don’t, something has gone horribly wrong! Say we wanted a prediction for two days’ time. We first raise this transition matrix to the power of 2, giving the following calculation:

\[ \begin{pmatrix}{\frac56}&{\frac12}\\ {\frac16}&{\frac12} \end{pmatrix}^2 = \begin{pmatrix} {\frac{5}{6} \times \frac{5}{6} + \frac{1}{2} \times \frac{1}{6}}&{\frac{5}{6} \times \frac{1}{2} + \frac{1}{2} \times \frac{1}{2}}\\ {\frac{1}{6} \times \frac{5}{6} + \frac{1}{2} \times \frac{1}{6}}&{\frac{1}{6} \times \frac{1}{2} + \frac{1}{2} \times \frac{1}{2}} \end{pmatrix} = \begin{pmatrix} {\frac79}&{\frac23}\\ {\frac29}&{\frac13} \end{pmatrix}. \]

Let’s see what is going on here by looking at the first entry of the new matrix. Like before, this is the probability of starting on happy and finishing back on happy, but this time for the day after tomorrow. If we relate this back to the graph, we can see that each term is a different possible path of probabilities (try saying that five times as fast) for exactly two days; $(5/6) \times (5/6)$ is happy tomorrow then happy the day after, and $(1/6)\times (1/2)$ is sad tomorrow and back to happy the day after. We then just choose a starting state. Like before, let’s be happy today: we represent this as a vector $\left(\begin{smallmatrix} 1 \\[2pt] 0 \end{smallmatrix}\right)$. We then do the following calculation with our matrix we just raised to the power of 2:

\[ \begin{pmatrix}{\frac79}&{\frac23}\\{\frac29}&{\frac13} \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} {\frac79}\\ {\frac29} \end{pmatrix}. \]

In return, we will get this column vector where the first entry is the probability of being on the happy state in exactly two days, and the second entry is being on the sad state. The cool thing is that we can put this matrix to any power $n$, which will give us a set of predictions for the $n$th day from today. Now, we’re mathematicians, so we need to do what any good mathematician should do and ask what happens when $n$ tends to infinity. This is something called the long run average probability and can be used to predict the behaviour of the Markov chain for some arbitrary but significant time in the future. This can be found analytically by taking some more ideas from linear algebra including a process called matrix diagonalisation, which would call for the use of more advanced mathematics. So instead, with a little rough-around-the-edges Python code (see the bottom of this article) we can get a pretty good idea. As $n$ gets very large, it is seen that the happy state tends to $0.75$, or $3/4$, and the sad state to $0.25$, or $1/4$. Therefore, given a significant amount of time in the future, this Markov chain is predicting a 75% chance we’ll be happy: not bad, all things considered.

We should, of course, acknowledge the limitations of this as a model. There are plenty of emotions not taken into consideration, nor whether a day holds special significance, eg a birthday. However, it’s easy to imagine how this can be expanded to accommodate for these other ideas with bigger graphs and larger matrices. The below graph shows how we might add a third emotion, for example boredom. Assign the probabilities based on whatever data we may be using, then fill out the graph accordingly.

We must be careful, however! When adding the new probabilities, it’s vital we ensure the sum of all arrows exiting a state still sum to exactly $1$. In addition, we are after all working with probabilities, and as such should be aware that a low chance does not mean impossible, and a high chance does not mean inevitable. This is just a model, and real life is rarely so organised.

What can be done with them?

Markov chains are used in a wide array of industry-based mathematics. But, with the rise of the technological age, these more light-hearted, fun and fascinating applications have emerged. A very interesting such use of these can be text prediction; quite a simple idea but we can have a lot of fun with it! If we take a few short sentences, say

“I love Markov chains.”
“Markov chains love me.”
“Markov is I.”

and we wanted to generate new original sentences from these, how could we do it? Representing each word as a state, we can create a Markov chain. The probabilities between states are then intuitively derived from the frequency of words following each other within these sentences. Take the word ‘Markov’. In these short sentence, the word ‘Markov’ is followed by the word ‘chains’ or ‘is’. However, if we look at the frequencies of these words, we have that ‘chains’ follows ‘Markov’ $2/3$ of the time, and ‘is’ for $1/3$. Do this analysis for every word and we have all the states and probabilities we need. Hence, like before, we can draw this up.

Once again, the probabilities allow for this to be played with using a fair six-sided die, with which we can generate some new sentences:

“I love Markov is I love Markov chains love me.”
“Markov chains love Markov chains.”
“I.”

Notice that not every pair of states has a pair of probabilities between them. This is because some states have a zero chance of following the current word. For example, in none of the three short sentences does ‘me’ directly follow from ‘chains’, leading to the zero chance of ‘me’ following ‘chains’ in the Markov chain. We could include these arrows on our graph, annotating them with the zero chance, however this would lead to an unnecessary clutter, especially since these extra arrows would be inconsequential for our purposes anyway.

There’s an amusing example of this method in Hannah Fry and Thomas Oléron Evans’s The Indisputable Existence of Santa Claus where they use this method to generate new Queen’s speeches with interesting results. Similarly, the sentences we’ve generated aren’t really sentences despite how much hilarity ensues, but imagine if we had a much larger data set\dots say someone’s Twitter. Twitter’s public availability lends itself as a large library of data containing peoples’ thoughts and opinions that we can use. One such person is 45th president of the United States, Donald Trump, who often likes to express his opinions publicly with questionable legitimacy, although here, this can work in our favour. Filip Hráček is a programmer from the Czech Republic who, as an experiment, created a Donald Trump tweet generator using Markov chains.

The probabilities become a lot more reliable when we introduce this large data set, causing the system to generate more coherent sentences. They’re still not perfect, but as was mentioned, this data coming from Donald Trump works in our favour. By setting each word in the tweet to a state, like before, the probabilities become more fine-tuned with the vast amount of data at hand. This model also employs something called an order-2 Markov chain. What this means is that instead of the next state being solely dependent on the previous, the model takes into account two states, or in the case the words, for making the decision on the next. A Reddit user under the handle Deimorz took this one step further and created a subreddit entirely populated with posts and comments generated by bot accounts using Markov chains. We can’t interact with them, but it’s unnerving to see the conversations they have relating to some topic unknown to us, especially since the bots are seemingly fully invested. There are quite a number of diverse experiments such as these online which use Markov chains, and which you can play with. Curiously, on the more serious side of application, this is the very primitive idea behind text prediction on mobile phones.

Andrey Andreyevich Markov, a Russian mathematician born in 1856, was the creator of this piece of mathematics in his work in probability theory. They have since been used in applied mathematics spanning many fields. Uses of Markov chains appear in computer science, business statistics, mathematical biology, contributing to Google’s PageRank, predictive text on mobile phones, and plenty more. What’s curious is that Markov developed this process for letter analysis in his native language of Russian: given a letter, calculating what is likely to be the next one. His motivation was based in probability and statistics and idea called the law of large numbers. For further reading, I’d recommend a research paper, The five greatest applications of Markov chains by Philipp von Hilgers and Amy N Lanville, which explains some of the most revolutionary uses of Markov chains in history, including going more in depth into Andrey Andreyevich Markov’s own application. It talks about historical uses in information theory, computer performance, and was one of the most interesting reads I found when conducting research for this article.

Now it’s your turn! Get out some dice and play with these examples, or even come up with your own. There is so much more to this neat piece of mathematics worth exploring, far too much to squeeze into this article. So I implore you to get reading, and start creating!

Python code for predicting mood

Some simple but functional code to find the probabilities for 52 weeks:

import numpy as np
A = np.array([[5 / 6, 1 / 2], [1 / 6, 1 / 2]])
B = []
for x in range(0, 365, 7):
    b = np.linalg.matrix power(A, x)
    start = np.array([[1], [0]])
    c = np.dot(b,start)
    B.append(x / 7)
    B.append(c)
print(B)

Six years ago, in September 2014, I started working on my PhD. By Christmas, I was doing calculations using code that would’ve taken the average PhD student three to four years to write. But this wasn’t down to my own programming skills: this was thanks to my supervisor and his previous students deciding to work on open source software.

Open source software is software whose developers release the source code that makes up the software, rather than just releasing a binary or application that the user can run. Almost always, open source software is free to use and adapt. Continue reading →

Rachel Riley puts the last of the six numbers on the rack and presses the button to generate a random target. The host—whoever the host is now, I haven’t really watched Countdown since Richard Whiteley died—says a few words and starts a 30-second timer. And the contestant thinks, ‘Now I need to combine those numbers to make the target. I know! I’ll just check all of the possible calculations with these six numbers! I wonder how many there are.’

The aim of the game is to combine the six given numbers using the four basic arithmetic operations ($+, -, \times$ and $\div$) to reach a target number. You do not need to use all of the numbers, but you may not use any number more often than it appears on the board. Also, you’re inexplicably not allowed to use fractions at any point.

For example, given the numbers in the big picture above, with the displayed target of 333, you might solve it as \[ ((50-4) \times 7)+5 + 6, \quad \text{or as} \quad ((50-6)\times 7) + 25,\] or several other acceptable ways.

TL;DR: including the trivial answer of 0, there are 974,861 distinct answers that can be reached by applying the four basic operations to combine six numbers, if you ignore (a) coincidences and (b) Countdown’s fraction-phobia.

Continue reading →

Any Chalkdust reader who has spent time playing billiards, snooker, or pool, will probably have some kind of feel for how the balls move around the table, how they bounce off each other, and how they bounce off the cushions. After a while, you just know instinctively how they should behave, at least in very simple situations. Reading this article is unlikely to improve your potting statistics; writing it has certainly not improved mine.

We can start by shrinking the cue ball to the size of a point, and imagining the object ball being squashed into a hard-edged circular disc that is so heavy that it does not recoil in a collision. The path of the incoming cue ball can be represented by a ray. Rays always follow straight lines between bounces, mimicking a ball rolling across a perfectly smooth horizontal table. Reflection of the incident ray by the disc is shown on the right. Draw a line from the disc’s centre through the point where the ray hits the circumference. That line is the normal, and the law of specular reflection tells us that angle out equals angle in, or in symbols, $\theta_\text{ref} = \theta_\text{inc}$.

To make things a bit more interesting, place identical discs at the corners of an equilateral triangle. That setup was first analysed in detail around three decades ago by physicist Pierre Gaspard and chemist Stuart Rice. Scientifically, their groundbreaking paper provided a paradigm for chaotic scattering in a plane but we can think of it as just an abstract game of pinball. The three-disc system turns out to be really useful in applied mathematics for understanding billiard-type problems, while in physics it crops up in fields from laser optics to the kinetic theory of gases.

Formulating the problem

The three-disc arrangement is shown below. Each disc has a radius of 1 unit, the size of the gap between them is $\ell$, and the shaded area $\Omega$ is called the scattering region. Any incoming ray is defined by an incidence angle $\theta_0$ and a displacement $x_0$. We can select whatever values we like for $\theta_0$ and $x_0$, and will refer to the pair of numbers $(x_0,\theta_0)$ as the input.

An incident ray can generally end up doing only one of four things, which are the allowed outputs of the system. If the ray enters $\Omega$, it ricochets between the discs before eventually escaping through one of the three gaps. The fourth possible outcome is that the ray is reflected away early on and so never enters $\Omega$ at all. Sometimes, a ray may also remain trapped inside $\Omega$ forever! But that situation is so incredibly unlikely that we can discard it here. Our question to try and answer is: for a given input, what will the ray do?

The butterfly effect

The zig-zagging path of any ray (its trajectory) can be computed using straight lines and applying the law of specular reflection every time it hits a disc. Crucially, our scattering problem is deterministic because it is governed by mathematical rules in which there is absolutely no randomness whatsoever.

Given an input, classical physics demands that there must exist a unique output. Seems reasonable and obvious. What is not so reasonable and obvious is that a tiny change to the input can lead to a dramatic change in the output. This strange phenomenon—where a system can be susceptible to minuscule fluctuations—is known technically as sensitive dependence on initial conditions. The term ‘butterfly effect’ is perhaps more widely known, coined by mathematician and meteorologist Edward Lorenz in the early 1970s as a nod to the unpredictability he discovered in a toy model of the weather. It purports, only half-jokingly, that a butterfly flapping its wings in Brazil can set off tornadoes in Texas.

The butterfly effect appears in our scattering problem when we have, for example, two incoming rays starting from the same $x_0$ value but with slightly different $\theta_0$ values. The difference between their paths may become magnified through successive bounces, building up remarkably quickly until the two trajectories have diverged and no longer bear any resemblance to one another. Ultimately, we may even find that the two almost (but not quite!) identical inputs lead to completely different outputs.

Scattering that exhibits the butterfly effect is said to be chaotic. In common parlance, ‘chaotic’ is often used to convey disorder or perhaps even (perceived) randomness. Here, we are deploying the word in a scientific sense. While it might sometimes look random, the three-disc system cannot do anything except behave deterministically. It also hides some very intricate and very ordered structure that can be seen if we look in the right place$\dots$

Exit basins and their properties

Ideally, we would like to relate a whole range of inputs to their corresponding outputs in one go. A nice way to do that is to think of $x_0$ and $\theta_0$ as labelling the horizontal and vertical axes, respectively, in a plane (just like the $x$–$y$ axes in coordinate geometry). Let us impose a square grid on a section of that $(x_0,\theta_0)$ plane, where all the points represent different initial conditions. For each point in turn, the outcome of the computation is recorded. The collection of outputs is then overlaid on top of the grid, and colour-coded according to our three-disc system in figure 1 to create a kind of map.

An example is shown below when the gap between the discs is relatively small. The map answers our earlier question in a very direct and effective way. It tells us exactly what a ray does as a function of starting point $(x_0,\theta_0)$, and even cuts out all the unnecessary information about individual trajectories. But a single map is just the tip of a giant iceberg, and many more questions now follow.

We can see that the $(x_0,\theta_0)$ plane is divided into four coloured regions, known as exit basins, which identify a unique output for a given input—white for gap 1, red for gap 2, black for gap 3 (initial conditions giving rise to trajectories that never enter $\Omega$ are shown in grey). The boundaries of these basins form striated patterns that are intertwined in extremely complicated ways. An important feature of the map is its self-similarity, where zooming-in on any portion of a boundary region uncovers smaller-scale substructure which looks like the pattern as a whole. Self-similarity persists all the way down to arbitrarily-fine length scales, and that property is typically one of the signatures of a mathematical fractal.

It has been known since the mid 1990s that the basins can also possess the infinitely-mindbending Wada property which, in visual terms, means the boundary between two colours never quite forms. Amazingly, the remaining colours somehow always nestle in. Wada says that we can never jump from a black region to a red region without also jumping across a white region. Similar is true for other black-red-white permutations. More subtly, any jump over a boundary necessarily involves crossing all three colours an infinite number of times!

As an analogy to the Wada property, think about the points on a number line. Any number is either rational (expressible as a ratio of integers, like $1/2$ or $3/4$) or irrational ($\pi$ or $\sqrt{2}$ are the usual suspects). We cannot jump from $1/2$ to $3/4$ without necessarily jumping over all the numbers in between, both the (countably-infinite) rationals and the (uncountably-infinite) irrationals. The same idea would also hold if we were to jump between any two irrational numbers instead.

It turns out that the basins vary with the gap width $\ell$ (see below). For instance, the map takes up more of the $(x_0,\theta_0)$ plane as $\ell$ increases. That result makes physical sense: we would expect the scattering region to be accessible from a wider range of initial conditions as the gaps become bigger. We can also see, qualitatively, that the pattern complexity reduces as $\ell$ increases since the density of the striations (loosely speaking, the number of stripes per unit area of boundary) drops off as the gaps expand.

The striations in the maps look quite linear, especially when magnified. However, some curving can be seen if we look over a wider range of the $(x_0,\theta_0)$ plane than shown here, particularly when the gap size increases.

There is also a fundamental physical principle determining how the stripes must fit together (perhaps you spotted it earlier). Look on the right: if the black and white areas are swapped over, the map still looks the same! This is a consequence of the fact that there is no difference between gaps 1 and 3. Our three-disc system has a line of mirror symmetry along the $y$-axis, and so the trajectories from $(-x_0,-\theta_0)$ and $(x_0,\theta_0)$ are necessarily mirror images of each other.

Uncertainty and unpredictability

So far, we have found that the butterfly effect can play a key role in scattering, and that basins become less finely-structured as the gaps increase in size. Far from being independent, these attributes are two sides of the same coin. One way to establish their connection is through the concept of uncertainty, thinking more carefully about what it means for a deterministic system to have an uncertain outcome. How can that apparent contradiction be allowed by physics?!

Let us start with an arbitrary initial condition, say $\boldsymbol{x}_0 \equiv (x_0,\theta_0)$, and from that point we can define two nearby initial conditions which are $\boldsymbol{x}_{0+\varepsilon} \equiv (x_0+\varepsilon,\theta_0)$ and $\boldsymbol{x}_{0-\varepsilon} = (x_0-\varepsilon,\theta_0)$. The small positive number $\varepsilon$ satisfies the inequality $\varepsilon \ll 1$. Equally, we could consider $(x_0,\theta_0+\varepsilon)$ and $(x_0,\theta_0-\varepsilon)$; it makes no difference to what follows. If the trajectories from all three starting points lead to the same outcome, then the input $\boldsymbol{x}_0$ is not susceptible to the butterfly effect when disturbances are of size $\varepsilon$.

We can quantify the uncertainty in a fixed region of the $(x_0,\theta_0)$ plane. Select at random a large number $N$ of $\boldsymbol{x}_0$ points within that region, and let $N_\varepsilon$ be the number of those points which exhibit the butterfly effect at the scale $\varepsilon$. Then, the fraction of our initial conditions with uncertain outcomes is given by the power law ${f_\varepsilon \equiv N_\varepsilon/N \sim \varepsilon^{2-D}}$. The pure number $D$ is the uncertainty fractal dimension. Smooth boundaries are associated with $D = 1$, a value that coincides exactly with the dimension of a typical line in Euclidean geometry (where points are 0D, lines are 1D, areas are 2D, and volumes are 3D). Accordingly, $f_\varepsilon$ scales with $\varepsilon^{2-1}=\varepsilon$, so that halving $\varepsilon$ halves the fraction of initial conditions with uncertain outcomes.

Fractal boundaries are those with $1 < D < 2$, where $D$ is non-integer and lies somewhere between the Euclidean dimensions of a line and an area. We can think of such boundaries as becoming increasingly rough and irregular (sometimes called area-filling) as $D$ approaches 2. In those cases, $f_\varepsilon$ scales with $\varepsilon$ to a power that drops towards zero as $D \rightarrow 2$. The crux of the matter is that for fractal boundaries, the proportion of uncertain points, $f_\varepsilon$, can fall off relatively slowly even for big reductions in $\varepsilon$.

An intuitive way to visualise unpredictability is to consider a small circle $\Sigma$ with radius $\varepsilon$ in the $(x_0,\theta_0)$ plane, as on the right. The centre of that circle of uncertainty is placed on the ‘ideal’ initial condition, $\boldsymbol{x}_0$. However, if we know $\boldsymbol{x}_0$ only to within an error $\varepsilon$, the ‘true’ initial condition may lie anywhere in the neighbourhood $\Sigma$ around $\boldsymbol{x}_0$. If $\Sigma$ contains only one colour, the outcome is independent of the finite accuracy. Uncertainty appears whenever $\Sigma$ impinges on a basin boundary, in which case all colours are contained and the outcome cannot be predicted. That is a recipe for a deterministic system to behave unpredictably, but in such a way that our faith in physics (thankfully) remains intact.

After a quick calculation, we find the following formula for relating $D$ to the way in which $f_\varepsilon$ varies across the scales: \[ D = 2 – \frac{\textrm{d}\;\textrm{log}_{10}f_\varepsilon}{\textrm{d}(\textrm{log}_{10}\varepsilon)}. \]

The slope of the log-log graph is thus a crucial piece of information, and it needs to be obtained by curve fitting. A set of graphs is shown on the left for the centre panes of the exit basins in figures 2 and 3 when $\varepsilon$ varies across six decimal orders of scale. For $\ell = 0.05$, we find $D \approx 1.92$ while for $\ell = 0.13$, we find $D \approx 1.81$. The largest (smallest) uncertainty dimension occurs for arrangements with the narrowest (widest) gaps, and the conclusion we can rightly draw is that the smaller the gap, the greater the sensitivity to initial fluctuations.

But what does it all mean more generally? It means something quite profound: systems associated with larger values of $D$, irrespective of their physical nature, have more complicated basin boundaries. So in a sense, the fractal dimension becomes a convenient yardstick for comparing the susceptibility of different systems to the butterfly effect.

Concluding remarks

We’ve applied some very deep ideas—ideas that have come to play a pivotal role in modern understandings of physics—to a toy scattering problem. But the bigger picture to think about is that simplicity can very often be deceptive. Uncertain outcomes are present whenever finite precision in our knowledge of initial conditions becomes important, not just here but pretty much everywhere. Perhaps one of the most important scientific discoveries of the 20th century is that unpredictability, so beautifully encoded within fractal basin boundaries, is in the DNA of physical law.

If you’re still not convinced, or if you want to amaze people with all this stuff, take four silvered spheres such as Christmas tree decorations and a bit of Blu-Tack or glue (see How to make). Form a tetrahedron with the decorations, place it on top of a mirror, and surround it on three sides with three pieces of cardboard (each of a different colour). Now look into the gaps of the tetrahedron. What you’ll see is chaotic scattering in action, and an impressive fractal pattern made possible by the law of specular reflection. You can see an example in the banner image at the top, and read more about it in the article Christmas Chaos by Windell Oskay.

I always derive great pleasure from seeing simple systems behave in complicated ways (the greater the contrast, the better). And it is inevitably mathematics that allows us to unpack what is going on. The fact that even the most trivially-familiar laws of Nature can conspire to create such complexity should be a source of wonder and inspiration to us all—not just Chalkdust readers!