Most programming languages are already generally deterministic.
Pick any programming language. Now, remove access to I/O (except standard input and output), networking, time, random number generators, threads, OS syscalls, etc.
Given an input, the program will always generate the same output, i.e. it is deterministic. However, the program is still allowed to have global mutable state; the state is just encapsulated to the program's memory and execution time.
A trivial example is Brainfuck. It is most certainly not a functional programming language, but it is deterministic.
> Pick any programming language. Now, remove access to I/O (except standard input and output), networking, time, random number generators, threads, OS syscalls, etc.
The devil is in the details, and if you miss even one case then the problems are just as bad as if you hadn't bothered at all. For example, comparing two URLs in Java is not deterministic. For another example, iterating through a set in Python will give you the elements in a different order on 32- versus 64-bit systems.
In practice it's just not practical to retrofit deterministic behaviour onto a language that was not designed for it. Even your "trivial example" isn't; Brainfuck does not standardize overflow behaviour and so the same program may behave differently on different systems.
> For example, comparing two URLs in Java is not deterministic.
Well, it does network access, so it would excluded.
> For another example, iterating through a set in Python will give you the elements in a different order on 32- versus 64-bit systems.
This is a good counter-point.
> Brainfuck does not standardize overflow behaviour and so the same program may behave differently on different systems.
Different implementations of Nix might have the same issue in some places. In this case, whether the language is fully defined is orthogonal to whether its behavior is deterministic; here, a particular implementation will continue to be as such.
As far as I know, Nix doesn't have a formal specification; it is defined by its reference implementation.
Deterministic execution simply requires you remove sources of non-determinism. This is not to be confused with defined vs undefined behaviour, like a program behaving different on another machine. As long as it's behaviour remains constant over all executions in the same input environment (where architecture, for example, is part of the input), it is entirely fine.
After all you need to be non-constant over architecture, since you need to download the correct binaries for 32-bit and 64-bit architectures.
