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.
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.