LATEX-L Archives

Mailing list for the LaTeX3 project

LATEX-L@LISTSERV.UNI-HEIDELBERG.DE

Options: Use Forum View

Use Proportional Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Subject:
From:
"Randolph J. Herber" <[log in to unmask]>
Reply To:
Mailing list for the LaTeX3 project <[log in to unmask]>
Date:
Tue, 3 Nov 1998 07:56:47 -0600
Content-Type:
text/plain
Parts/Attachments:
text/plain (46 lines)
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.

ATOM RSS1 RSS2