Thursday, December 31, 2009

Hey it's new years. We made it all the way around again!

I'm still sitting here and again I'm trying hard to care that the year has come to an end. And this time even the decade is ending.

Nobody else seems to care about the end of this decade either. All of the "best of the decade" lists have come late, almost as an afterthought. I think that's because the decade has no name. Goodbye seventies, eighties, 20th century, ... now what? The BBC calls them "the naughties", but I think that's the disease I blamed for having caused me to steal all of the cookies (if you know what I mean) and have sex with them. No wait, I think the naughties were the villain in the pilot episode of the Teletubbies.

Anyway, I think "first ten years of the century" probably fits best. So, goodbye ftyotc. We hardly knew you.

Sunday, December 27, 2009

The Standard Halting Problem Proof has a Major Flaw

The halting problem: the problem of figuring out whether or not a program will halt (not run forever) based on a description of the program, its machine and the input.

The standard proof that this is not solvable boils down to the following:

Imagine you had a program that could solve this problem. You could easily modify it to, instead of saying "this program will halt", run forever if the in put program would have halted. You could run the program on itself. The result is that the program will halt if it doesn't halt and not halt if it halts: a contradiction. Therefore such a program cannot be made.

Simple and clever right? Well what if you wanted to know if a program would output "red" or "blue". This really can be accomplished very simply. No question about that. Well, what if you write a wrapper that outputs red if the input program would have output blue and blue if the input program would have output red. Now feed this program to itself. You get the same contradiction.

Thus the logical flaw in the standard halting problem proof is exposed. There isn't something special about a program that doesn't halt. It's a false logical trick.

It's sort of like using a compiler to compile itself.

Wednesday, December 16, 2009

I've been blogging for one year

In case I'm dead or something, don't worry. It's not a ghost or a hacker. I set this up months ago to post at this time.