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.

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

```

• 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