Similarly relaxing in my armchair, a deterministic universe is compatible with a CSPRNG as long as the information required to recover it's internal state is too diffuse to recover, or is outside the light cone of your adversary.

Eg, rolling a dice is deterministic, and I imagine an algorithm exists that could recover the value of a dice throw from a recording of the sound of it rolling and it's initial position. But once that sound has turned into heat, and that heat has conducted itself about the walls and into the air, I don't think it's possible to recover the sound.

See also:

"Is flipping a coin random?" (Numberphile)

https://www.youtube.com/watch?v=AYnJv68T3MM [8m]

It’s possible. As in physics says it can be done. But it isn’t technically feasible, probably ever.

There’s nothing in the laws of physics that prohibits us turning burned paper smoke back into a document and recover the information.

I'm not sure physics really does say that. Physicists seem to believe that information is never lost - but that doesn't mean the information can be retrieved. If it's in a fragile state, then the act of measuring it might change it. Eg an electron has both a position and a momentum, but that doesn't mean you can measure it's velocity.

When you burn a document, all the matter might be transferred into the smoke, but you've rendered it into a stream of particles which is small enough to be effected by Brownian motion. Reversing the process (figuring out the initial position of each soot particle) involves knowing the position and momentum of the air molecules impacting the soot particles. In principle, you could take the current position and momentum of those particles and extrapolate backwards - but you can't actually measure that, not even in theory.