4 ms·
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 comple
by WJW 3y ago
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.
- 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.