<function name="main"><call function="print"><arg>Hello, World</arg></call></function>
XML isn't a programming language in the same way ASCII isn't a programming language -- in the same way CSV isn't a programming language. Not because of turing completeness, but because they are a completely different thing.
The best necessary condition I can come up with for a language to be called a programming language is that it expresses computations.
The DTD is just a regular expression, and your document as a string to match. The validator is the interpreter that gives you a yes/no answer for any problem you can represent in those terms.
Actually... hmm. If you look closely at the entity replacement rules, the conditional inclusion entities, and the ability to include external dtd references, you may well be able to get full turing completeness.