Expressiveness is not a criteria of being Turing complete. Computability is.
If Pure Prolog is Turing Complete then Pure Prolog can compute the intersection between two sequential sets.
You may not be able to express this computation. It may take you several lines of code or even several pages. You may not be able to use the data structure you prefer. You may need to resort to a different data structure to represent the list or even resort to files on disk. But it should be possible.
The definition of Turing completeness is strictly:
Being able to write a program that implements a Universal Turing Machine.
In other words:
If you can write a Universal Turing Machine emulator in it, it is Turing Complete!
Nothing more, nothing less.
The only reason this definition is considered useful is that for a given computable list of instructions (also called a "language" but most people these days would call it a "program"), there should be at least one Turing Machine capable of parsing it. And it is proven that you can write programs for a Universal Turing Machine that can emulate any Turing Machine. When combined, this means that a Universal Turing Machine can parse anything computable because even if it can't it can execute a Turing Machine eumlator that can parse that thing.
So the theoretical solution for any Turing Complete language incapable of performing a computation is to run a Universal Turing Machine emulator in that language and run a Turing Machine eumlator in that emulator to perform the given computation.
Of course, this is not practical. But Turing Completeness is not about practicality (nor is it about expressiveness), it is only about possibility. It is about computability.
Side note: I would like to bring to your attention the fact that there is a lot of things in computing that are what I call beyond Turing complete.
For example, modern OSes like Linux and Windows and iOS require a computing system that is beyond Turing complete - specifically they require interrupt support. It is possible to write a virtual CPU and run it on a CPU that cannot do interrupt and fake interrupts in software but doing so will fail to work real-time (note: there was a Unix workstation that did something like this but I forgot its name, the CPU did not have interrupts so the computer used two CPUs - one to run the programs and OS and another to monitor hardware and pause the main CPU to handle hardware events thus emulating hardware interrupts - but note that the system is essentially using a second full Turing Machine to implement the thing the main Turing Machine cannot do on its own).
Another example is the Top-Down Operator Precedence algorithm for implementing compilers/parsers. While it can be implemented with any language it is considerably easier to implement it with a language that has first-class functions, a features common in functional languages but uncommon in procedural languages. Heck, even functions themselves are beyond Turing complete since they're not part of Universal Turing Machines (though they form the core of Lambda Calculus - the other computing system developed to define computability and computing)