Remix.run Logo
▲ qarl 19 hours ago

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.