News for hackers. Stuff that matters.
Re:The Busy Beaver Problem by amalcon on Thursday October 29, 2009 @02:44PM (#910563)
Yeah, that's a good one. The only complaint I have is that it contends that the Busy Beaver numbers grow faster than any computable sequence, but what it actually shows is that no computable sequence can be proven to grow faster than the Busy Beaver numbers. If a sequence happens to grow faster than the Busy Beaver sequence, but we can't prove it, then it doesn't help us prove anything about Turing machines.
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.