La característica principal de los algoritmos probabilistas es que un mismo algoritmo se puede comportar de forma distinta cuando se aplica dos veces a un mismo caso. Su tiempo de ejecución e incluso el resultado obtenido, pueden variar considerablemente entre usos consecutivos.

Los cálculos MD5 se utilizan para generar una firma única asociada a una secuencia de bytes sin importar la naturaleza de los datos representados en dicha representación.

La máquina de Turing, presentada por Alan Turing en 1936 en On computable numbers, with an application to the Entscheidungsproblems, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos. Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).

Backtracking (en español vuelta atrás) es una técnica para encontrar solución esos problemas que tienen que satisfacer ciertas restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense Derrick Henry Lehmer en la década de 1950.El backtracking gradualmente construye tareas básicas y las inspecciona para determinar si conducen a la solución del problema. Si una tarea no conduce a la solución, retrocede a la tarea original y se prueba otra cosa distinta. Es una prueba sistemática hasta llegar a la solución, o bien determinar que no hay solución por haberse agotado todas las opciones que probar (espacio de búsqueda).