References: <199811030953.JAA04308@nag.co.uk> <98102213123551@man.ac.uk>,
            <199811030953.JAA04308@nag.co.uk>
Message-ID:  <199811031356.HAA11625@dcdrjh.fnal.gov>
Reply-To: Mailing list for the LaTeX3 project
              <LATEX-L@URZ.UNI-HEIDELBERG.DE>
Date:         Tue, 3 Nov 1998 07:56:47 -0600
From: "Randolph J. Herber" <herber@DCDRJH.FNAL.GOV>
Sender: Mailing list for the LaTeX3 project
              <LATEX-L@URZ.UNI-HEIDELBERG.DE>
To: Multiple recipients of list LATEX-L
              <LATEX-L@URZ.UNI-HEIDELBERG.DE>
Subject:      Re: Quotes and punctuation
Status: R

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 <haberg@MATEMATIK.SU.SE>
|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:haberg@member.ams.org>
|                  * 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, herber@dcdrjh.fnal.gov, +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.