¿Qué hace que PROLOG Turing sea completo?

Sé que se puede demostrar que PROLOG es Turing completo mediante la construcción de un programa que simula una máquina de Turing como esta:

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]).

Fuente

Sin embargo, me pregunto qué partes del lenguaje PROLOG se podrían eliminar (especialmente símbolos de función, sobrecarga de cláusulas, recursividad, unificación) sin perder la integridad de Turing. ¿Están completos los símbolos de función de Turing?

Es una regla general bastante confiable que la integridad de Turing depende de la capacidad de construir respuestas o valores intermedios de "tamaño" sin restricciones y la capacidad de recorrer o repetir un número ilimitado de veces. Si tiene esas dos cosas, probablemente tenga la integridad de Turing. (Más específicamente, si puedes construir la aritmética de Peano, ¡entonces ciertamente tienes integridad de Turing!)

Supongamos por el momento que ya ha eliminado la aritmética. También asumiremos que no tiene características no lógicas como atom_chars, assertetc., que habiliten travesuras generales.

Si eliminó los símbolos de función, no puede construir respuestas o intermedios de tamaño ilimitado; solo puede usar átomos que aparecen en el programa y la consulta. Como resultado, el conjunto de todas las soluciones posibles para cualquier consulta es finito , por lo que tomar el punto menos fijo del programa / consulta siempre terminará. Datalog (un lenguaje de consulta de base de datos relacional basado en Prolog) funciona según este principio.

Del mismo modo, si restringió Prolog solo a recursividad primitiva (que no incluye recursividad como un caso degenerado), la cantidad de recursión que puede hacer está limitada por el tamaño de la consulta, por lo que todo el cálculo termina. Por lo tanto, necesita una recursividad general para completar Turing.

Y, por supuesto, si tiene una recursividad general, puede cortar un montón de características y conservar la integridad de Turing, incluida la unificación general (la construcción y la coincidencia de patrones de nivel superior es suficiente), la negación y el corte.

Completando la excelente respuesta de @Pseudonym y refiriéndose a su última pregunta "¿Los símbolos de función en sí están completos?".

Probablemente quiera decir: ¿Puede un lenguaje hecho solo de símbolos de función ser Turing-Complete?

La respuesta es sí: piense en lenguajes de programación funcional como ML y Haskell.