Un lenguaje de programación no determinista es un lenguaje que puede especificar, en ciertos puntos del programa (llamados "puntos de elección"), varias alternativas para el flujo del programa . A diferencia de una declaración if-then , el método de elección entre estas alternativas no lo especifica directamente el programador; el programa debe decidir en tiempo de ejecución entre las alternativas, a través de algún método general aplicado a todos los puntos de elección. Un programador especifica un número limitado de alternativas, pero el programa debe elegir posteriormente entre ellas. ("Elegir" es, de hecho, un nombre típico para el operador no determinista). Se puede formar una jerarquía de puntos de elección, con elecciones de nivel superior que conducen a ramas que contienen elecciones de nivel inferior dentro de ellas.
Un método de elección se materializa en sistemas de retroceso (como Amb, [1] o la unificación en Prolog ), en los que algunas alternativas pueden "fallar", lo que hace que el programa retroceda y pruebe otras alternativas. Si todas las alternativas fallan en un punto de elección en particular, entonces falla una rama entera y el programa retrocederá aún más, hasta un punto de elección anterior. Una complicación es que, como cualquier elección es tentativa y puede rehacerse, el sistema debe ser capaz de restaurar estados antiguos del programa deshaciendo los efectos secundarios causados por la ejecución parcial de una rama que finalmente falló.
Otro método de elección es el aprendizaje de refuerzo , incorporado en sistemas como Alisp. [2] En estos sistemas, en lugar de retroceder, el sistema realiza un seguimiento de cierta medida de éxito y aprende qué elecciones suelen conducir al éxito y en qué situaciones (tanto el estado interno del programa como la entrada ambiental pueden afectar la elección). Estos sistemas son adecuados para aplicaciones en robótica y otros dominios en los que retroceder implicaría intentar deshacer acciones realizadas en un entorno dinámico, lo que puede ser difícil o poco práctico.