¿Qué significa que un problema sea no determinista?

Un “problema” no es realmente no determinista. El resultado puede ser.

Imagine que toma un trabajo en una fábrica de dulces.
Cada día, su trabajo consiste en sacar los dulces del transportador a medida que pasan junto a usted, y retorcer su cuerpo de una manera para mover los dulces del transportador a una caja cercana.
El trabajo es predecible, mundano. Desarrollas la capacidad de proyectar tu mente en otro lugar mientras trabajas …
Un día entras a trabajar y tu jefe te dice que hay algún problema con el transportador. Parece atascarse, a veces disminuyendo la velocidad, otras acelerando. Tu jefe te pide que hagas lo mejor que puedas, y tendrás que pagar por cualquier dulce que se dañe / pierda.
Rápidamente se da cuenta de que las contorsiones sin sentido que pudo realizar sin esfuerzo el día anterior, sin perder un solo caramelo en el piso, no funcionarán hoy. A veces puede mantenerse al día y lograr llenar algunas casillas. Pero a veces los dulces se disparan tan rápido que no puedes seguir el ritmo. Comienzan a caer al suelo. Empiezas a comerlos para tratar de ocultar el hecho de que estás perdiendo el control del proceso. Pides ayuda …
Pero pronto tus esfuerzos serán inútiles. La monotonía predecible destruida, te llenas la cara y agitas locamente. Cajas medio llenas de dulces aplastados caen al suelo. Los dulces se caen sin tocar el extremo del transportador.
La diferencia está en el transportador. En cualquier otro día, pero hoy la solución al problema del transportador móvil era predecible, las contorsiones requeridas eran manejables, repetibles, periódicas. Hoy en día, la solución al problema del transportador móvil cambia de un momento a otro, y no de ninguna manera que pueda imaginarse como “predecible” para que pueda aplicar su solución de contorsión periódica manejable, repetible.

Terminas agitándote, boca llena de dulces, incapaz de pensar en otra cosa que no sea “¡POR FAVOR, DETÉNGATE!”

En informática tiene una definición muy simple y aparece en bases de datos SQL todo el tiempo. Una función no es determinista si hay algún factor externo que produce un cambio en la respuesta entre varias ejecuciones. Una determinista se puede almacenar en caché.

Todas las funciones son deterministas o no deterministas:

  • Las funciones deterministas siempre devuelven el mismo resultado cada vez que se llaman con un conjunto específico de valores de entrada.
  • Las funciones no deterministas pueden devolver resultados diferentes cada vez que se llaman con un conjunto específico de valores de entrada.

Ver: funciones deterministas y no deterministas