Hacker News new | past | comments | ask | show | jobs | submit login

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.




Alright, this is a good proof. I therefore concede the point regarding the values themselves.


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


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.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: