No, document formats are not turing complete. HTML for example can be parsed without any problem. However take this TeX snippet "\foo [bar]" and tell me if "bar" is an argument of "foo" or not, without running the macro (which maybe you do not have. This is the basic problem any TeX conversion program encounters. TeX is not a document format but a programming language. The only thing you can do with a TeX program is to run it. On the other hand an HTML document can be parsed without knowing anything about its content.
I once upgraded an EPS interpreter that was used as the key piece of an EPS importer. I added a couple of PS things like 'arcto'. It seems to me a LaTeX importer could work as an interpreter, too. Probably not very much fun after a while.
Graphics is different since usually the graphics primitives are the common substrate of all graphics languages, so the interpreter can just be adapted to a different backend. For more structured content this is not possible: the natural output of TeX is a sequence of graphics boxes for the glyphs, or something like a DVI format. It is too late to retain semantic informations, e.g. about mathematical formula. Ask anybody which writes LaTeX/HTML converters for example. TeXmacs does a good job to interpret "usual" LaTeX files but you cannot expect to be able to interpret arbitrary files and still retain semantic informations, e.g.: sectioning, references, emphasised texts, theorem statements, change of languages (e.g. from English to C++ to Math...) etc...
> For more structured content this is not possible: the natural output of TeX is a sequence of graphics boxes for the glyphs, or something like a DVI format. It is too late to retain semantic informations, e.g. about mathematical formula.
I think this applies to the natural output of TeX's "mouth" as well, i.e. one could exapnd LaTeX macros till one obtains TeX primitives, but at that point the information on structure is already lost.
