Qu'est-ce qui rend PROLOG Turing complet?

Je sais qu'il peut être prouvé que PROLOG est Turing-complete en construisant un programme qui simule une machine de Turing comme ceci:

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

La source

Cependant, je me demande quelles parties du langage PROLOG on pourrait supprimer (en particulier les symboles de fonction, la surcharge de clause, la récursivité, l'unification) sans perdre l'intégralité de Turing. Les symboles de fonction eux-mêmes sont-ils Turing complets?

C'est une règle empirique assez fiable que l'exhaustivité de Turing dépend de la capacité de construire des réponses ou des valeurs intermédiaires de "taille" illimitée et de la capacité de boucler ou de récuser un nombre illimité de fois. Si vous avez ces deux choses, vous avez probablement l'intégralité de Turing. (Plus précisément, si vous pouvez construire l'arithmétique Peano, alors vous avez certainement l' intégralité de Turing!)

Supposons pour le moment que vous avez déjà supprimé l'arithmétique. Nous supposerons aussi que vous n'avez pas toutes les fonctionnalités non logiques comme atom_chars, assertet ainsi de suite, qui permettent aux manigances générales.

Si vous supprimez les symboles de fonction, vous ne pouvez pas construire de réponses ou d'intermédiaires de taille illimitée; vous ne pouvez utiliser que des atomes qui apparaissent dans le programme et la requête. Par conséquent, l'ensemble de toutes les solutions possibles à n'importe quelle requête est fini , donc prendre le point le moins fixe du programme / de la requête se terminera toujours. Datalog (un langage de requête de base de données relationnelle basé sur Prolog) fonctionne sur ce principe.

De même, si vous avez limité Prolog à la récursion primitive uniquement (qui n'inclut aucune récursivité en tant que cas dégénéré), la quantité de récursivité que vous pouvez effectuer est limitée par la taille de la requête, de sorte que tout calcul se termine. Vous avez donc besoin d'une récursivité générale pour Turing-complétude.

Et, bien sûr, si vous avez une récursivité générale, vous pouvez couper tout un tas de fonctionnalités et conserver l'intégralité de Turing, y compris l'unification générale (la construction et la correspondance de modèle de niveau supérieur sont suffisantes), la négation et la coupe.

Compléter l'excellente réponse de @Pseudonym et faire référence à votre dernière question "Les symboles de fonction eux-mêmes sont-ils Turing complets?".

Vous voulez probablement dire: un langage composé uniquement de symboles de fonction peut-il être Turing-Complete?

La réponse est oui - pensez aux langages de programmation fonctionnelle comme ML et Haskell.