3 ms·
They describe computations that are forbidden despite the inputs to these computations being small, and the description of the computation being easily fit insi
by nabla9 3y ago
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.
- WJW 3y agoSure? 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.
- Nevermark 3y agoLimits 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.