I do not pretend that I’m not a computer geek – but I am a mobile phone Luddite. Recently though, I got a shiny new one which can take pictures. Here is one of the Highgate ponds on Hampstead Heath (with a little bit of fiddling in photoshop to improve the contrast):
London’s not such a bad place after all… especially when you realise that within 10 minutes walk of this spot there are at least 3 different places to get excellent cake. Take that, countryside!
Filed under: Mathematics
I’ve had this sitting around for a while. Harvey Friedman wrote a new proof of Godel’s theorem on the FOM mailing list. I’m writing this entry so that I have a reminder of it for myself, but others might find it interesting too.
Intuitively speaking, Godel’s theorem says that every mathematical system has statements which are true but can’t be proved within that system. The normal way to think of this is that you can’t prove the statement “This statement cannot be proved” but nonetheless it’s true. You can’t prove it because if you could it would be true, and then it would say that you couldn’t prove it which would be a contradiction. But it must be true, because if it was false then there would have to be a proof of it, and so it would have to be true, which is a contradiction. This might seem reminiscent of the paradoxical sentence “This sentence is false”, but there is a subtle difference which I probably don’t want to go into in too much detail here. (The difference between truth and provability.)
Friedman’s proof uses Turing machines. Without going into any technical details – a Turing machine is basically just a computer program. A computer program can be represented as a single number. Just take the file on your computer; it’s a string of 1s and 0s, which is just a (very large) number in binary. So we can number every possible computer program. Write TM[n] for the computer program whose corresponding number is n. Actually, I’m going to restrict myself to computer programs which take one input (say the number m), and return one output. Given some computer program and an input m, the program may never stop running. For example, the program
never stops running. The custom when talking about Turing machines is to say that the program doesn’t halt.
So here is Friedman’s proof. We write a computer program P that does the following: Given an input m, it searches for a proof that “TM[m] does not halt when given input m”. That is, it searches for a proof that program m, when given input m, will eventually stop running and return some number. If there is a proof, then P will eventually find it, otherwise P itself will not stop running.
Here’s where it gets clever. The program P is itself just a computer program that takes a single input m, and so it must have a number, call that number k. In other words, P=TM[k] for some number k. Keep that in mind.
So what happens if we run program P with input k? We can work this out by considering two alternatives. Either there is or isn’t a proof of the statement “TM[k] does not halt when given input k”. If there is a proof then running program P with input k will find the proof, and therefore this program halts at input k. But we’re assuming that there is a proof that “P=TM[k] does not halt at input k”, so this is a contradiction.
Therefore, there is no proof that “TM[k] does not halt at input k”, but nonetheless it is true.
If you want to know more (that’s just a very sketchy and technically inaccurate overview), then take a look at Harvey’s message to FOM above. If you want to understand it but can’t (e.g. you might ask yourself having read it: what is PA and what is Con(PA)?) , just post a message here. If you found it interesting, you might also be interested in reading up on The Halting Problem (which is closely related).
Filed under: Politics
In a previous entry I asked if the Labour party could get my vote, and suggested some policies they would have to change to do so. My motivation for doing so was not purely narcissistic, it’s a way of making myself think about electoral politics. I quipped that my plan was not very electable, but actually that’s not good enough. Why isn’t it and what can be done about it?
So, some ideas about how to present the policies I suggested (this entry should be read in conjunction with my previous one):
- Civil liberties: the present government portray anti-terrorism measures as necessary to combat the extreme danger of terrorism. This can be countered by pointing out that the threat of terrorism is considerably less than it is portrayed to be and that the government’s measures are incredibly wasteful and expensive. The ID card system will cost between £5bn and £20bn over 10 years and not be of much use. The CCTV network around the country is very expensive (3/4 of the Home Office crime prevention budget, totalling hundreds of millions of pounds), and according to the government’s own research doesn’t actually prevent crime. Why are we paying for this when that money could be so much better spent elsewhere?
- Democracy: I don’t think it’s that hard to sell the idea of democratic reform, but introducing state funding for political parties might be difficult to justify. Limiting spending though, as Brian suggested in the comments to my previous entry would have many of the same effects and be relatively easy to justify.
- Immigration: more complex, not something I know enough about to make any coherent suggestions.
- Economics: Convincing people that progressive taxes like income tax are better than flat or regressive taxes like VAT and council tax seems to be more difficult than you might think. I don’t have anything to add. On the other hand, I think it would be fairly easy to make a convincing case that market fundamentalism ends up costing us more because when the private sector fails the government bails them out.
- Environment and transport: this is tricky because it might involve an awful lot of spending and there really is a necessity for people to lower their energy consumption which is never going to be an easy sell.
- Public sector: I find it perplexing that the well-being of public sector workers is such a low priority in electoral politics. There’s lots about making the public sector more efficient, delivering better outcomes, etc., but these are often at the expense of public sector workers themselves. The National Statistics web page says that about 1 in 5 workers are in the public sector, which ought to be significant enough to warrant more attention than they actually get. Perhaps this is because in a two party system, policies tend to be aimed at improving the lot of the median voter, who is perhaps not a public sector worker?
In conclusion, I don’t think it would be impossible to run an electoral campaign on some of these ideas. You would probably have to make difficult compromises in some areas, and make some unpalatable decisions, but I don’t think you have to go as far to the right as New Labour has done.
Two unconnected articles that might be of interest.
The first from The Register:
According to figures from German scientific think-tank the Max Planck Society, Italy leads the world with 76 intercepts per 100,000 head of population, shortly ahead of the Netherlands (62), and with third-placed Sweden some way back (33). Germany comes in fourth with 23.5 intercepts per 100,000 head of population with England and Wales trailing on six intercepts per head of population.
The second from The New Standard:
Every year since 1989, members of Congress have pushed for a study into how the US might atone for slavery, its aftermath and legacy. And every year, the white majority says the subject is off limits.
The Labour party really couldn’t give a shit about my vote, and my opinion of the Labour party is that it is a lost cause. Left-thinking people of good conscience should not be supporting a party that does not and likely will not represent their views. But it’s an interesting question to ask what sort of Labour party we would like to see. In response to the wholly uninteresting Milburn-Clarke ‘open debate‘ on Labour’s future, Brian Barder has written an interesting 10-point plan for Labour.
To get me to vote Labour, they would have to do at least some of the following (in no particular order, and by no means a comprehensive list):
- Civil liberties: abandon the ID card scheme, detention without trial, etc. More positively: ensure that all government institutions are designed so as to make it as difficult as possible for future less libertarian governments to misuse them.
- Democracy: reverse the control-freakery of the current government, their plans to introduce legislation bypassing parliament, etc. Instead, introduce voting and political funding reform including proportional representation and equal state funding for political parties above a (low) minimum size.
- Immigration: behave in a civilised way, not in a Daily Mail way.
- Economics: favour positive rather than regressive taxes (including flat taxes). Don’t make it axiomatic that the private sector is more efficient. Consider implementing some institutions that are decentralised but not market-based, as in parecon.
- Environment and transport: prioritise the construction and improvement of environmentally friendly forms of transport as a matter of urgency! Tinkering around with marginal incentives won’t do the trick.
- Public sector: reforms should be designed to improve the lives of public sector workers as well as improving the efficiency and effectiveness of institutions.
Yeah my plan’s probably even less electable than Brian’s. Not all of it has to be though. The major obstacles would probably be immigration (because ours is a very xenophobic country) and taxation (something that is very difficult to sell as being positive, and understandably given some of the stupid stuff governments spend money on).
I should probably include something about crime and foreign policy in there too, but it’s late and I’m tired. Now who wants to be the first to tell me that my ideas are idealistic and unworkable?