In mathematics, there are easily described problems that are very challenging to solve.

A great example of this was made famous by Christian Goldbach in 1742. He discovered that no matter what even number he picked that was greater than two, it was always the sum of two primes.

A set of four tiles with four patterns that can tile a three-by-three floor. The tiles described in the main article are called Wang tiles and were introduced by the logician Hao Wang in 1961. Wang tiles are used to study decidability in mathematical logic.

For example, 42 = 23 + 19 where both 23 and 19 are prime. A prime number can only be divided by itself and one.

Even 279 years later, no one has been able to prove this is true for all even numbers – although with the help of computers it has been checked to billions of billions.

In mathematics, statements such as these that seem to be true, but we haven’t proved to be true, are called ‘conjectures’.

This particular conjecture is known as the ‘Goldbach conjecture’.

We can create a program that will stop when it finds a number where the Goldbach conjecture isn’t true. If we knew ahead of time if this program would stop, we would also know ahead of time that the Goldbach conjecture was false.

In mathematics, the question “can I build a program to know if another program will stop” is known as the ‘halting problem’. The halting problem is ‘undecidable’, which means that even with unlimited time and resources (even with all of Amazon’s data centres!) there will still be some programs that your program will never be able to check.

Maltese tile layers can have a difficult life made even more difficult by the undecidability of the halting problem. I’m sure you’ve often heard them say “Darned Halting Problem! I’m going to be late for dinner again!”.

Many times a customer will ask our beleaguered tile layer: “I would like my square room tiled with square tiles divided into four along the diagonals. I would like different colours or patterns in each quarter”. Even worse, the customer often adds: “the colours or patterns on the sides must match those tiles they touch and the tiles cannot be rotated”.

Our tile layer has a problem. What if he does a great job and the customer wants tiles to the same specification at his mother’s house? Our tile layer knows the customer’s mother and knows her house is filled with perfectly square rooms of different sizes.

He can determine if he can tile any particular square room given a choice of tiles. However, he cannot determine if he can tile any square room of any size with a given choice of tiles. This is undecidable.

This is why tile layers often never show up when they say they will.

The undecidability of the tiling problem was proved in 1966 by the mathematician Robert Berger. He proved this by embedding the halting problem as a subproblem of the tiling problem. In this way, the undecidability of the halting problem implies the undecidability of the tiling problem.

Dr Beatriz Zamora-Aviles is a lecturer at the Department of Mathematics within the Faculty of Science of the University of Malta.

Did you know?

• If the Goldbach conjecture described in the main article is shown to be unprovable, then the conjecture must be true! If it is false, then there is an even number greater than two that cannot be written as the sum of two primes. This number could be found even if it was incredibly large – proving the Goldbach conjecture false.

For more trivia, see: www.um.edu.mt/think

Sound bites

• Mathematicians observe patterns and use intuition to formulate conjectures. Researchers from the Technion Israel Institute of Technology have described the creation of an AI-based conjecture generator. They named it the Ramanujan Machine after the Indian mathematician known for his incredible ability to observe patterns in numbers and create conjectures. Their AI (artificial intelligence) simulates intuition to create formulas for mathematical constants such as π (pi). If you can prove one of these conjectured formulas correct, it will become a theorem named after you!

Raayoni, G., Gottlieb, S., Manor, Y. et al. Generating conjectures on fundamental constants with the Ramanujan Machine. Nature 590, 67–73 (2021)

For more sound bites, listen to Radio Mocha: Mondays at 7pm on Radju Malta and Thursdaysat 4pm on Radju Malta 2 (https://www.fb.com/Radio MochaMalta).