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

If there was an algorithm that produced the busy beaver for a computer of a certian size, you could run it to see how long it would run and then compute the busy beaver function. The busy beaver function grows faster than any computable function[] so that's not possible.

[]https://en.wikipedia.org/wiki/Busy_beaver



You couldn't use that to compute the busy beaver function, as the busy beaver function asks about Turing machines which have unlimited tape. You can solve it if you have a finite amount of tape, but you'd never know whether one of machines that tried to exceed the limit would have produced a longer output before eventually halting.




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

Search: