And now, for your entertainment, a bad math quickie.
I live in New York. ’round here, we’ve got a somewhat peculiar feature of how we run our elections. A single candidate can run for office on behalf of multiple parties. If they do, they appear on the ballot in multiple places – one ballot line for each party that they represent. When votes are tallied, if the candidate names for two different ballot lines match exactly, then the votes for those two lines are combined.
The theory behind this is that it allows people to say a bit more with their votes. If you want to vote for the democratic candidate, but you also want to express you preferences for policies more liberal than those of the democratic party platform, you can vote for the democrat, but do it on the liberal party line instead of the democratic party line.
In practice, what this means is that we’ve got lots of patronage parties – that is, lots of small parties which were set up by a small group of people as a way of making money by, essentially, selling their ballot line.
One thing we hear, election after election, is how terribly important these phony parties are. This year, we keep on hearing, over and over, how no Republican has won a statewide election since 1975 without the backing of the Conservative party! Therefore, winning the backing of the Conservative party is so very, very important!
This is, alas, a classic example of the old problem: correlation does not imply causation. The Republicans don’t lose elections because they don’t have the backing of the Conservative party: the Conservative party always backs the republican candidate unless it’s completely clear that they’re going to lose.
Between work, trying to finish my AppEngine book, and doing all of the technical work getting Scientopia running smoothly on the new hosting service, I haven’t had a lot of time for writing new blog posts. So, once again, I’m recycling some old stuff.
It’s that time again – yes, we have yet another wacko reinvention of physics that pretends to have math on its side. This time, it’s “The Electro-Magnetic Radiation Pressure Gravity Theory”, by “Engineer Xavier Borg”. (Yes, he signs all of his papers that way – it’s always with the title “Engineer”.) This one is as wacky as Neal Adams and his PMPs, except that the author seems to be less clueless.
At first I wondered if this were a hoax – I mean, “Engineer Borg”? It seems like a deliberately goofy name for someone with a crackpot theory of physics… But on reading through his web-pages, the quantity and depth of his writing has me leaning towards believing that this stuff is legit. (And as several commenters pointed out the first time I posted this, in Germany, you need a special license to be an engineer, and as a result, “Engineer” is actually really used as a title. Still seems pompous to me – I mean, technically, I’m entitled to go around calling myself Dr. Mark Chu-Carroll, PhD., but I don’t generally do that.)
Between work, trying to finish my AppEngine book, and doing all of the technical work getting Scientopia running smoothly on the new hosting service, I haven’t had a lot of time for writing new blog posts.
But in the process of doing my technical work around here, I was browsing through some archives, and seeing some of my old posts that I’d forgotten about. And odds are, if I forgot about it, then there are a lot of readers who’ve never seen it. So I’m going to bring back some of the classic old material.
For example, Neal Adams. Comic book fans will know about Neal: he’s a comic book artist who worked on some of the most famous comics in the 1970s: he drew Batman, Superman, Deadman, Green Lantern, the Spectre, the X-men. More recently, he’s done a lot of work in general commercial art – for example, he did the animated nasonex bee commercials a few years ago.
But he’s not just an artist. No, he’s so much more than that! He’s also a brilliant scientist. He’s much smarter than all of those eggheads with college degrees. They’re struggling to build giant particle accelerators to help understand things like mass. But Neal – he’s got them beat. He’s figured out exactly how things work!
According to Neal, there is no such thing as gravity – it’s all just pressure. People trying to figure out stuff about how gravity works are just wasting time. The earth (and all other planets) is actually a matter factory – matter is constantly created in the hollow center of the earth, and the pressure of all the new matter forces the earth to constantly expand. The constant expansion creates pressure on the surface as things expand – and that constant expansion is what creates gravity! You’re standing on a point on the surface of the earth. And the earth is expanding – the ground is pushing up on you because of that expansion. You’re not being pulled down towards the earth: the earth is pushing up on you.
And according to Neal, the best part is the math works!. In the original version of this post, I had a link to Neal’s page with his explanation of how the math works – but he has, since then, moved most of his science stuff behind a paywall – you now need to pay Neal $20 to get to see his material, so I can’t provide a direct link. But it’s in a video here, and you can see the original using the Wayback Machine.
Some people expressed interest in seeing a full-out, formal presentation of the Halting problem proof. So, I’m going to walk through it. There are actually a lot of different versions of this proof; the one that I’m going to use is based on the one used by my grad-school theory professor, Dr. John Case. To be clear, I’m doing it from memory, so any errors are completely my own fault, not John’s!
To start off, we need to define what a computing device is. In formal mathematical terms, we don’t care how it works – all we care about is what it can do in abstract tems. So what we do is define something called an effective computing device. An effective computing device is any Turing equivalent computing device. An ECS is modelled as a two parameter function . The first parameter is an encoding of a program as a natural number; the second parameter is the input to the program. It’s also a natural number, which might seem limiting – but we can encode any finite data structure as an integer, so it’s really not a problem. The return value is the result of the program, if the program halts. If it doesn’t halt, then we say that the pair of program and input aren’t in the domain of . So if you wanted to describe running the program “” on the input 7, you’d write that as . And, finally, the way that we would write that a program doesn’t halt for input as .
So now we’ve got our basic effective computing device. There’s one thing we still need before we can formulate the halting problem. We need to be able to deal with more parameters. After all – a halting oracle is a program that takes two inputs – another program, snd the input to that program. the easiest way to do that is to use something called a pairing function. A pairing functions is a one-to-one function from an ordered pair to an integer. There are lots of possible pairing functions – for example, you can convert both numbers to binary, left-pad the smaller until they’re equal length, and then interleave the bits. Given (9,3), you convert 9 to 1001, and 3 to 11; then you pad 3 to 0011, and interleave them to give you 10001011 – 139. We’ll write our pairing function as angle brackets around the two values: .
With the help of the pairing function, we can now express the halting problem. The question is, does there exist a program , called a halting oracle, such that:
In english, does there exist a program such that for all pairs of programs p and inputs i, the oracle returns if halts, and 0 if it doesn’t?
Time, finally, for the proof. Suppose that we do have a halting oracle, O. That means that for any program and input , .
So, can we devise a program $p_d$ and input where ,
Of course we can. We need a which takes two parameters: an oracle, and an input. So it should be really simple right? Well, not quite as easy as it might seem. You see, the problem is, needs to be able to pass itself to the oracle. But how can it do that? A program can’t pass itself into the oracle. Why not? Because we’re working with the program as a Gödel number – and a program can’t contain its own Gödel number. If it contained it, it would be larger than itself. And that’s rather a problem.
But there’s a nice workaround. What we care about is: is there any combination of program and input such that will incorrectly predict the halting status? So what we’ll do is just turn into a parameter to itself. That is, we’ll look at a program like the following:
(oracle, program) = unpair(input)
if oracle(program, input):
Then we’ll be interested in the case where the value of the program parameter is a Gödel number of the deceiver itself.
(As an aside, there are a variety of tricks to work around this. One of the more classical ones is based on the fact that for any given program, , there are an infinite number of versions of the same program with different Gödel numbers. Using that property, you can embed a program into another program . But there are a few other tricks involved in getting it right. It’s not simple – Alan Turing screwed it up in the first published version of the proof!)
Now, when input = , then will make the wrong prediction about what will do. So – once again, we’re back where we were in the simpler version of the proof. A halting oracle is a program which, given any pair of program and input, will correctly determine whether that program will halt on that input. We’re able to construct a pair of program and input where the oracle doesn’t make the right prediction, and therefore, it isn’t a halting oracle.
This version is more abstract, but it’s still got that wonderfully concrete property. Even in the most abstract way of talking about a computing device, if you’ve got something that you believe is a halting oracle, this shows you how to create a program that will prove that the halting oracle is wrong. So you can’t possibly create a halting oracle.
And to be extra clear: this doesn’t rely on any ambiguities about definitions, or any distinction between values and meanings. It shows a way of producing a real, concrete counterexample for any purported halting oracle. No trickery, no fudging – if you think you have a halting oracle, you’re wrong, and this proof shows you exactly how to create a program that will demonstrate that.
One of the long-time cranks who’s commented on this blog is a bozo who goes by the name “Vorlath”. Vorlath is a hard-core Cantor crank, and so he usually shows up to rant whenever the subject of Cantor comes up. But last week, while I was busy dealing with the Scientopia site hosting trouble, a reader sent me a link to a piece Vorlath wrote about the Halting problem. Apparently, he doesn’t like that proof either.
Personally, the proof that the halting problem is unsolvable is one of my all-time favorite mathematical proofs. It’s incredibly simple – just a couple of steps. It’s very concrete – the key to the proof is a program that you can actually write, easily, in a couple of lines of code in a scripting language. And best of all, it’s incredibly profound – it proves something very similar to Gödel’s incompleteness theorem. It’s wonderful.
To show you how simple it is, I’m going to walk you through it – in all of its technical details.