News for hackers. Stuff that matters.
Re:The Busy Beaver Problem by camccann on Thursday October 29, 2009 @04:28PM (#910827)
Consider a Turing machine M1 of size X that, given an input value n, calculates a function f(n) such that O(f(n)) > O(BB(n)) and halts.

Consider a Turing machine M2 of size Y that calculates a number A and halts, where X + Y < A.

Combine the two machines, using the number calculated by M2 as the input for M1. The resulting Turing machine of size X + Y calculates a value f(A) such that f(A) > BB(A) > BB(X + Y) and then halts. This contradicts the definition of BB(X + Y), therefore no such computable function f can exist.

Re:The Busy Beaver Problem by amalcon on Thursday October 29, 2009 @04:56PM (#910893)
Alright, this is a good proof. I therefore concede the point regarding the values themselves.
Re:The Busy Beaver Problem by camccann on Thursday October 29, 2009 @05:51PM (#910998)
It's more of a proof sketch, really--there's a few unexamined assumptions in there. It was the best I could do off the top of my head and typing on a smart phone, but I'm reasonably confident that the overall structure is valid.

I was actually kinda hoping someone who knows more than I do would chime in and clarify things...

Re:The Busy Beaver Problem by gwern on Friday October 30, 2009 @06:26PM (#912928)
Well, here's another approach. We can solve the halting problem for any finite TM (http://portal.acm.org/citation.cfm?id=1052796.1052798), so let's imagine we're looking at a possible BB, n. All we have to do is run all the possible programs, and see whether of the halting ones, one is bigger than n.