Hacker News Reader

The function BB() is necessarily larger than any function you can compute. It's a surprising/fascinating result.

I've had a lot of success answering questions like this by asking an LLM. It turns out they understand each other and do a great job explaining.

Here's a link for this paper:

https://claude.ai/share/81b1380d-ca03-4ecb-8475-8e0bb95ea87e

View on HN

Thanks, I enjoyed that explanation quite a bit (didn't understand everything, but enough to get a major clue).

I think the idea here is: how do you write as many 1s as you can - without going into an infinite loop. You gotta stop. You only have 10 states in a state machine to "program" with.

That's BB(10).

The naive way to solve this is to generate all possible 10 state state-machines and see what they produce - take the biggest one.

Except many of those will go into an infinite loop - and you cannot easily detect that (or detect it at all for arbitrary n - see also: halting problem) so you go into an infinite loop too.

Computation theory is fun.

Reply on news.ycombinator.com