Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?
Turing-complete means &quot;can compute every function on natural numbers that a Turing machine can compute&quot;. 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.