O que torna o PROLOG Turing completo?

Eu sei que pode ser comprovado que o PROLOG é Turing-completo construindo um programa que simula uma 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]).

Fonte

No entanto, estou imaginando quais partes da linguagem PROLOG poderiam ser removidas (especialmente símbolos de função, sobrecarga de cláusula, recursão, unificação) sem perder a integridade de Turing. Os próprios símbolos de função Turing estão completos?

É uma regra prática bastante confiável que a conclusão de Turing dependa da capacidade de construir respostas ou valores intermediários de "tamanho" irrestrito e da capacidade de repetir ou repetir um número irrestrito de vezes. Se você tem essas duas coisas, provavelmente tem a perfeição de Turing. (Mais especificamente, se você pode construir a aritmética do Peano, certamente tem a perfeição de Turing!)

Vamos supor que você já tenha retirado a aritmética. Também assumimos que você não possui recursos não lógicos como atom_chars, assertetc., que ativam travessuras gerais.

Se você retirou os símbolos de função, não poderá criar respostas ou intermediários de tamanho irrestrito; você só pode usar átomos que aparecem no programa e na consulta. Como resultado, o conjunto de todas as soluções possíveis para qualquer consulta é finito ; portanto, o ponto menos fixo do programa / consulta sempre será encerrado. O Datalog (uma linguagem de consulta de banco de dados relacional baseada no Prolog) funciona com esse princípio.

Da mesma forma, se você restringiu o Prolog apenas à recursão primitiva (que inclui nenhuma recursão como um caso degenerado), a quantidade de recursão que você pode fazer é limitada pelo tamanho da consulta, para que todo o cálculo termine. Portanto, você precisa de uma recursão geral para completar Turing.

E, é claro, se você tiver recursão geral, poderá cortar um monte de recursos e manter a integridade de Turing, incluindo a unificação geral (construção e correspondência de padrões de nível superior é suficiente), negação e corte.

Completando a excelente resposta com @Pseudonym e referindo-se à sua última pergunta "Os próprios símbolos de função Turing estão completos?".

Você provavelmente quer dizer: Uma linguagem composta apenas de símbolos de função pode ser Turing-Complete?

A resposta é sim - pense em linguagens de programação funcional como ML e Haskell.