Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Graham's number is big, sure. But in a similar duel[1] between two MIT professors, they settled on this number: β€œThe smallest number bigger than any number that can be named by an expression in the language of first order set-theory with less than a googol (10^100) symbols.” Try and beat that! :)

[1] http://tech.mit.edu/V126/N64/64largenumber.html



Per my comment above, Busy Beaver will pass that pretty quickly too, as again, a Busy Beaver contestant will rather early on simulate that entire problem (and BB has ready access to numbers like a mere googol). As large as that number is, I'd guess it's probably under BB(30), and certainly under BB(100) as I'd bet even a mere human could write a 100-state TM to simply simulate that answer.


Why? Perhaps I misunderstand something, but why can't I define a turing machine and the upper bound, and then BB with first order set theory. It is therefore my misunderstanding, that this gives me a lower bound of

BB( googol -n),

whith n the number of symbols I need to define BB.




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

Search: