Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.

However, pure Prolog is incapable of expressing list intersection. (Disequality, dif/2, would allow it to do it, but dif/2 is not Horn, unlike equality).

This seems like a paradox, at first glance. Is there a simple explanation?

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that.

A list is not a natural number, and list intersection is not a function on natural numbers.

Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a function on natural numbers. And I have no doubt that, given you chose a suitable encoding of lists, Pure Prolog will be perfectly capable of expressing list intersection.

To put it another way: just because Pure Prolog is not capable of expressing list intersection using the particular representation of lists that was chosen for General Prolog does not mean that there does not exist a representation of lists more suitable for use with Pure Prolog such that Pure Prolog is capable of expressing intersection of those particular lists.

StackExchange Computer Science Q#133895, answer score: 82