I think you actually meant 'referentially transparent', not nondeterminism. You can very much have mutable data and still guarantee determinism. For example with H-calculus you can hard proof that a function that modifies variables will always have the same outcome for the same input. This does for a big part boil down to the 'If a tree falls in the middle of a forest, and no one is there to hear it, does it make a sound?' arguments of local mutability.