I don't see the relevance of this paper to AGI assuming one considers humans GI. Humans exhibit the same behavior where for each there's a complexity limit beyond which they are unable to solve any tasks in reasonable amount of time. For very complex tasks even training becomes unfeasible.