Comment by webstrand
3 months ago
Doesn't the discovery of the fifth Busy Beaver value indicate that there is a decider for 5-state Turing machines?
3 months ago
Doesn't the discovery of the fifth Busy Beaver value indicate that there is a decider for 5-state Turing machines?
Yes, there are deciders for all finite sets of TMs. You just cannot have one for all TMs.
I think actually for relatively small n we get cases where mathematics says nope, you can't decide that, the machine goes recursive and so now your decider may be looking at a machine which is itself running deciders and Kurt Gödel says "No".
Thanks for the hint to go looking some more. I found that Johannes Riebel has proven that BB(748) is undecidable. So for even small k there may not be deciders for them.
1 reply →
Yes. But there is no decider for n-state Turing machines that works regardless of n.