At 07:56 -0600 1998/11/03, Randolph J. Herber wrote:
>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.
Provided the semantics that one wants to describe can be expressed by
binary numbers: For example, TeX proper cannot draw a non-straight spline
curve no matter how you apply Turing theorems and Godel theorem, even
though you can define structures simulating that TeX can handle that -- but
that has no practical significance unless you figure out a way to extend
TeX to print it. (In this example, even though the curve itself can be
described by binary numbers, the capacity of printing it cannot.)
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/>