3 ms·
Sort of. There are math problems that we "know" we can't prove or disprove, unless we can prove every statement both true and false (this is Godel's first inco
by gpm 3y ago
Sort of.
There are math problems that we "know" we can't prove or disprove, unless we can prove every statement both true and false (this is Godel's first incompleteness theorem). If we can prove every statement both true and false then our proof system just sucks and proving something means nothing so we should choose another proof system where that's not the case, so we assume we're in the first case (there are math problems that we know we can't prove or disprove). Incidentally Godel's second incompleteness theorem is that we can't ever prove we are in the first case.
And then ya, BB being incomputable means that as BB grows at some point they start to be able to encode programs that halt if and only if a problem we can't prove or disprove is true. So we can't prove that program does or doesn't halt.
Now, technically, proving/disproving something you can't prove or disprove would be proving false, which in turn could be used to "prove" every statement, and would therefore "encompass all maths", so what you said is in a sense correct. It's a threshold condition though, and one that kicks in well before you have turing machines large enough to encode "every" math problem. And in fact there is no finite number of states sufficient to encode every math problem (I can just make longer and longer strings of arithmetic for instance)...
- pjot 3y agoSo is this (BB) then just an exercise demonstrating our inability to reasonably solve the problem? I suppose what I’m asking is what is its significance? Or why does this matter? As a self taught programmer, I realize I have definite gaps in the more theoretical realms of computer science.
- gpm 3y agoThe collatz conjecture isn't a problem that we think is unsolvable, it probably (maybe even definitely?) has a solution. It is a problem that a lot of really good mathematicians have sunk a lot of time into and made basically no progress. Collectively the mathematical community has more or less decided that we don't know how to even approach solving this kind of problem yet, and probably won't be able to solve it in the foreseeable future. This article is saying that solving for BB(3, 3) requires solving a collatz-conjecture like problem, so it's probably also beyond our current abilities in mathematics. It's not saying it's unsolvable, just that we probably won't figure out the solution anytime soon. As for why solving BB(3, 3) matters... it doesn't really. It's just an intellectual curiosity. We've figured out some busy beaver numbers. We've proven some upper bounds on the biggest ones we can figure out, but there's a big gap between what we've solved and what we've shown we can't solve for. Making that gap smaller is something of a game.
- pjot 3y agoGot it. Thanks for adding context!
- sligocki 3y agoThe Busy Beaver problem sits somewhere on the range from "intellectual curiosity" to "lens that allows us to view the edges of uncomputability". I would guess that the majority of people doing work here are hobbyists (including myself). In fact, when Tibor Rado first introduced BB, he introduced it as the "Busy Beaver Game", so it has had a playful energy since the beginning :)