It means that the environment at time t is totally unpredictable given the environment at time t-1. If you imagine that the universe at time t is described as a

It means that the environment at time t is totally unpredictable given the environment at time t-1. If you imagine that the universe at time t is described as a string of random bits, and the universe at time t-1 is also described as a string of random bits, it means that you can't predict any of the bits at t given the bits at t-1. That's what it would mean for nature to be "algorithmically random" in the sense of the paper.