write unificacion reglas operadores negacion listas explicados ejercicios prolog turing-machines

unificacion - Por favor explique este simulador de máquina Turing escrito en Prolog



unificacion prolog (1)

El artículo de Wikipedia Prolog incluye este simulador de máquina de Turing:

turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :- symbol(Rs0, Sym, RsRest), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), perform(Q1, Ls1, Ls, Rs1, Rs). symbol([], b, []). symbol([Sym|Rs], Sym, Rs). action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). left([], [], Rs0, [b|Rs0]). left([L|Ls], Ls, Rs, [L|Rs]).

Le da un programa de muestra que:

  • Al leer un "1", mueve la cabeza hacia la derecha.
  • Al leer un espacio en blanco, escribe uno y entra en el estado final.

Programa:

rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay).

El programa se ejecuta como se muestra:

?- turing([1,1,1], Ts). Ts = [1, 1, 1, 1] ;

Entiendo el significado de algunos de los nombres de variables en reglas / hechos:

turing(Tape0, Tape)

  • tape0 es la cinta de entrada
  • la cinta es la cinta de salida

rule(Q0, Sym, Q1, NewSym, Action)

  • Q0: estado de inicio
  • Sym: símbolo leído
  • Q1: estado final
  • NewSym: símbolo para escribir
  • Acción: cómo mover la cabeza

No entiendo los significados de las variables en estas reglas / hechos:

perform(Q0, Ls0, Ls, Rs0, Rs) symbol([Sym|Rs], Sym, Rs) action(left/stay/right, Ls0, Ls, Rs0, Rs) left([L|Ls], Ls, Rs, [L|Rs])

¿Alguien puede explicar?

En la máquina de Turing, en cualquier estado dado, el cabezal de escritura apunta hacia un lugar particular de la cinta. Habrá símbolos a la izquierda de la cabeza y símbolos a la derecha de la cabeza.

Mirando el primer predicado principal:

turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape).

Va a "ejecutar la máquina" llamando a perform/5 . Los argumentos para perform(Q0, Ls0, Ls, Rs0, Rs) representan:

Q0 - the current state (or initial state before the "perform") Ls0 - the current set of symbols that are LEFT of the head Ls - the FINAL set of symbols that WILL BE left of the head after perform Rs0 - the current set of symbols that are RIGHT of the head Rs - the FINAL set of symbols that WILL BE right of the head after perform

Inicialmente, no quedan símbolos de la cabeza. Tape0 contiene inicialmente todos los símbolos a la derecha de la cabeza. Para "ejecutar la máquina", el predicado principal llama:

perform(Q0, [], Ls, Tape0, Rs)

Comienza con el estado inicial, Q0 , no tiene símbolos de la cabeza para comenzar con ( [] ) y tiene los símbolos en Tape0 derecha de la cabeza para comenzar. Al completar la consulta, espera que Ls se Ls instancia con el conjunto final de símbolos que quedan de la cabeza, y Rs el conjunto final de símbolos a la derecha de la cabeza.

Todo lo demás ahora es compatible con perform/5 .

symbol([Sym|Rs], Sym, Rs)

Esto define una relación entre la lista de símbolos [Sym|Rs] , y el primer símbolo en esa lista ( Sym ) y el resto de la lista ( Rs ). perform/5 usa este predicado para leer el siguiente símbolo que está actualmente a la derecha de la cabeza.

Para que esto funcione correctamente en el contexto en el que se usa, el predicado perform/5 mantiene la variable Rs0 modo que esté en orden correcto , donde el encabezado de la lista es el primer símbolo a la derecha, el segundo elemento de la lista es el siguiendo el símbolo a la derecha, y así sucesivamente. Tenga en cuenta que este no es el caso de la lista de símbolos a la izquierda. La lista del lado izquierdo se mantiene en orden inverso a cómo aparecen los símbolos en la cinta. La razón es para que puedan considerarse en función de qué tan lejos están de la posición actual de la cabeza. Más sobre esto un poco más tarde.

action(left/stay/right, Ls0, Ls, Rs0, Rs)

Aquí es donde está la acción . :) Su función es realizar la acción dada y proporcionar las listas actualizadas correctamente de lo que está a la izquierda y a la derecha de la nueva posición de la cabeza después de que se realiza una acción. Ls0 y Rs0 son las listas de símbolos a la izquierda y derecha de la cabeza, respectivamente, antes de que se realice la acción. Y Ls y Rs son los símbolos a la izquierda y derecha de la cabeza, respectivamente, después de que se realiza la acción.

action(stay, Ls, Ls, Rs, Rs).

Esta acción dice que cuando me quedo , los símbolos a la izquierda y a la derecha de la cabeza no cambian.

action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

Esta acción dice que cuando muevo la cabeza a la derecha una posición de símbolo, el símbolo inmediatamente a la derecha (que es Sym ya que el conjunto de símbolos correcto es [Sym|Rs] ) se convierte en el símbolo inmediatamente a la izquierda. El conjunto izquierdo de símbolos originalmente era Ls0 y se convierte en [Sym|Ls0] . La lista de símbolos a la derecha era originalmente [Sym|Rs] y se convierte en Rs .

La acción left vuelve un poco más complicada que stay o right porque cuando no hay más símbolos a la izquierda y se indica un movimiento a la izquierda, la cabeza aún se mueve hacia la izquierda y aparece un espacio en blanco a la derecha. Así que lo left dividido en un pequeño predicado separado:

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). left([], [], Rs0, [b|Rs0]).

Aquí, si el conjunto izquierdo de símbolos está vacío ( [] ), moverse a la izquierda significa que los símbolos izquierdos permanecen vacíos ( [] ) y aparece un nuevo espacio en blanco ( b ) a la derecha del encabezado, a la cabeza del conjunto original símbolos a la derecha (la lista del lado derecho cambia de Rs0 a [b|Rs0] ).

left([L|Ls], Ls, Rs, [L|Rs]).

Aquí hay algunos símbolos a la izquierda y la acción es mover hacia la izquierda. El conjunto inicial de símbolos a la izquierda es [L|Ls] ( L es el símbolo inmediatamente a la izquierda de la cabeza) y el conjunto inicial de símbolos a la derecha de la cabeza son Rs . Cuando la cabeza se mueve hacia la izquierda , el primer símbolo a la izquierda se convierte en el primer símbolo a la derecha. Por lo tanto, el conjunto de símbolos actualizado izquierdo es Ls , y el conjunto derecho actualizado de símbolos es [L|Rs] .

El predicado de action(left, ...) podría haberse escrito sin el predicado auxiliar, left/4 , de esta manera:

action(left, [], [], Rs0, [b|Rs0]). action(left, [L|Ls], Ls, Rs, [L|Rs]).

Volver a la lista de la izquierda y el predicado original de turing/2 : después de realizar turing/2 llamadas perform(q0, [], Ls, Tape0, Rs) , tiene un conjunto final de símbolos a la derecha ( Rs ) que están en la posición correcta orden, de izquierda a derecha. Sin embargo, el conjunto final de símbolos a la izquierda ( Ls ) se enumera de derecha a izquierda (ya que en orden de cuán cerca están de la posición actual de la cabeza). Por lo tanto, para mostrar toda la cinta en el orden correcto, la lista de símbolos de la izquierda debe invertirse y, a continuación, anteponerse al conjunto de símbolos correcto. Por lo tanto, las llamadas:

reverse(Ls, Ls1), append(Ls1, Rs, Tape).

Desglosando el predicado perform/5 :

perform(qf, Ls, Ls, Rs, Rs) :- !.

Esto dice que si estamos en el estado final qf , entonces la lista final de símbolos izquierdos, Ls , se convierte en nuestro conjunto actual de símbolos izquierdos . Del mismo modo para los símbolos correctos.

perform(Q0, Ls0, Ls, Rs0, Rs) :- % Read the symbol to the right of the head (Sym) % symbol(Rs0, Sym, RsRest), % Apply first found matching rule to the current state (Q0) % and the current symbol on the right (Sym), resulting in % a new symbol (NewSym) and an action (Action) % once(rule(Q0, Sym, Q1, NewSym, Action)), % Perform the action using the current list of symbols on the left (Ls0) % and the updates list of symbols on the right (old right symbol (Sym) % replaced by the new right symbol (NewSym), which is [NewSym|RsRest] % with the action resulting in new left Ls1 and new right Ls2 % sets of symbols % action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), % Recursively perform the Turing engine on the new state, left, % and right sets of symbols until we hit the final state (qf) % with final result being left symbols, Ls, and right symbols, Rs % perform(Q1, Ls1, Ls, Rs1, Rs).