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.