alt Hacker NewsDoesn't the discovery of the fifth Busy Beaver value indicate that there is a decider for 5-state Turing machines?
Replies
orlp • yesterday at 5:05 PM
Yes. But there is no decider for n-state Turing machines that works regardless of n.
Doesn't the discovery of the fifth Busy Beaver value indicate that there is a decider for 5-state Turing machines?
Yes. But there is no decider for n-state Turing machines that works regardless of n.
Yes, there are deciders for all finite sets of TMs. You just cannot have one for all TMs.