Algorithms are not by definition deterministic, which seems to be one of your key points. Probabilistic algorithms exist. They may or may not be used in machine learning currently, but they do exist.
Can you provide an example? All probabilistic algorithms I have seen rely on a pseudo-random generator a rely on an external source if numbers. I have argued elsewhere in these comments that both cases my be considered deterministic.
