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