Boris

Oops, I mis-stated the result. If we fix a universal Turing machine (equivalently, a programming language), then there exists a constant C so that deciding the halting problem for programs of length less than N can be done by a program of length less than N+C. Pengvado's solution works here.

Unfortunately, as Richard observed, you can't do this with Turing machines, essentially because Turing machines can not inspect their own finite control, unlike the stored program on a von Neumann machine. In fact, it appears that my claim---in Richard's notation, th... (read more)

I would drop dead of shock if there were a 500-state Turing machine that solved the halting problem for all the Turing machines up to 50 states.

Here's the algorithm: given as input a Turing m... (read more)

Eliezer, thank you very much for all of these posts. I believe that this post is an excellent way of presenting them all in a reasonable sequence.

Why doesn't someone make some circular sunglasses that have two polarized disks that you can rotate with respect to each other?

You say "the neural circuitry of anger is a reproductive organ as surely as your liver" and "the evolutionary purpose of anger is to increase inclusive genetic fitness."

I don't believe you have enough evidence to assert these statements. All you know is that "angry ancestors had more kids" but you DON'T know that it's as a result of the anger. It could have happened that, say, the same ancestors that could run faster also happened to have the capacity for anger. As a result of their faster running, they reproduced/survived,... (read more)