BB(3, 3) is Hard
sligocki.com
BB(3, 3) is Hard
1–10 of 146 posts
Re: BB(3, 3) is Hard
#2Pretty good writeup.
Re: BB(3, 3) is Hard
#3[dead]
Re: BB(3, 3) is Hard
#4I appreciate the authors writing style. It helped me understand the subject without seeming verbose. That sweet spot can be difficult.
Re: BB(3, 3) is Hard
#5Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
Re: BB(3, 3) is Hard
#6Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
If BB is a computable function, then you can solve the halting problem by running every turing machine with n states for BB(n), and the ones that don't halt by then don't halt at all.
Re: BB(3, 3) is Hard
#7Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
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)...
Re: BB(3, 3) is Hard
#8I have always been curious about BB but never saw Scott Aaronson's survey of the topic. Link within.
Re: BB(3, 3) is Hard
#9Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
Sort of. Uncomputable functions exist because the halting problem exists. So any function whose definition includes anything to do with halting also becomes uncomputable. e.g. BB is uncomputable because you have to determine all the TMs that would halt given n and m.
The entire rest of mathematics is smuggled into BB via the halting problem: you can write programs that only halt if arbitrary mathematical conjectures are true or false, so anything that wants to solve the halting problem or solve BB has to be able to know all maths[0]. Of course, this is possible because Turing-completeness is the boundary of computability. Anything that can have a computer in it is itself a computer.
[0] This isn't actually the thing that makes halting undecidable. Undecidability comes from programs that "pull themselves into the halting problem" by only halting if a hypothetical halting problem decider would claim that they don't halt.