Posts
Comments
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 for Functions Related to Busy Beavers" by Ben-Amran and Petersen showed that BBB(N) is N+o(N). I haven't found better results, but on the off-chance that I do, I'll post another comment here.
Now, because my claim is open, we still have to check if Eliezer's original intuition (that 500-state Turing machines can't solve the halting problem for 50-state ones) holds up. Luckily for me, it doesn't. It's known that BBB(N) is less than 3N+6 (that's the O(N) result above), so at worst, there exists a 500-state Turing machine that solves the halting problem for 100-state ones. This is less impressive than what I originally claimed, because it's off by a multiplicative constant rather than an additive one, but it still does the trick.
What's the moral here? I think it's that you really should define Kolmogorov complexity in terms of the number of bits in the shortest program doing whatever you're analyzing, as is standard, rather than the number of states in a Turing machine. Indeed, this is how Eliezer defines it in this post; furthermore, Eliezer alludes to it when he responds to my post by mentioning a "500-bit Turing machine" [emphasis mine]. Only in the aside beginning "I would drop dead of shock" was the number of states actually mentioned.
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,
- Compute a number k greater than BB(400).
- Simulate M for k steps.
- If it halts by then, then output "M halts". If it doesn't, then output "M doesn't halt".
Correctness proof: If it halts in less than k steps, then obviously it halts. If it doesn't, then by the definition of BB(400), it never will.
Analysis of number of states: This is possible with 400+C states because you use about 400 states for step 1, and a constant number of overhead states for simulating Turing machines. Because there exist universal Turing machines with less than 25 states, you can arrange for C to be less than 100.
There's a small amount of subtlety in actually doing step 1. Let me know if you want more detail. However, I believe the overall result and method should be clear; moreover, I hope the result is unsurprising once you see the method. As such, please don't drop dead of shock.
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, kids end up worse off with parents that divorce, but all else equal, divorce may very well be GOOD for the kid. Similarly, although here angry ancestors did have more kids, anger may very well be BAD for reproduction/survival. I'm sure there's also a good cynical example, too, like that the reason the dollar was the dominant currency through the 20th century was because it was green.