Re: Language vs. Library why it matters / Turing

• To: mathgroup at smc.vnet.net
• Subject: [mg61415] Re: Language vs. Library why it matters / Turing
• From: Richard Fateman <fateman at cs.berkeley.edu>
• Date: Tue, 18 Oct 2005 02:45:20 -0400 (EDT)
• Organization: University of California, Berkeley
• References: <dipr57\$hfl\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```I think you miss the point of Turing computability in reference
to programming languages.

1. Yes, most programming languages are "Turing equivalent" if they
are permitted unlimited memory. This does not imply that all programming
languages are equally mysterious.  Mathematica is unusual in being
complex, secret, and non-deterministic.  These are each, in my view,
significant detractions from the language and why I would not
suggest that it be used for (say) a first course in programming.

2. Actually, the relevant mathematical model is not that of a
Turing machines (which REQUIRES potentially infinite memory), but
that of a finite state machine.  A computer with N bits of memory
has 2^N states, and if it ever returns to one of those states it
is in an infinite loop.  To see if it halts, you do not have to
run for more than 2^N instructions.  This, of course, could take a
very very very long time, but the mathematics of this is pretty
straightforward.

RJF

Jose Luis Gomez wrote:

> Richard Fateman, to my knowledge (I am not a Mathematician) the classic
> works of mathematician Kurt Goedel and computer scientist Alan Turing shows
> that both Mathematics and computer programs have this property:
>
>
>>  here, it IS NOT nice to have a language so complicated that you
>>don't
>>  know what it will do, and use as an excuse that's ok because no one
>>  else knows either, and often it does the right thing.
>
>
> That is, I think, the reason why Andrzej Kozlowski gave you that somehow
> ironic answer about Arithmetic. It might not be nice, but it is the way it
> is, it is a fundamental limitation of Mathematics, it is also a fundamental
> limitation of Computer Programs, it is Not a particular limitation of
> Mathematica.
>
> Let me recommend this beautiful book about the work of Goedel and the
> fundamental limitations of Mathematics:
>
> Douglas R. Hofstadter, "Gödel, Escher, Bach: An Eternal Golden Braid"
> http://www.amazon.com/gp/product/0465026567/103-1693629-0244650?v=glance&n=2
> 83155&s=books&v=glance
>
> It is a beautiful book.
>
> Best regards!
>
> José Luis
>
>
> ----Mensaje original-----
> De: Andrzej Kozlowski [mailto:andrzej at yhc.att.ne.jp]
> Enviado el: Viernes, 14 de Octubre de 2005 04:54 a.m.
> Para: mathgroup at smc.vnet.net
> Asunto:  Re: Language vs. Library why it matters
>
>
> On 13 Oct 2005, at 14:39, Richard J. Fateman wrote:
>
>
>>  here, it IS NOT nice to have a language so complicated that you
>>don't
>>  know what it will do, and use as an excuse that's ok because no one
>>  else knows either, and often it does the right thing.
>
>
>
> Actually, a "language" need not be terribly complicated for that. It
> only needs to contain the axioms of arithmetic...
>
> Andrzej Kozlowski
> Tokyo, Japan
>
>
>

```

• Prev by Date: Re: Stylesheets vs. DTDs or XML Schemas
• Next by Date: Re: Re: Getting a pure text widget?
• Previous by thread: Re: Re: Double integral of a piecewise-constant function
• Next by thread: Re: Re: Language vs. Library why it matters / Turing