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.There exists a constant C so that if you want to solve the halting problem for all Turing machines up to N states, you can use a particular Turing machine with N+C states. Moreover, this constant C is small (definitely less than 100). In other words, there exists a 500-state Turing machine that solves the halting problem for all the Turing machines up to 400 states.
Here's the algorithm: given as input a Turing m...
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,...
It's possible that anger was a byproduct of something else which is adaptive (certainly such evolutionary byproducts exist)... but it seems pretty unlikely in this case. Anger is a rather complicated thing that seems to have its own modular brain systems; it doesn't seem to be a byproduct of anything else.
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)