3 ms·
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 phon
by camccann 17y ago
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...
- gwern 17y agoWell, here's another approach. We can solve the halting problem for any finite TM (http://portal.acm.org/citation.cfm?id=1052796.1052798 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.