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

I think I can explain that. If you only have two symbols, you can encode the same information as having four symbols in two cells, so performing the same operation on them requires an extra state to read the first of the two and then move to one of two other states to handle the second. Less symbols requires more states.

This is related to the linear speed-up theorem, which roughly states that you can speed up any TM by expanding its alphabet. And speed-up is not what BB is about.

So actually, it would make sense to limit the the busy beavers to BB(n, 2) only.



Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

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

Search: