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: > > >>contrary to some comments >> 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: > > >>contrary to some comments >> 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 > > >

**Follow-Ups**:**Re: Re: Language vs. Library why it matters / Turing***From:*Andrzej Kozlowski <akoz@mimuw.edu.pl>