See [1], which is about the 'complexity class' Bounded-error Probabilistic Polynomial time. Similar to the P=NP conjecture, there is a BPP=P conjecture. Also c

See [1], which is about the 'complexity class' Bounded-error Probabilistic Polynomial time. Similar to the P=NP conjecture, there is a BPP=P conjecture. Also consider [2], which concerns variations of the Church-Turing thesis. Notably, it mentions probabilistic computation. To answer your original question, indeed probabilistic algorithms are an extension of normal algorithms. One way to make the extension (and retain the property that algorithms give the same output on the same input) is to add a 'random oracle'. [1] https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity) [2] https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#V...