Boris
78
5
Boris has not written any posts yet.
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 machine M with less than 400 states,
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, and so did anger.
I liken this to classic studies on the effects of divorce on children. Of course,... (read more)
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, that BBB(N) is N+O(1)---is open. It is known that BBB(N) is O(N), and moreover, a 2002 paper "Improved Bounds... (read more)