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: <email@example.com>
- 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
But this note deserves some response.
Andrzej Kozlowski wrote:
Mathematica not only computes,
> it also uses mathematical concepts. Some of these concepts are
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?
> sense Bill is correct, any algorithmic mathematics can in principle
> be implemented in Mathematica and will have to be subject to Godel's
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,
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.
(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?
> I think I have now written more than I ever wanted to write on this
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