MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Language vs. Library why it matters

  • To: mathgroup at
  • Subject: [mg61692] Re: Language vs. Library why it matters
  • From: Richard Fateman <fateman at>
  • Date: Wed, 26 Oct 2005 01:01:47 -0400 (EDT)
  • Organization: University of California, Berkeley
  • References: <djk1c7$got$>
  • Sender: owner-wri-mathgroup at

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:


  Mathematica not only computes,
> it also uses mathematical concepts. Some of these concepts are  
> "infinitistic". 

I don't know what this word means.
> essentially anything infinitistic is subject to Godel's theorems. 

Is that what it means?   Is that a definition "essentially"?

> 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

>>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

> 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.)

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!

> Andrzej Kozlowski

  • Prev by Date: Re: Accessing Elements of Arrays in TableForm
  • Next by Date: Re: Re: JLink discover and link to an already running kernel from a Java App
  • Previous by thread: Re: Re: Language vs. Library why it matters
  • Next by thread: Re: Re: Language vs. Library why it matters