Posts Tagged ‘lawl’

Count von Count vs. Cantor

Saturday, November 28th, 2009

A combination of an incidental argument over whether the cast of Sesame Street or the Muppet Show would win in a fight and reading about Internet crazy people refusing to believe the uncountability of the real numbers lead to this. I hope you like math.

So we know that Count von Count (colloquially known as The Count) loves counting. According to Wikipedia, he will count anything and everything, regardless of size, amount, or annoyance he causes everyone else. The logical question would be, what happens when we present The Count with an uncountable set like the set of real numbers, ℝ (unless you are a crazy person)? Can he count it?

The answer is of course he can, he’s the goddamn Count.

What are the implications? Basically, The Count can enumerate any set, whether it’s uncountable or not. This means that to The Count, every set is recursively enumerable. This means that for every set S, S and its complement S’ are recursively enumerable. But this means that every set S is recursive.

So, now we consider the halting set H = { (P, w) : program P halts on input w ∈ Σ* }. From above, we have that H is recursive (since H’ is recursively enumerable). But this means that H is decidable. This means that The Count can decide the Halting Problem, and thus, can decide any undecidable problem.

What we conclude is that The Count’s power isn’t to count, but is, in fact, to break logic.