3 ms·

Sorry, you are wrong here. We may never solve BB(6) exactly because of undecidability. We don't have an algorithm for computing BB(6). If we had one, BB(6) woul

Sorry, you are wrong here. We may never solve BB(6) exactly because of undecidability. We don't have an algorithm for computing BB(6). If we had one, BB(6) would be computable (= decidable). Of course, as soon as we know BB(6) = n, for some numeric literal n, it is trivially clear that BB(6) is computable/decidable: function BB(k) { if (k === 6) return n; } Granted, we don't know if BB(6) is decidable or not, because we don't know if there are proofs in reasonable axiomatic theories which show for each of the 6-state TMs which don't halt that they don't halt. That there are only finitely many such TMs does not really matter here. For something like BB(3) there are only 21 TMs, so we can try our luck to prove that those TMs which don't seem to halt actually don't halt, and hey, we got lucky, we can! Nobody knows if we have the same kind of luck for BB(6). Indeed, for BB(745) we know that at least for ZFC, we don't have this kind of luck. Of course, if we knew BB(745) = n, for some numeric literal n, then in ZFC + {BB(745) = n} we have that BB(745) is decidable, but if you don't like logical tricks, then you won't like that result too much, either. The fact that BB(745) is undecidable in ZFC doesn't mean that it will stay unknown forever. But we will have to come up with some other mathematical explanation than ZFC to know BB(745), and nobody knows if such an explanation exists. It could also be that you come up with such an explanation, but many others don't agree with it. Now, on which grounds would you defend your explanation? But I am a Platonist, so I do agree with you that there is some sort of mathematical explanation for BB(745) = n for some n formulated in a suitable mathematical theory. Because obviously, such an n must exist. Because TMs are real, and they either halt or they don't (Platonist leap of faith I). And then there must be a way to explain why that is (Platonist leap of faith II). But it may be that we never find such an explanation, and/or that humans are too limited to understand the explanation. Certainly, there is no known general algorithm to find human-understandable answers to all human-understandable mathematical questions, and that's why undecidability is the reason we may never know BB(6).

srcreigh 3y ago
I believe we are in agreement about everything. I just would not say that undecidability is the reason why we can't solve BB(6), it would be some reason such as you mention (unable to prove 6-state machines halt). In jest. If I am lacking a source of heat, the reason for my being unable to cook food isn't my lack of Superman heat vision eye laser beams. Similarly, the fact that we can never skip all of math with one finite algorithm isn't the reason why we can't discover BB(6). In any case, at a Platonic level there is no such algorithm, so us lacking it can't be the reason why we can't solve BB(6). In a way it's even less realistic than Superman heat vision eye laser beams.

srcreigh 3y ago

I believe we are in agreement about everything. I just would not say that undecidability is the reason why we can't solve BB(6), it would be some reason such as you mention (unable to prove 6-state machines halt). In jest. If I am lacking a source of heat, the reason for my being unable to cook food isn't my lack of Superman heat vision eye laser beams. Similarly, the fact that we can never skip all of math with one finite algorithm isn't the reason why we can't discover BB(6). In any case, at a Platonic level there is no such algorithm, so us lacking it can't be the reason why we can't solve BB(6). In a way it's even less realistic than Superman heat vision eye laser beams.