Una descripción no determinista como la presentada, representa una especificación formal de la evaluación de programas en lógica, interpretada como invocaciones de procedimientos.
Cada punto de no determinismo de la descripción determina un conjunto de posibles caminos de computación. Una implementación de programación en lógica, que será necesariamente determinista, deberá recorrer cada uno de esos caminos, y realizar las evaluaciones corresspondientes. De esta forma se podrá encontrar la o las soluciones a la invocación del programa.
El siguiente ejemplo, extraído de[Hog84] ilustra lo anterior. Sea el programa:
CONSEC ( X, Y, [X.[Y.Z]] ) <- . (1)
CONSEC ( X, Y, [W.Z] ) <- CONSEC ( X, Y, Z ). (2)
El primero y el segundo de los argumentos, son elementos que deben ser consecutivos en la lista que aparece en el tercero. Como se trata de listas se puede utilizar la notación para las mismas que ya fue presentada y cuya estructura [1.[2.[5.[]]]] se escribe (1 2 5).
Sea la invocación:
<- CONSEC ( 2, Z, (2 3 2 4) ).
En este caso la invocación puede activar tanto el procedimiento (1) como el (2). Si se escoge el primero, se inicia una computación que culmina con un resultado de:
Z := 3
Si por el contrario la decisión hubiera recaído en el procedimiento (2), entonces otra computación se hubiera realizado y el nuevo conjunto de objetivos sería:
CONSEC ( 2, Z, (3 2 4) )
Sólo el procedimiento (2) satisface este objetivo, por lo que se obtiene:
CONSEC ( 2, Z, (2 4) )
Se presenta una nueva disyuntiva ya que ambos procedimientos pueden ser activados. Si se opta por el (1), la computación finaliza satisfactoriamente dando como resultado:
Z := 4
En cambio si se escoge el procedimiento (2), la computación sería:
El último predicado no representa ninguna invocación posible. La misma no puede ser satisfecha por los procedimientos del programa. Se ha llegado a una situación de terminación no satisfactoria sin resultados:
[ ]
En el ejemplo se evidencian los distintos caminos de computación posibles, y la forma en que pueden obtenerse las diferentes soluciones de la ejecución de un programa.
Al conjunto de todos los caminos de evaluación se le llama espacio de
computación. Un intérprete de programas en lógica debe considerar
dicho espacio, y recorrerlo mediante una estrategia definida. Una
forma de representar ese espacio es mediante un árbol cuyos nodos son
los valores del conjunto 
de invocaciones a ser ejecutadas. Los
descendientes de un nodo representan las distintas alternativas de
evaluación del mismo. Las hojas del árbol que correspondan al valor
vacío para significarán una culminación exitosa de una
evaluación, y se representarán por «[ ]». En caso
que se termine sin posibilidad de resolver una invocación, o sea en la
culminación insatisfactoria, se denotará con«[X]».
Si se considera el ejemplo anterior y la invocación considerada, el espacio de computación puede representarse de la siguiente manera:
* CONSEC(2, Z, (2 3 2 4))
/ \
/ \
[ ] * CONSEC(2, Z, (3 2 4))
|
|
* CONSEC(2, Z, (2 4))
/ \
/ \
[ ] * CONSEC(2, Z, (4))
|
|
* CONSEC(2, Z, ())
|
|
[X]
Todas las computaciones que han sido presentadas son finitas en el sentido que culminan, satisfactoriamente o no. Pueden existir, sin embargo, casos de caminos de computación infinitos, como sería el caso si al programa del ejemplo se lo invocara con:
<- CONSEC ( 1, 2, Z ).
Un espacio con computaciones infinitas implica un árbol de profundidad infinita.
En el ejemplo presentado cada nodo contenía un solo predicado. Sin embargo, en el caso general pueden ser más de uno, y entonces la decisión a tomar no es solamente cuál procedimiento activar, sino también cuál invocación elegir. Este hecho no hace sino poner en evidencia los dos puntos de no determinismo de la máquina presentada en la sección anterior.
Un intérprete de programación en lógica tendrá definido internamente el orden en que irá recorriendo el espacio de computación, es decir el orden en que irá escogiendo invocaciones y procedimientos. Esto implica que una vez escogido un camino, será necesario retornar al punto de la decisión para buscar una nueva alternativa. Cabe señalar que todos los caminos deben ser iniciados con el mismo estado de las variables. El retorno no solamente necesita de un posicionamiento de control en el punto de decisión, sino que además se deben restaurar los valores que tenían las variables al iniciar la alternativa anterior. Al mecanismo para realizar tal proceso se le denomina englishbacktracking.
Las implementaciones de PROLOG y de sus lenguajes derivados poseen una estrategia generalmente aceptada de decisión, que se basa en el orden establecido por el usuario al escribir sus programas.