The following header lines retained to affect attribution: |Date: Tue, 3 Nov 1998 13:28:07 +0100 |Reply-To: Mailing list for the LaTeX3 project |From: Hans Aberg <[log in to unmask]> |Subject: Re: Quotes and punctuation |To: Multiple recipients of list LATEX-L |At 12:53 +0100 1998/11/03, Chris Rowley wrote: |>By contrast, clever TeX code showing that "TeX can do it" is not so |>useful, right now, for this type of parsing problem: since TeX (and |>even its expansion mechanism alone) is Turing complete "TeX can do all |>parsing and string manipulation". | The Turing argument is not so interesting in the context of computer |languages, because firstly computers are not Turing machines, and second |the equivalence between Turing machines normally do not preserve the other |semantic structures that one wants to describe. | Hans Aberg | * Email: Hans Aberg <mailto:[log in to unmask]> | * Home Page: <http://www.matematik.su.se/~haberg/> | * AMS member listing: <http://www.ams.org/cml/> I grant your first point that computers are not Turing machines. That is because no computer has infinite memory (8^} not even big TeX). I disagree with your second point---with sufficient encoding, any semantic can be preserved, possibly with a time penalty (which are ignored when discussing such equivalences). That is one of the points of Goedel's Incompleteness (Undecidability) Theorem. Without regard to available memory, TeX is ``Turing complete''. I suggest that you check the coursework of a Theory of Automata course. The proper argument is whether the encoding is practical in some sense: ease of coding, complexity, running time, maintainability, etc. I offer that the Chris Rowley is correct in that it _could_ be done and that you (Hans Aberg) are correct in that it is not practical to do. Randolph J. Herber, [log in to unmask], +1 630 840 2966, CD/CDFTF PK-149F, Mail Stop 318, Fermilab, Kirk & Pine Rds., PO Box 500, Batavia, IL 60510-0500, USA. (Speaking for myself and not for US, US DOE, FNAL nor URA.) (Product, trade, or service marks herein belong to their respective owners.) BA Math '72.