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>
- Re: Re: Language vs. Library why it matters