They describe computations that are forbidden despite the inputs to these computations being small, and the description of the computation being easily fit inside the black hole.
Sure? That doesn't even matter for normal computers though. Busy beaver algorithms can be described in very few lines of code but can generate incredible complexity. It's not super difficult to devise an algorithm that would need many more bits of information than just its description+inputs to accurately describe all the state required, and that is in fact exactly what the authors of this paper did.
Limits on all computational complexity in a given regime are a quite different result from noting particular algorithms have high computational complexity.
And if these results and the holographic principle holds, then these limits would apply to all computers. Even “normal” ones.
