Statistician Solves Famous Mathematical Conjecture and Nobody Notices

The discovery was like a religious epiphany and a reward in itself

Via Wired, a delightful news story from Quanta Magazine about a retired statistician who solved a famous mathematical conjecture.

Thomas Royen, of Schwalbach am Taunus in Germany, solved the Gaussian Correlation Inequality conjecture (GCI), a problem that had eluded mathematicians since the 1950s. Royen’s breakthrough came by applying statistical methods and functions to a problem that others had been trying to solve using geometry. This has wonderful anecodtal value when we think about problem solving in general: someone with a different point of view was able to crack a conundrum that had eluded the most eminent of tenured mathematicians for two generations. Continue reading “Statistician Solves Famous Mathematical Conjecture and Nobody Notices”

So I Built A Cupcake Card Game Simulator

Children as young as 3 can play with adults on an equal footing because the game is entirely based on chance.

Orchard Toys do a great line in table top games for kids.  They include games of chance, strategy and memory using thick card and clear, colourful illustrations. I heartily recommend any of the line as good value for money birthday presents.  (They also have a Pirate Memory Game, a fact which will be hilarious to fans of Little Britain).

One of their games is Where’s My Cupcake?  Children as young as 3 can play with adults on an equal footing because the game is entirely based on chance.  Players take turns to pick a cupcake card off a central pile, and see if it matches one of the cake cards laid out on the table.  If it does, they add both cards to their pile.  If it does not, they check to see if anyone has a matching card on the top of their pile, asking “would you like a cupcake?”  If no-one claims the cupcake card, its placed on the table and the next person takes a turn.  Play continues like that until the pile of cards are exhausted. The player with the most cupcake cards is the winner. Full instructions are here.

The only problem with the game is that because it is entirely based on chance, its actually very hard to let a very young person win, if you want them to!  Sometimes, a string of bad luck can mean they miss several opportunities to put a cupcake on their plate, and they might lose several games in a row.  For someone just learning how to share and play fair, this can be demoralising to the point where they refuse to play.  It would be nice to be able to optimise their chance of victory.

Since the game is entirely procedural, the outcome of the game is pre-determined from the moment the cards are shuffled.   However, the shuffling involves 30 cards with 10 designs on them, which means there are 4.39 x 1039 possible combinations.  Even the fastest super computer in the world would take several millennia to evaluate every combination.

Nevertheless, I decided to script a virtual version of the game, so I could simulate many hundreds of games and discover which player is statistically most likely to win.  Armed with that knowledge, I can ensure that the person I want to prevail is sat in that spot when the game is played, and thereby decrease the likelihood of tears before bedtime. Continue reading “So I Built A Cupcake Card Game Simulator”

How many coins do I need to get all the characters in Crossy Road?

To be 95% certain of getting the last character you need from the Crossy Road vending machine, you’ll need 26,800 coins.  (Jump to the full table.)

Let me explain.

Crossy Road is a game for iOS and Android. It’s been described as ‘endless frogger‘. You begin playing as a chicken, and you have to cross a road and other obstacles.

For extra fun, the game offers additional characters to replace the chicken. At the time of writing there are 72 104 characters: farm-yard animals, jungle frogs, ghosts, zombies, robots, aliens and fauna from the Australian outback. You can even play as humans in the form of the game’s three creators. Continue reading “How many coins do I need to get all the characters in Crossy Road?”

Free encryption for Outlook and Apple Mail

What with the Heartbleed exploit, and approaching anniversary of the Edward Snowden revelations, I have been doing a lot of thinking about encryption of my e-mails and digital files.  A couple of weeks ago, at the FairSay e-Campaigning forum, I had a good chat with the folk from Open Rights Group who encouraged me to set up OwnCloud (which I’ve already done) and install open-source encryption for my e-mail.

I operate computers using both Microsoft Windows and Mac OS X, and use the standard mail applications for each.  Its not too hard to find open source encryption for these programmes, but I thought I would oil the cogs of the Internet by linking to them here.

gpg4win is the free and open-source encryption tool for Microsfot Outlook.  Installation is a relatively simple procedure and the end result is that you get an extra menu item, ‘Add Ins’, which has a big ‘encrypt this message’ button on it.  GPGTools is an analogus appliocation for Apple Mail on a Mac. Installation is just as easy—a single click to run the installer—and little ‘encrypt’ and ‘sign’ icons appear alongside the signature icons in a mail compose window. Continue reading “Free encryption for Outlook and Apple Mail”

Does Star Wars Prove That The Universe is Finite?

I’ve been thinking about the way languages are portrayed in the Star Wars film franchise, and what this says about the universe in which the adventures take place.

Star Wars Poster
Star Wars Poster

I’ve been thinking about the way languages are portrayed in the Star Wars film franchise, and what this says about the universe in which the adventures take place.

Some films portray all languages as English. This often happens in war and action films, where you’ll have German World War II officers or Russian spies speaking in accented English.

However, many English language films and television series choose to portray the other languages realistically, which involves subtitles (at least, when the dialogue is crucial).

In the Star Trek franchise, the Starfleet heroes encounter alien races every week. The problem is cleverly explained by the use of a Universal Translator (apparently built in to the little space ship emblem on the officers’ jerseys) which uses sophisticated AI to simultaneously translate the aliens’ words. There is even an episode of Star Trek: The Next Generation where the Universal Translator unexpectedly kicks in, thereby alterting the Enterprise Crew to the presence of a bizarre life-form, where they had perceived only crystals. Douglas Adams’ Hitchhikers’ Guide to the Galaxy series solves the language problem in a similar way. Arthur Dent puts a Babel Fish in his ear, allowing him to understand all alien languages perfectly.

By contrast, Star Wars introduces no such trickery. Each alien race has its own language, and we often see subtitles when characters like Greedo or Jabba the Hut are speaking. R2D2 and Chewbacca speak languages that are unintelligible to the audience, but at least the main characters have learnt to converse with them. C3PO’s raison d’être is as a protocol droid, familiar in millions of languages.

What does this say about the English used in Star Wars? Well, since all the alien languages are rendered as one might hear them, with no concessions to the audience, then we can assume that the language we hear spoken by Luke Skywalker and Han Solo is also as we would hear them. The actors are not speaking English as a cheat for the audience. They are speaking English because that is the language that these characters actually speak. Continue reading “Does Star Wars Prove That The Universe is Finite?”

Trainyard and Neural Pathways

Trainyard works wonderfully well as a metaphor for neural pathways

By far the best iPhone game I have come across is Trainyard. Is a deceptively simple puzzle, in which the player lays tracks to guide a set of coloured trains from their starting points to a goal. It has all the features of a great game: the rules are few, simple and intuitive. The puzzles are solved on a 7×7 grid, which gives the impression that a correct solution is on the cusp of revealing itself. The graphic design and sound design give you a satisfying mental ‘pay off’ when a puzzle is solved. This all adds to the addictive quality. It is no surprise it is one of the highest ranking games in the App Store.

Until recently, Trainyard’s only flaw was that it had a set number of puzzles to play. When they were solved, the payer had to go cold turkey. Playing a pre-solved puzzle was dull. However, with the latest update, the game’s creator Matt Rix has solved this problem, by providing an ‘engineer’ feature. Players can now create their own puzzle and upload it to Trainyard site for others to download and solve. This adds an element of competitiveness, and also social play, which makes the project as perfect as can be on it’s own terms. Highly recommended.

The ‘engineer’ feature has an interesting constraint. You cannot upload a self-made puzzle to the website unless you have solved it yourself. For a while I wondered why the computer could not already perceive which puzzles were solvable, and which were unsolvable… But then I remembered Godel’s Incompleteness Theorem, as explained to me in the sprawling Pulitzer Prize winning meditation on symmetry, mathematics, loops and consciousness, Godel, Escher, Bach by Douglas Hofstadter. Trainyard is, I think, a perfect little companion to this bizarre, genre defying book.

The cover of Godel, Escher, Back gives some clue to its esoteric subject matter
The cover of Godel, Escher, Back gives some clue to its esoteric subject matter

Godel’s Incompleteness Theorem says that in any consistent mathematic system will have certain “undecidable statements” which the system will not be able to answer either way. There will be true statements that nevertheless cannot be proven within that system. This holds for Trainyard, which is definitely a mathematic system with just a few logical rules. If you translate the elements of a puzzle (the starting points, gates, tracks, switch points, the colours of the trains, the goals, and the grid) into a mathematic formula (which, of course, you can do because the iPhone is essentially a mathematical machine, manipulating millions of 1’s and 0’s each second) there would be no equation or test that could consistently tell you whether the puzzle could be solved or not. The only way to tell is to run the puzzle, set off the trains, and see what happens. With some puzzles (such as this one) it is actually quite easy for even a novice player to work out that the puzzle has been solved, but the computer has to run it (all 10,603,843 steps) to confirm that fact.

Kurt Gödel
Kurt Gödel

The second link with Godel, Escher, Bach is to do with synapses, and how elements as simple and as binary as a neurones can give rise to enough symbols and signals to constitute a consciousness. Trainyard works wonderfully well as a metaphor for neural pathways, but it is only with the addition of the ‘engineer’ feature that this becomes apparent.

What do we notice when we look at the game in this way? (1) First of all anyone playing the game can see how the same track layout can result in completely different outcomes, depending on the number of trains sent from any given start position. On a related point, it is also interesting to see tiny changes to the track layout can fundamentally alter the outcome, once the trains are set in motion.

One of 3403 solutions to 'A Barrel Roll', one of the puzzles on Trainyard
One of 3403 solutions to 'A Barrel Roll', one of the puzzles on Trainyard

Through this, one can begin to comprehend how a brain, with very simple building blocks can give rise to huge, complex patterns, which is what is required to perceive and interact with the world. We can see how an apparently fixed set of neurones can act in different ways, depending on the precise nature of the stimulus.

A different insight – one only needs to play Trainyard for a short period of time to see how the same outcome can be achieved in a near infinite number of different ways – for each puzzle in game, users have submitted hundreds of unique solutions. It’s not really important how you get there, just so long as the right pattern emerges. When thinking about brains (artificial or biological), the lesson might be that trying to discover a particular set of pathways could be a red herring. If you were to do so, you would only understand one brain, not The Human Brain. We all have different patterns and pathways in our cerebal cortexts, and it is the different pathways we take to make the same patterns, that makes us unique.

Finally, it is worth remembering the insight of Godel’s Incompleteness Theorem. When you get to a sufficiently complex puzzle solution,you can never know whether it will produce the desired outcome, until you set the train running. This will hold for the artificial brains we create on circuit boards and in the RAM of computers – we won’t know whether the pattern we have created will work, until we have tried it. Which means we can’t work out the ‘correct’ pattern in advance. We’ll need to create some process of trial and error – a metaphor for evolution – before we hit on a correct pattern, and win our mental payoff.