But the theory of the machines is entirely deterministic. Any non-deterministic behavior of a machine would be considered an error under any approaches being discussed here.

The point is that the universe can do things that functions cannot. If your only tool is functions (only thing that algorithms can compute), then you will necessarily be unable to handle all possibilities (by which point, I question your intelligence).

Functions routinely use random number generators. Pretty much all AI/Machine Learning techniques use non-determinism as part of their design.

But even so, it's confusing to phrase intelligence in terms of non-determinism. It's easy to come up with a non-deterministic answer to an arbitrary question. It's hard to come up with a correct answer to an arbitrary question. If unpredictability is a component of sound reasoning, it's because we humans are so bad at reasoning.

Pseudo-random generators, for sure, which are entirely deterministic. It does not even matter if you had a source of truly random numbers. Given the same sequence of numbers, an algorithm will return the same result. That is what it means to be a function.

The problem is not that, "my answer must be 'unpredictable'", but, "the actual answer may not be computable" (and so, no algorithm may ever derive it).

That is why random generator has seed, which sometimes considers non-deterministic factors such as hardware noise and environment noise.