I could write programs in XML and write a machine to run them.

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

Oh, you can program meaningful in less than turing complete languages. See Datalog, or even SQL.

Being Turing complete is a sufficient but not necessary condition to be called a programming language.

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 part of the 1.0 spec.

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.