gjm comments on Frequentist Magic vs. Bayesian Magic - Less Wrong

41 Post author: Wei_Dai 08 April 2010 08:34PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (79)

Sort By: Best

You are viewing a single comment's thread. Show more comments above.

Comment author: gjm 13 April 2010 12:52:38AM 1 point [-]

The fact that BB(n) is uncomputable means that your procedure doesn't, in fact, work. No?
You don't, in any case, have a fixed n. (Unless perhaps you are only interested in modelling Turing machines that fit in the universe -- but in that case, wouldn't you also want your own computations to fit in the universe?)

Comment author: gwern 13 April 2010 01:16:30AM 1 point [-]

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.

Comment author: gjm 15 April 2010 08:00:52PM 2 points [-]

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).

Comment author: RobinZ 15 April 2010 08:28:46PM * 1 point [-]

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.

Comment author: gwern 15 April 2010 10:11:10PM 2 points [-]

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.

Comment author: JGWeissman 15 April 2010 11:46:24PM 1 point [-]

now you know any Turing Machine less than 10 is bluffing when it threatens 3^^^^3 specks of sand in eyes.

How did you conclude that from a lower bound?

Comment author: gwern 16 April 2010 02:17:44AM 2 points [-]

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.

Comment author: thomblake 15 April 2010 10:30:52PM 1 point [-]

Off the cuff, couldn't it actually accomplish that if it just doesn't terminate?

Comment author: gwern 15 April 2010 11:38:28PM 1 point [-]

If it doesn't terminate, then I think its threat would be an infinite number of sand specks, wouldn't it?