Editorial: The Uncertainty Guidelines

Having a few days off over Christmas has given me the chance to catch up on some reading, including revisiting Gödel, Escher, Bach [ Hofstadter ]. In turn, this has absorbed rather a lot of time, so I haven’t got round to writing an editorial. I was also given a Sudoku Rubik’s cube, which I haven’t managed to complete yet. Tips welcome. I know I will have to resort to some group theory and a sensible notation on paper rather than just randomly trying moves and hoping for the best, though that is a good way to start to explore a puzzle. As ever, I digress. Near the start of his book, Hofstadter presents a puzzle he calls ‘MU’. You form valid strings from three characters, {M, I, U}. Starting with ‘MI’ can you form ‘MU’ using the following four rules?

1. x I => x IU
2. M x => M xx
3. x IIIy => x U y
4. x UU y => xy

where x and y stand for any string of characters. I haven’t solved this puzzle either, though a bit of trial and error reveals starting with ‘MI’, or indeed any string starting with M will only form strings starting with M, since none of the rules remove an M. MU is plausible, but it is neither self-evident nor certain that it can be made from MI. Of course, it might be impossible. How, in general, can you be certain that something is impossible? If you have a finite set of possibilities you can enumerate all of them and check the claimed impossibility is not held within. In the case of MU, there are infinite possible strings, so we cannot do this. Sometimes by assuming the impossible, you can derive a contradiction, from which all reasonable people would conclude the starting point is impossible. There are other options. I will leave the reader to explore the puzzle themselves and drawn their own conclusions or cheat [ Wikipedia ].

The ‘Sudokube’ is probably possible. The internet assures me if I remind myself how to solve a Rubik’s cube it will be simple enough. I have a confession – I never fully learnt how to do this. I was shown some instructions, transformed into group theory notation, when I was about twelve, yet not knowing group theory made these less than useful. Transforming the situation into another is often a successful way to solve a problem, provided you transform it into a known problem. Finding a helpful notation allows you to think more abstractly and drawn conclusions about blind alleyways and potentially fruitful paths. Abstracting and generalising can be powerful tools. We do this when we write functions. Usually, we don’t have a lookup table of all the possible results, but perform a transformation or calculation to return an answer. Of course, we sometimes then resort to lookup tables to speed things up later, but that is another matter. As programmers, we frequently solve puzzles or problems. The way the problem is presented tends to influence the outcome. If the person setting the problem frames it in terms of how they would like the problem to be solved, it is useful to ask, ‘What problem are you really trying to solve?’ or simply ‘Why?’ This type of issue is sometimes referred to as the XY problem, and frequently mentioned on Stack Overflow. It has been described as:

a mental block which leads to enormous amounts of wasted time and energy, both on the part of people asking for help, and on the part of those providing help. It often goes something like this:

• User wants to do X.
• User doesn’t know how to do X, but thinks they can fumble their way to a solution if they can just manage to do Y.
• User doesn’t know how to do Y either.
• User asks for help with Y.
• Others try to help user with Y, but are confused because Y seems like a strange problem to want to solve.
• After much interaction and wasted time, it finally becomes clear that the user really wants help with X, and that Y wasn’t even a suitable solution for X.’ [ XyProblem ]

I am not suggesting spending all your time being a sceptic or doubter; however, it is worth trying to find the right levels of abstraction to frame a question or answer. As I said, transforming something into a problem with a known solution can help, but it must be ‘isomorphic’ (or at least similar enough) to the original problem. If you admit uncertainty when you are not sure, this can be fruitful. If you can find a way to express the problem you are considering, be that in interfaces, function signatures or a concise mathematical formulation you at least have a way to discuss and explore the conundrum.

I have another confession; I never managed to learn my times tables properly at school. Some were easy because they had nice patterns, for example the nine times table. I tended to count up (or down) from the numbers I did know, by some combination of lookup and algebra. If I was uncertain of my answer, I would try another combination, say 7 times 8 stumped me, then 8 times 7 was far easier being double 4 sevens. Realising the general principle that natural numbers are commutative under multiplication

x × y = y × x

is powerful. Proving such general principles is another matter. In fact, it is possible to develop number systems which are not commutative, specifically Hamilton’s quaternions, which take the form

a + b i + c j + d k

where a , b , c , d ∈ ℝ or ℂ with i ² = j ² = k ² = ijk = -1. Those using complex numbers ℝ are known as bi-quaternions. You cannot be certain of commutativity; it is a property of basic arithmetic, rather than something provable. On the face of it, developing new number systems might seem like a pointless mind game. What’s their use? On one level this should not matter; theoretical things can be interesting in and of themselves. Nonetheless, if you insist, the quaternions provide a neat shortcut in theoretical physics to represent the Lorenz group of special relativity. They also provide quicker ways to calculate transformations in computer graphics, compared to matrices. Surprising things happen when you question things that seem certain, obvious or no-brainers.

Revisiting Hofstadter reminded me of Euclid’s fifth axiom. I remember it as given a ‘straight line’ and a point not on the line, there is only one way to draw a line through that point which doesn’t cross the line, though this appears to be Playfair’s axiom [ Playfair ]. The fifth axiom, or parallel postulate, is more usually stated as

If a straight line crossing two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if extended indefinitely, meet on that side on which are the angles less than the two right angles. [ Cut-the-knot ]

For the MU puzzle, MI was given as an axiom; you assume it is ‘true’ or take it as given and see what follows. We can do likewise with Euclid’s axioms, and derive theorems of Euclidean geometry, such as the internal angles of a triangle sum to 180°. The thing about axioms or principles is they are more like guidelines. The inner child shouts ‘But why?’ then finds out what happens if you disobey the claimed ‘rules’. By dropping Euclid’s parallel postulate, you develop or discover so-called Non-Euclidean geometries. For a hyperbolic geometry, parallel lines get further apart, whereas for an elliptical geometry they get closer together. The fifth postulate got picked on because it seemed untidy compared to the others, which in essence defined a straight line, circles and right angles. Many people tried to prove the fifth postulate, using just the first four and all failed. In the process, counterintuitive, yet consistent geometries were discovered. Poincare accepted these counterintuitive ideas, paving the way for Einstein [ Barbosa ]. It is worth noting that special relativity’s use of non-Euclidean geometry is not equivalent to saying it is ‘true’ or correct, just that the more counterintuitive mathematical setting made the scientific theory simpler. This echoes the quaternions; a different representation with fewer or different constraints can give more powerful or simpler ways to approach puzzles.

Many scientific theories are referred to as ‘Laws’, for example Kepler’s laws of planetary motion. This suggests they are unbreakable and in some sense fixed. Newton took on board Kepler’s ideas, and talks of Kepler’s guesses, deductions and discoveries; he did not describe these as laws. Any ideas, be that scientific or otherwise, tended to be described as ‘philosophy’ at the time. It seems Voltaire first introduced the term ‘Law’ of Kepler’s philosophy, where he describes the area rule as a ‘ Law inviolably observed by all the Planets ’ [ Wilson ]. Using the word law suggests either a divine decree, or a rule following from the essence or nature of the planets and indeed space. They are fundamental principles, which fit observation. Most people would just take the term on board nowadays, without giving it too much thought. We tend to regard scientific models as something which fits observations, but expect them to change and evolve over time. Our thinking about science, and indeed thinking itself, changes over time. Similarly, our approach to coding has changed over time. Some things are driven by trends or new language features. Other things are more fundamental; the move to structured code changed how we wrote and reasoned about code. Introduction of object oriented programming has an effect. Attempting to write in a functional language influences how you solve a problem. I wonder what we might discover if we looked at coding standards through the last decades? Would we see trends and changes? Perhaps they should actually be referred to as conventions, or guidelines. Some laws are more like models, and others an attempt to enforce a norm. They can still be questioned or modified over time. They may be governed by some guiding principles, like fit our current observations, communicate clearly, or be nice. Laws and conventions give ways to assess and reason about things, but should never be set in stone.

In general, our syntax and abstractions allow us to frame problems in different ways, which in turn can make analysis easier or, if we are not careful, more difficult. We see this when we try to add features to code, or even test it. Sometimes an abstraction introduced in just the right place allows us to hook something different in, be that a test or a new feature. Sometimes this was a deliberate choice from a developer, or we just got lucky. Kevlin Henney [ Henney ] wrote about what he coined ‘The Uncertainty Principle’ for Overload a few years ago. In particular, he said, ‘ in software development, a lack of certainty about something can be part of the solution rather than part of the problem. ’ Rather than having a long meeting and countless arguments when a choice is presented, he advocates structuring your code so it doesn’t matter which is chosen. Hiding the choice between an algorithm or lookup table behind an interface helps to ‘ mark out the boundaries in a software system and loosen the coupling ’. Using uncertainty as a positive force is a great guideline.

Uncertainty can be unnerving, but if you embrace it and remember all the times it has driven new discoveries this should give you hope. We don’t know everything, and there is always room for improvement. Let’s see what chaos, new discoveries and surprising, unpredicted results the New Year brings.

References

[Barbosa] Pedro M. Rosario Barbosa The Relation between Formal Science and Natural Science: Underdetermination of Science Project http://pmrb.net/uos/?q=4_3_2

[Cut-the-knot] http://www.cut-the-knot.org/triangle/pythpar/Fifth.shtml

[Henney] ‘The Uncertainty Principle’, Overload 115, June 2013 https://accu.org/index.php/journals/1854

[Hofstadter] Douglas R. Hofstadter, Gödel, Escher, Bach: An Eternal Golden Braid , New York: Basic Books, 1979.

[Playfair] Playfair, J. Elements of Geometry: Containing the First Six Books of Euclid, with a Supplement on the Circle and the Geometry of Solids to which are added Elements of Plane and Spherical Trigonometry . New York: W. E. Dean, 1861. (according to http://mathworld.wolfram.com/PlayfairsAxiom.html )

[Wikipedia] https://en.wikipedia.org/wiki/MU_puzzle

[Wilson] Wilson, Curtis ‘Kepler’s Laws, So-Called’, HAD News (Historical astronomy division of the American Astronomical Society, May 1994. https://had.aas.org/sites/had.aas.org/files/HADN31.pdf

[XyProblem] http://mywiki.wooledge.org/XyProblem