En informática , un algoritmo determinista es un algoritmo que, dada una entrada particular, siempre producirá la misma salida, y la máquina subyacente siempre pasará por la misma secuencia de estados. Los algoritmos deterministas son, con diferencia, el tipo de algoritmo más estudiado y familiar, así como uno de los más prácticos, ya que pueden ejecutarse eficientemente en máquinas reales.
Formalmente, un algoritmo determinista calcula una función matemática ; una función tiene un valor único para cualquier entrada en su dominio , y el algoritmo es un proceso que produce este valor particular como salida.
Los algoritmos deterministas se pueden definir en términos de una máquina de estados : un estado describe lo que una máquina está haciendo en un instante particular en el tiempo. Las máquinas de estados pasan de forma discreta de un estado a otro. Justo después de ingresar la entrada, la máquina está en su estado inicial o estado de inicio . Si la máquina es determinista, esto significa que a partir de este momento su estado actual determina cuál será su próximo estado; su curso a través del conjunto de estados está predeterminado. Tenga en cuenta que una máquina puede ser determinista y aun así nunca detenerse ni terminar y, por lo tanto, no ofrecer un resultado.
Ejemplos de máquinas abstractas particulares que son deterministas incluyen la máquina determinista de Turing y el autómata finito determinista .
Una variedad de factores pueden hacer que un algoritmo se comporte de una manera que no sea determinista o no determinista:
Aunque los programas reales rara vez son puramente deterministas, es más fácil para los humanos y para otros programas razonar sobre los programas que lo son. Por esta razón, la mayoría de los lenguajes de programación y especialmente los lenguajes de programación funcionales se esfuerzan por evitar que ocurran los eventos anteriores, excepto bajo condiciones controladas.
La prevalencia de procesadores multinúcleo ha dado lugar a un aumento del interés en el determinismo en la programación paralela y los desafíos del no determinismo han sido bien documentados. [1] [2] Se han propuesto una serie de herramientas para ayudar a afrontar los desafíos [3] [4] [5] [6] para hacer frente a los puntos muertos y las condiciones de carrera .
En algunos casos, es ventajoso que un programa muestre un comportamiento no determinista. El comportamiento de un programa para barajar cartas utilizado en un juego de blackjack , por ejemplo, no debería ser predecible para los jugadores, incluso si el código fuente del programa es visible. El uso de un generador de números pseudoaleatorios a menudo no es suficiente para garantizar que los jugadores no puedan predecir el resultado de una mezcla. Un jugador inteligente podría adivinar con precisión los números que elegirá el generador y así determinar de antemano todo el contenido de la baraja, lo que le permitirá hacer trampa; por ejemplo, el Grupo de Seguridad de Software de Reliable Software Technologies pudo hacer esto para una implementación de Texas Hold 'em Poker distribuida por ASF Software, Inc, lo que les permitió predecir consistentemente el resultado de las manos con anticipación. [7] Estos problemas se pueden evitar, en parte, mediante el uso de un generador de números pseudoaleatorios criptográficamente seguro , pero aún es necesario utilizar una semilla aleatoria impredecible para inicializar el generador. Para ello, se requiere una fuente de no determinismo, como la proporcionada por un generador de números aleatorios de hardware .
Tenga en cuenta que una respuesta negativa al problema P=NP no implicaría que los programas con resultados no deterministas sean teóricamente más poderosos que aquellos con resultados deterministas. La clase de complejidad NP (complejidad) se puede definir sin ninguna referencia al no determinismo utilizando la definición basada en verificadores .
El lenguaje de programación funcional lógico de mercurio establece diferentes categorías de determinismo para modos de predicados como se explica en la referencia. [8] [9]
Haskell proporciona varios mecanismos:
Como se ve en Standard ML , OCaml y Scala
En Java , el valor de referencia nulo puede representar un resultado fallido (fuera del dominio).