Can an algorithm be truly non-deterministic?
There are two meanings of non-deterministic.
Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the algorithm can branch into multiple execution paths, and the algorithm accepts if any of these paths accepts.  Or, equivalently, you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.  Such an algorithm can't actually be implemented in practice (except by simulating it in an inefficient way), so it is more of a thought experiment.
Meaning #2: non-deterministic means &quot;it is not a deterministic algorithm&quot;.  For instance, such an algorithm might be randomized.
An algorithm that uses random numbers would be considered non-deterministic in the sense of Meaning #2 but not in the sense of Meaning #1.
Usually when you see the phrase &quot;nondeterminism&quot; in complexity theory or algorithms, it will typically mean the former meaning, but no guarantees.  You might have to infer which was meant from context.
See also Differences and relationships between randomized and nondeterministic algorithms?.