Finding BB(n) for all n is uncomputable. Finding BB(n) where n=10, say, is not uncomputable.
Yeah, this is an interesting point. My thinking is that yes, we do only care about modeling Turing machines that fit in the universe, since by definition those are the only Turing machines whose output we will ever observe. We might also have to bite the bullet and say we only care about predicting Turing machines which are small enough that there is room left in the universe for us; we don’t want to perfectly model the entire universe, just small parts.
If it’s uncomputable in general then it’s uncomputable for some particular n. I expect that in fact it’s uncomputable for any n above some rather small value. (In particular, once n is large enough for there to be n-state Turing machines that unprovably don’t always halt.)
Well, if you only care about predicting smallish Turing machines, then for the same reason prediction is only useful if it can be done with smallish machines, in reasonable time. And even for very small n this isn’t true for calculating BB(n).
Finding BB(n) for all n is uncomputable. Finding BB(n) where n=10, say, is not uncomputable.
Yeah, this is an interesting point. My thinking is that yes, we do only care about modeling Turing machines that fit in the universe, since by definition those are the only Turing machines whose output we will ever observe. We might also have to bite the bullet and say we only care about predicting Turing machines which are small enough that there is room left in the universe for us; we don’t want to perfectly model the entire universe, just small parts.
If it’s uncomputable in general then it’s uncomputable for some particular n. I expect that in fact it’s uncomputable for any n above some rather small value. (In particular, once n is large enough for there to be n-state Turing machines that unprovably don’t always halt.)
Well, if you only care about predicting smallish Turing machines, then for the same reason prediction is only useful if it can be done with smallish machines, in reasonable time. And even for very small n this isn’t true for calculating BB(n).
Just out of my own curiosity, I checked Wikipedia on Busy Beaver numbers: BB(10) > 3^^^3.
While the article admits that every finite sequence (such as n = 1...10) is computable, I think it is safe to call it intractable right now.
Hey, don’t laugh. That’s useful to know—now you know any Turing Machine less than 10 is bluffing when it threatens 3^^^^3 specks of sand in eyes.
Off the cuff, couldn’t it actually accomplish that if it just doesn’t terminate?
If it doesn’t terminate, then I think its threat would be an infinite number of sand specks, wouldn’t it?
How did you conclude that from a lower bound?
I don’t think the lower-bound will turn out to be all that off, and I tossed in another ^ as insurance. Jests don’t have to be air-tight.