4 ms·
It is indeed proven and the reason they're called Turing machines! https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
by mwenge 1y ago
It is indeed proven and the reason they're called Turing machines! https://en.wikipedia.org/wiki/Halting_problem https://en.wikipedia.org/wiki/Halting_problem
- webstrand 1y agoDoesn't the discovery of the fifth Busy Beaver value indicate that there is a decider for 5-state Turing machines?
- tromp 1y agoYes, there are deciders for all finite sets of TMs. You just cannot have one for all TMs.
- tialaramex 1y agoI 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".
- webstrand 1y agoThanks 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.
- tialaramex 1y agoThe suspicion is that this happens maybe as early as BB(15). We just can't prove that whereas we can prove BB(745) is not decidable, and, of course, we've decided BB(5) as we see here.
- orlp 1y agoYes. But there is no decider for n-state Turing machines that works regardless of n.