I’ve an article in the current edition of the New Scientist, about linear programming, convex polytopes, and Santos’ recent refutation of the Hirsch conjecture.
It’s available online here (£) or in a newsagent near you, presuming you live somewhere where the New Scientist is sold…
Like many others I’ve spent the morning watching the CERN seminar & press-conference on the announcement of the discovery of a Higgs-like boson. I have nothing to add to the huge amount of coverage of the physics itself, but I do want to note what an excellent job CERN’s director general Rolf Heuer has done in communicating these subtle & difficult issues, with clarity, enthusiasm, and humour.
In particular, here are three delightful metaphors he used during this morning’s press conference. (Questions and answers are all paraphrased by me.)
1. So have they found the Higgs boson or not?
Heuer likened the situation to seeing someone from far away. Imagine that you expect your best friend to emerge from over a distant hill at a certain time. Sure enough, a figure appears roughly when and where expected. That is the situation we are in now, following the latest round of data-crunching. But is it really the right person? Or could it be his twin brother? Or someone else altogether? These are the questions for which we need more data.
2. How does the Higgs mechanism give other particles mass?
Brilliantly, Heuer compared the Higgs field to a room full of journalists. Massless particles are like unknown members of the public, who can move through the room uninhibited. Massive particles, meanwhile, are celebrities; the more famous they are, the more journalists will gather round them, and the slower they will travel. (He drily observed that Peter Higgs was “very heavy” this morning.) Without these all-important ‘journalists’ to slow them down, other particles would travel at the speed of light.
That’s the Higgs field, but what of the boson? Heuer likened this to opening the door to the press room and whispering a rumour. Journalists will come together in clusters, as they try to find out what the buzz is. Those small crowds of journalists are the Higgs particles.
3. Why should we fund CERN rather than developing more practical new technologies?
Heuer spoke of a virtuous circle, connecting fundamental science to more applied research, noting that the feats of engineering which allowed this latest discovery required many significant technological breakthroughs.
He likened the situation to someone with a sack of corn. Should he eat it all? Or plant it all? In either case, he will starve sooner or later. The answer is he should eat some and plant some; the delicate judgement is in finding the right balance.
Mathematicians celebrate him above all for his trailblazing 1936 paper On computable numbers with an application to the Entscheidungsproblem [pdf], which remains a very readable and coherent account of his work.
Historians reflect on the heroic role he played in the cracking of the Enigma Code during WW2.
Artificial Intelligence researchers contemplate his work on neural networks and the challenge he posed in the Turing Test.
Civil liberties campaigners regret his persecution for homosexuality and mourn his tragic death.
If you’ve got five minutes to spare, click through any of the links above, or just have a flick through Andrew Hodges’ Turing scrapbook and read a little about the great man behind all these stories, and many more.
This is a sequel to the first hat game post, please read for the background. Everything here is based on a recent talk by Robert Lubarsky, about work of his with Stefan Geschke, though any errors are mine. This post will end up with some unsolved questions: if you think you know the answers (either because you can solve them yourself, or you know where solutions can be found), please leave a comment here or drop Robert an email. (He told me he was quite happy to throw this material out into the public domain, and I would obviously be delighted if this blog helps find some answers!)
So… the basic puzzle in this post is as before, but this time the first person in line sees an infinite queue of hat wearers standing in front of him. What strategy can our team adopt, to maximize the number of hats they are able to name correctly? Have a think about it… and a discussion follows…
Last time we started representing our hat-wearers using binary sequences, that is strings of 0s and 1s. The new puzzle plunges us into a world of infinite binary sequences. Infinite things are generally not easy to write down, so let’s take a very simple example consisting only of ones:
A = 1111111111111111……..
We’ll say that two infinite binary sequences are equivalent if they share the same tail, meaning that are identical beyond some point, before which they may differ (or to put it another way, the two only differ in finitely many places). So the sequence A above is equivalent to B = 0010111111111111……..
This notion of equivalence divides the whole space of all possible binary sequences into ‘classes’, inside each of which all sequences are equivalent. Getting back to our hat-wearing friends, everyone in the line has infinitely many people in front of them, and only finitely many behind. So everyone can tell at a glance which class they are in. They all know whether or not they are equivalent to A, or to any other specified sequence.
This doesn’t immediately help them. But we can take it a little further. We say two sequences are evenly equivalent if they differ in an even number of positions. Obviously, if two sequences are evenly equivalent, then they are equivalent. But not vice versa: A and B are equivalent but not evenly so.
A little thought reveals that any sequence which is in the same class as A (and therefore B) must be evenly equivalent to either A or to B. (Think about it!) Now this really is a useful fact for the hatters to exploit. In their strategy-meeting before the game, they go through every class, and they select one special sequence from it, to act as a reference point. Let’s say, for the class containing A & B, they choose A.
When they come to line up, let’s suppose the sequence of hats which emerges is B = 0010111111111111…….. Now, everyone can see which class they are in. So everyone knows to follow the plan and compare their own sequence to A. But they do not know which subclass they’re in i.e. whether they are evenly equivalent to A. However, the first person (who is hatless in this version) can see the whole sequence. So she can discern the subclass, in particular she sees that the sequence is not evenly equivalent to A. So she calls out “1”. (It would have been “0”, had the sequence been evenly equivalent to A.)
Now, as far as the next person is aware, the sequence is X010111111111111…….. where X is his own hat colour. He doesn’t know the value of X, but he knows from what he hears over his shoulder that the overall sequence is not evenly equivalent to A. So, he deduces that X=0, which he calls out. The next person knows 0Y101111111111….., and that the whole sequence is not evenly equivalent to A, so concludes that Y=0, and so on.
So our team has its strategy. The nub of it is to use the meeting beforehand to select one special sequence from every class, to which they will then compare their own via even equivalence. Call this strategy 1.
In fact, strategy 1 is overkill. The players don’t need to specify an individual sequence from each class. All they really need to select is one of the two subclasses. Of course, a unique sequence gives you a subclass (`the subclass containing A’), but not vice versa. Strategy 2 is to go through all the possible classes of sequences, selecting one subclass from each.
To put this into action, the first person will call “0” if the sequence is in the selected subclass, and “1” if it’s in the other. The next player now knows which subclass they’re in. Combining that with what he can see will tell him his hat-colour, and so on.
There is also a third possible strategy: the players use their meeting to decide upon a non-principal ultrafilter on the natural numbers. (I won’t go into further details here, people who care about such things can fill them in themselves.)
We have arrived at three solutions to the puzzle. But there are further questions: which strategy is the easiest? And what superpowers do the players need to follow it? Leaving aside their infinitely good eyesight, hearing, mental acuity, and patience, each strategy gives them a job to do during their planning meeting. These tasks are not at all straightforward!
In the example above, A is a very easy-to-describe sequence. Most sequences are not like this, but are uncomputable, random, and generally indescribable. In general, there is no procedure or algorithm that the players can hope to use to pick out a single sequence from each class, as strategy 1 requires. This can only be done using a superpower, meaning some version of the axiom of choice. But full choice is certainly excessive, and there is an assortment of weaker axioms. What is actually required here?
Strategy 2 appears slightly easier than 1: the players don’t have to select one sequence from the infinitely many in each class, they just need to pick one of the two subclasses. Nevertheless Lubarsky & Geschke have shown that this still requires more choosing-power than comes freely with the ZF axioms. What is more, strategy 2 is minimal: any strategy which solves the puzzle will allow a subclass to be selected from each class. Together these two facts imply that a team of hat-wearers working purely within ZF cannot solve the problem, but one with the full power of ZFC can. What is the minimum superpower, in terms of ability to choose, that the players need for each strategy?
We know from the above remarks that strategies 1 and 3 are each at least as strong as strategy 2. The conjecture here is that they are both strictly stronger than 2, and what is more that 1 & 3 are themselves inequivalent. Any further thoughts?
This is the first of two two posts about it, each based around a puzzle. So let’s get going with the first, which is something of a classic. The second is altogether trickier, indeed a complete answer seems to be as yet unknown…
Here’s the first puzzle: ten (or a hundred or any number) people stand in a line, one in front of the other. Each is wearing either a black or a white hat. If you’re in the queue, you don’t know your own hat-colour, or those of the the people behind you. But you can see the ones in front. Starting from the back of the line, the challenge is for each person to call out in turn, trying to guess the colour of their own hat. They are allowed to discuss strategy beforehand. So what plan can they hatch to maximise the number of right answers?
Here is one possibility: the first person says the colour of the hat directly in front of him. So the second knows her hat colour, which she calls out. The third person then does the same favour for the fourth, and so on. This way, the team are guaranteed to get half the hats right. (We only care about guaranteed correct answers in this game, not lucky guesses.) In fact, there is a much better strategy. If you don’t know the answer, have a think about it now. The solution is on the other side of this picture.
And the answer is... Kurt Gödel and Albert Einstein play the hat game.
Now, this strategy allows everyone to discover their own hat colour, except for first the very first person. It is easy to see this is the best that can be done: no-one can see the first hat, so any tactic the team try will be immune to a change in its colour. To avoid this exception, in the next post we’ll assume the person at the head of the queue is hatless.
To set things up for the next post, I’ll write this another way, using “1” to represent black and “0” for white. So the sequence of hats might read 0010001111. The first person sees the whole sequence, adds up all the digits to get 5, and says “1”. (This is the total modulo 2, if you like.). The second person sees 010001111, and so on, with everyone seeing the same binary sequence, but with the beginning chopped off in different places.
I hope you agree that this hat game is a fun puzzle, with a neat answer. Its solution uses what computer scientists call a parity bit, a technique used to guard against data becoming corrupted.
In the next post things will become a little more serious, when we allow the queue of hat-wearers to grow infinitely long. In this new version, we have to assume that the hatters have various superpowers: they can see infinitely far in front of them, for example. It is obvious that the same tactic will not work in this setting, since everyone is likely to see infinitely many black hats in front of them (and of course it makes no sense to ask whether ‘infinity’ is odd or even). So what is the optimal result here, and what strategy will produce it? And, critically, what further superpowers do the people need to enact it?
Update: the second post is here.
In cricket, we usually compare batsmen by their averages, that is to say their mean scores over their careers (total runs scored divided by number of times out). On this measure, the best batsman of all time is Donald Bradman (pictured), with a test average of 99.94[1], miles beyond his closest rival, Graeme Pollock, on 60.97.
However, as every statistician knows, the mean of a set of data is very far from telling the whole story. The obvious next thing to do is calculate its standard deviation. This will describe how ‘spread out’ a batsman’s scores are.
What does this mean in sporting terms? It is something like measuring his consistency. But better batsmen (i.e. those with higher averages) have more ‘space’ to spread into, which will result in larger standard deviations. On this measure alone the ‘most consistent’ performers are likely to be the lowest average scorers (not very helpful).
To take this into account, Ric Finlay hs suggested scaling this down, defining a batsman’s consistency index as his standard deviation divided by his average. (Statisticians know this as the coefficient of variation.) In 20 odd years of following the game, I have never seen these sorts of statistics before.
The lists that Finlay produces are fascinating[2], but need to be treated with caution for various reasons: most obviously, they fail to distinguish between consistently good and consistently bad performances! Secondly, consistency is not necessarily a positive thing: if a batsman scores exactly 50 in nine innings and then 200 in his tenth, his average will improve but his consistency index will be damaged. But no-one would argue that the double-century makes him in any sense a worse player. What is more, not every batsman aims for consistency. Players with a more aggressive style deliberately take more risks than whose who play more safely and defensively. The pay-off is that they also score more quickly (if they don’t get out).
Nevertheless, with all these caveats, I think the data is very interesting. It seems clear that Bradman’s reputation is enhanced still further, as is that of his successor as Australian captain Ricky Ponting. Meanwhile Sachin Tendulkar and Brian Lara (usually considered the greatest batsmen of the modern age[3]) turn out to be more inconsistent in comparison.
Rather than work with standard deviations, cricketers more commonly talk about consistency in passing certain milestone scores: 1 (‘getting off the mark’, 10 (‘into double digits’), and so on. One of the most important stages is somewhere between 20-35, where a batsman is considered to have ‘settled in’. The idea is that even the best batsmen get out to low scores sometimes; a mark of quality is that once they have settled in, they then go on to compile big scores with great reliability. (The cricketing world could really do with a standardized numerical value here, unfortunately the decimal system fails to provide an obvious candidate.)
One common measure here is a batsman’s “conversion rate”, meaning the proportion of the times in which they score 50 that they go on to hit a century. Again, Bradman tops the table, with a conversion rate of 69.95%.
[1] Famously, Bradman only needed to make four runs in his final innings in order to achieve an average of 100, but was out for a duck.
[2] Though slightly out of date.
[3] And I’m not saying that this analysis necessarily contradicts that opinion!
Over on G+, Alexander Kruel pointed me towards an article by Alex Knapp entitled “Why your brain isn’t a computer”.
The point of this post is not to argue whether it is or it isn’t, but to draw attention to a salient point, which I think Alex waves away rather too quickly (and which in any case is important and interesting).
One might reason that there are plenty of different types of ‘computation’ around these days: ordinary computer programs, embedded systems, neural nets, self-modifying code, and so on. So, with all this variety, why should we expect that a human brain, being a neurochemical network, should fall into the same computational category as a laptop? Might it not simply be that the two have different capabilities? As Alex argues “Electric circuits simply function differently then electrochemical ones”.
The problem with this argument is that it overlooks the great robustness of the notion of computability, specifically the Church-Turing thesis.
A bit of history: in the 1930s, Alan Turing was investigating the capabilities of Turing machines, funny little devices which creep along a ticker-tape, and respond to the symbols they find there. Meanwhile over in the US, Alonzo Church was exploring the semantics of a formal system he had developed, called lambda calculus.
On first sight, the two topics appear to have little in common. But when the two men encountered each others’ work, they quickly realised something unexpected and profoundly important: that anything which can be expressed in lambda calculus can also be computed by a Turing machine, and vice versa. Shortly afterwards, a third approach known as recursion was thrown into the mix. Again, it turned out that anything recursive is Turing-computable, and vice versa.
This leads to the assertion we know as the Church-Turing thesis: that a process which is computable by any means whatsoever, must also be computable by a Turing machine.
It is important to stress that the Church-Turing thesis has good experimental support. Every computational system we know of obeys it: cellular automata, neural networks, Post-tag systems, logic circuits, genetic algorithms, string rewriting systems, even quantum computers*. Anything that any of them can do can (in principle) be done by conventional computational means.
So when Alex comments that “the brain itself isn’t structured like a Turing machine”, the obvious response is, “well, no, and neither are lambda calculus, cellular automata, and the rest”. (Come to think of it my phone doesn’t much look like a Turing machine either.)
The ‘dualism’ which distinguishes software from hardware (which Alex argues fails for the human brain), is not something built in from the outset. Rather it emerges from the deep, non-obvious fact that computational systems beyond a certain complexity can all emulate each other.
Needless to say, there have been no shortage of people claiming to have developed systems of different kinds which go ‘Beyond the Turing Limit’. (See Martin Davis’ paper on The Myth of Hypercomputation.) And who knows, maybe our brain embodies such a process. (I have my doubts, but if we’re going to find such a system anywhere, the brain is certainly an obvious place to look.)
The bottom line here is that if you don’t want to accept that
0) The human mind is computable
then I’d say you have three positions open to you:
1) It requires an extra metaphysical ingredient;
2) It’s a hypercomputer which violates the Church-Turing thesis;
3) It relies in an essential way on a non-computable process, meaning some inherent element of randomness.
Personally I’d order these 0312, in order of likeliness. (At the same time, I’d say talk of reverse-engineering the human brain is like a toddler planning a manned expedition to Mars. How about we concentrate on crossing the room without falling over first?)
*Quantum computers may be able to compute certain things quicker than conventional ones, but they won’t be able to compute essentially different things.
Nightjack was an award-winning blog which ran from 2008-2009, written by an anonymous British police officer. In 2009, in what they claimed to be the public interest – but which struck many observers as an exercise in needless spite – The Times newspaper published an article exposing the author as Detective Constable Richard Horton.
Since then there have been claims and counter-claims about how that story came to press, culminating in the recent revelation that the Times likely misled both the High Court and its own readers.
We now know how Times journalist Patrick Foster knew Nightjack’s identity: he hacked his email account. What is interesting – and where considerations of computational complexity come in – is what happened next. Having found Nightjack’s identity through illegal means, Foster then approached Times lawyer Alastair Brett, and was advised to set to work on reproving Nightjack’s identity, purely through legally available sources. He was indeed later able to do this, with the result that the Times went to court and successfully fought off an injuction barring them from exposing Nightjack. But, critically, during the hearing, they omitted all mention of the original email hack, and spoke solely of Foster’s subsequent reproof.
Brett explained the thinking behind this advice in his testimony to the ongoing Leveson enquiry into the culture, practices, and ethics of the press:
“If he or any other journalist could identify Nightjack through legitimate sources and information in the public domain then we’ve got what I felt was a perfectly legitimate public interest story…
“He had to demonstrate to me that he could do it legitimately from outside in, and that’s what he did. He persuaded me that he was able, that the only person who could have been Nightjack was DC Horton…
“Rightly or wrongly I had believed you could separate the earlier misconduct by Mr Patrick Foster and you could then say that once he had done this legitimately then that could be presented to the court perfectly properly as he had done it legally. Now I accept that you say that the two are inextricably intertwined, but that, if I may say so is a subjective judgement. I happened to take the view that you could separate out the one from the other.”
Robert Jay QC, cross-questioning, makes the observation that the reproof was “a much easier exercise”, now that he “had the advantage of knowing the answer to his question”.
Of course this is true, but one might ask how much of an advantage he had. Is this a subjective judgement? Perhaps Foster could have determined the answer, legally, from the outset. In order to have a leg to stand on, the minimum he needed to establish was that Nighjack’s identity was in legal P, something which could discovered legally in polynomial time. All the reproof showed, however, was that it was in legal NP (as well as being in illegal P, of course). Are the two equal…? (And if they are, what is the polynomial mark-up…?)
David Allen Green has been monitoring the case since the beginning, and it was he who likened the identification to solving a maze ‘from the inside out’ (P) rather than ‘from the outside in’ (NP). He has an excellent run-down of the whole affair so far, at The New Statesman. (If you scroll down to the discussion of Oliver Kamm’s blogposts, you will also see how the Times went on to mislead its readers.)
The latest developments are that the Times’ editor James Harding has written to the hearing’s original judge to apologise, and that Nightjack is suing the Times for breach of confidence, misuse of private information and deceit. He is claiming aggravated and exemplary damages.
You can also watch Alastair Brett’s very uncomfortable evidence to the Leveson enquiry here. It begins at 72′, and the real drama starts at 129′, in which Lord Leveson accuses the Times of providing ‘utterly misleading’ evidence to the Court, an accusation which Brett essentially admits.
Although the expedition was successful in its primary aim (they made it to the South Pole, gathering many scientific specimens along the way) it failed in two major respects: they were not the first to reach the Pole, finding on their arrival a tent left behind by Roald Amundsen‘s team. Secondly, Scott’s party never made it back.
One of the most famous episodes, documented in Scott’s diaries, took place on the disastrous return trip. With one of their party, Edgar Evans, already dead, the team’s progress was being slowed by another, Captain Lawrence Oates, who was suffering with severe frostbite and possible scurvy. As Scott wrote, “Oates’ feet are in a wretched condition… The poor soldier is very nearly done.”
Aware that he was holding his colleagues back, Oates suggested that they go on without him. They refused; so, on the morning of 16th March 1912, Oates’ 32nd birthday, he took matters into his own hands.
Leaving his boots behind, and uttering the famous words “I am just going outside and may be some time”, Oates stepped out of the tent into a blizzard, never to be seen again.
I have known the heroic tale of Captain Oates for as long as I can remember. What I did not know, until today, was that he lived around the corner from me, in what is now Meanwood Park in Leeds, and was then Meanwoodside, the Oates family estate. Today marks exactly 100 years since Oates ‘went outside’, so an exhibition was held in the park, and a commemorative blue plaque unveiled.
As well as being largley responsible for the park’s attractive appearance, the Oates family included at least one other explorer: Lawrence’s uncle Frank Oates, who explored Central America, before dying during an expedition to Africa. The Oates approach to life can perhaps be summed up by Frank’s saying:
“I like anything that seems difficult of attainment”.
I meant to post something about John Derrick, a long-standing and much loved member of the logic group at Leeds University, who died in December. I only knew John in his later years (some time after his official retirement), but would regularly see him at the Wednesday afternoon logic seminar, which was often followed by a trip to the pub. He was always a thoughtful and benevolent presence in the seminar room, and made for entertaining and knowledgeable company over a drink.
For younger members, he was also something of a link to an earlier era, the days when the group was led by Martin Löb (of Löb’s theorem fame).
It is a testamant to his strength of character, and his love of the subject, that he continued to attend and contribute to these seminars through many year of ill-health, up until only a few weeks before his death.
An obituary by Garth Dales appeared in the LMS news-letter and a longer one can be read on the University of Leeds website.
Simple City 