Re: Language vs. Library why it matters

*To*: mathgroup at smc.vnet.net*Subject*: [mg61692] Re: Language vs. Library why it matters*From*: Richard Fateman <fateman at cs.berkeley.edu>*Date*: Wed, 26 Oct 2005 01:01:47 -0400 (EDT)*Organization*: University of California, Berkeley*References*: <djk1c7$got$1@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Bill and I have been corresponding off-line on this topic for a while, and I thought it would come to a rest there. But this note deserves some response. Andrzej Kozlowski wrote: ...snip... Mathematica not only computes, > it also uses mathematical concepts. Some of these concepts are > "infinitistic". I don't know what this word means. And > essentially anything infinitistic is subject to Godel's theorems. Is that what it means? Is that a definition "essentially"? In > fact, concepts very closely related to Godel's work have actually > been implemented in Mathematica: for example Chaitin's Omega. How about this: if I say Infinity in a piece of text, does that make it related to GT? In this > sense Bill is correct, any algorithmic mathematics can in principle > be implemented in Mathematica and will have to be subject to Godel's > theorems. > Nope. First of all you need to have the prospect of explicitly generating an infinite sequence of objects. The integers will do. Saying Infinity or Infinitisticalafragislisticexpialadocious doesn't work. > > >>Mathematica running on your computer is not, actually, as >>powerful as the simplest Turing machine. The "Halting Problem" >>for Mathematica on your computer is solvable. You have a finite >>machine with a finite number of states. It is possible in principle >>to tell if a program is in a loop or if it will halt. The testing >>procedure may take a very long time to run, but the testing procedure >>is also finite. >> >> > > > Yes, but bringing up the whole issue of finite state machines is just > a red herring. Actually, Godel's proof does not require the existence > of any infinite sets; it only requires the induction principle: for > every integer n there is an integer n+1. Um, but in any implementation of Mathematica there is a largest integer n. So this principle fails. In the case of computers > this is equivalent to the principle that you can always construct a > larger computer. no, you eventually end up running out of atoms, at least in most views of the universe. Godel's theorem is an abstract mathematical construct. > Even if the halting problem on any particular > computer is solvable, the halting problem for all possible computers > is not. And Mathematica can certainly be modified to run not just on > 64 bit computers but on any kind of computer. At the risk of prompting a response, "all possible" ... is not defined. Is this the mathematical abstraction, or the physical world? The answer is different for the two cases. > > On the other hand if you introduce the objection that there is a > limit to the largest computer that can be constructed e.g. the number > of atoms in the universe - (I recall this very feeble argument has > been used by some computer scientist arguing against Roger Penrose's > "Shadows of the Mind") then you have to accept that algorithms also > are limited by their running time. No, some algorithms can loop forever. Abstractly, not a problem either. There are many possible limits: > the maximum lifetime of the hardware, the maximum lifetime of any > human being, the maximum expected length of existence of any human > civilisation, the expected time before the lights go out in our solar > system, etc. The algorithm that solves the halting problem for the > computer made of all the atoms in the universe is likely to easily > exceed all of these. The point is, abstractly, one can describe this program on half a page or less. Starting at some initial configuration of a the computer process, Loop forever: 1. make a recording of its state. 2. has this state been recorded before? If so you are in a loop. Announce "in a loop" and stop. 3. advance one step in the process. If the process STOPS, announce: Algorithm halted. and stop Since there are a finite number of states, this will eventually stop. > > > So all the staff about finite state machines has virtually no > relevance to this discussion . No, it is exactly what you need to discuss when you are talking about abstractions like G.T. > > > big snip > > > (In fact there are pretty > good reasons to believe that exposure to too much Lisp diminishes > ones ability to understand more complex mathematics, which is one > reason why I would object to teaching Lisp as a programming language > to math students.) Really? Can you state some of these reasons? big snip > > I think I have now written more than I ever wanted to write on this > topic. No one is forcing you! RJF > > Andrzej Kozlowski > > >

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