Comment by mwenge
3 months ago
It is indeed proven and the reason they're called Turing machines! https://en.wikipedia.org/wiki/Halting_problem
3 months ago
It is indeed proven and the reason they're called Turing machines! https://en.wikipedia.org/wiki/Halting_problem
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".
2 replies →
Yes. But there is no decider for n-state Turing machines that works regardless of n.