Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
[deleted]
BB(3, 3) is Hard
11–20 of 146 posts
Re: BB(3, 3) is Hard
#12Is 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 mat…
So 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.
Re: BB(3, 3) is Hard
#13Earlier quoted context omitted.
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 mat…
So 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.
The 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.
Re: BB(3, 3) is Hard
#14`1RB2RA1LC_2LC1RB2RB_---2LA1LA` - how do I read this?
Re: BB(3, 3) is Hard
#15`1RB2RA1LC_2LC1RB2RB_---2LA1LA` - how do I read this?
It is a state transition table, the expansion is featured in the article right under it, or here
https://bbchallenge.org/1RB2RA1LC_2LC1RB2RB_---2LA1LA
For example: If in state B and the tape at the current marker reads 0: write 2, move the head Left once, and go to state C.
Re: BB(3, 3) is Hard
#16Earlier quoted context omitted.
So 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.
The 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…
Got it. Thanks for adding context!
Re: BB(3, 3) is Hard
#17`1RB2RA1LC_2LC1RB2RB_---2LA1LA` - how do I read this?
Click on the link in the article [0] and you'll get a page that expands it to a human readable table. Each current (state, tape value) pair maps to a (new tape value, direction to move tape head, new tape value) triple.
Re: BB(3, 3) is Hard
#18Is this what we mean when we says BB are uncomputable? That as BB grows they incompass all of maths, requiring us to prove everything?
Greatly simplifying, the most important result in comparability is “the halting problem”, which means we have no way of telling, for any program, if given some input it will halt or run forever.
After that, it’s not surprising there is some BB we can’t solve, and it’s interesting to investigate which we can, and can’t, solve.
Re: BB(3, 3) is Hard
#19`1RB2RA1LC_2LC1RB2RB_---2LA1LA` - how do I read this?
There is a more readable state table but each underscore separates a group of transitions for one symbol, writen as groups of 3 characters for each symbol. These are the symbol to write, new state and direction to move. The --- state halts.
Re: BB(3, 3) is Hard
#20Probably more accurate to say that BB(3, 3) looks hard; that is, it encodes a Collatz-type problem, and many Collatz-type problems are very hard to solve (including, of course, the classic Collatz conjecture).
However, this instance might not necessarily be hard. For one, the behaviour seems to be heavily biased; for another, we only have to consider a single trajectory instead of the trajectories for all integers (as with the classic Collatz problem).