From: Tayss
Subject: Intresting writings similar to Chaitin's?
Date: 
Message-ID: <5627c6fa.0308012121.70a3bcc0@posting.google.com>
Does anyone know interesting lispish stuff similar to Gregory
Chaitin's papers?  His work is apparently all about finding the limits
of math, continuing G�del's and Turing's work, and one can find lisp
hidden in lots of places in his work.  I wonder if there's anything
else in that vein.  Maybe something by Quine, who as I heard invented
the lisp-like prefix notation and contributed quite a bit to
philosophy?

http://www.cs.umaine.edu/~chaitin/
http://www.cs.umaine.edu/~chaitin/lisp.html

Of course, it doesn't have to be lispish; I'd never turn down anything
interesting.

From: Thomas Rivas
Subject: Re: Intresting writings similar to Chaitin's?
Date: 
Message-ID: <BgHXa.1953$jq.1507@fe01.atl2.webusenet.com>
"Tayss" <··········@yahoo.com> wrote in message
·································@posting.google.com...
> Does anyone know interesting lispish stuff similar to Gregory
> Chaitin's papers?  His work is apparently all about finding the limits
> of math, continuing G�del's and Turing's work, and one can find lisp
> hidden in lots of places in his work.

Surely your're familiar with the work of  Douglas Hofstadter
http://www.psych.indiana.edu/people/homepages/hofstadter.html-- of  "Godel,
Escher, Bach" fame? Perhaps too far-ranging, not mathematical enough? (He
just about said *Godel* discovered Lisp!)

Tom Rivas
From: Anton van Straaten
Subject: History of parenthesized prefix notation (was: Intresting writings similar to Chaitin's?)
Date: 
Message-ID: <76OXa.34226$Mc.2732251@newsread1.prod.itd.earthlink.net>
"Tayss" wrote:
> Does anyone know interesting lispish stuff similar to Gregory
> Chaitin's papers?  His work is apparently all about finding the limits
> of math, continuing G�del's and Turing's work, and one can find lisp
> hidden in lots of places in his work.  I wonder if there's anything
> else in that vein.  Maybe something by Quine, who as I heard invented
> the lisp-like prefix notation and contributed quite a bit to
> philosophy?

Not answering the question, but I was curious about the Quine reference and
did some investigation.  I can't find any info about Quine having "invented
the lisp-like prefix notation".  Prefix notation, a.k.a. Polish notation
originated with Jan Lukasiewicz in the 1920's.  This was a parenthesis-free
notation which relied on all operators having known arity - specifically,
binary.  See e.g. http://www.philosophypages.com/dy/p7.htm for an example.

However, John McCarthy credits both Lukasiewicz and Quine at
http://www-formal.stanford.edu/jmc/history/lisp/node3.html , as follows:

  "This notation later came to be called ``Cambridge Polish'', because it
resembled the prefix notation of Lukasiewicz, and because we noticed that
Quine had also used a parenthesized prefix notation."

So McCarthy agrees about the originator of prefix notation, but attributes
the use of a *parenthesized* prefix notation to Quine.  I've been unable to
find any other reference to this parenthesized prefix notation, though.

In the foreword to Schonfinkel's "On the building blocks of mathematical
logic", which was the first description of combinatory logic, Quine
apparently suggested using a Polish-style prefix notation for function
application, specifically to *eliminate* the need for parentheses in
combinatory logic.  I'm basing this on a passing reference at
http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html  : "As yet
another applicative notation, to eliminate parentheses completely, Quine in
his foreword to the Schoenfinkel (1924) reprint suggested using prefix for
[function] application, thus: @fx, @@gxy and so on."

So it isn't clear when, if ever, Quine actually used a parenthesized prefix
notation.  I haven't exactly done a thorough search, but I'm told it doesn't
appear in any of Quine's books.  Does anyone know what McCarthy might be
referring to?

(The history of Lisp syntax is at stake, and I'm told we shouldn't make
light of syntax!)

Anton
From: Kenny Tilton
Subject: Re: History of parenthesized prefix notation (was: Intresting writings similar to Chaitin's?)
Date: 
Message-ID: <3F2FB579.1070906@nyc.rr.com>
Anton van Straaten wrote:
> "Tayss" wrote:
> 
>>Does anyone know interesting lispish stuff similar to Gregory
>>Chaitin's papers?  His work is apparently all about finding the limits
>>of math, continuing G�del's and Turing's work, and one can find lisp
>>hidden in lots of places in his work.  I wonder if there's anything
>>else in that vein.  Maybe something by Quine, who as I heard invented
>>the lisp-like prefix notation and contributed quite a bit to
>>philosophy?
> 
> 
> Not answering the question, but I was curious about the Quine reference and
> did some investigation.  I can't find any info about Quine having "invented
> the lisp-like prefix notation".  Prefix notation, a.k.a. Polish notation
> originated with Jan Lukasiewicz in the 1920's.  This was a parenthesis-free
> notation which relied on all operators having known arity - specifically,
> binary.  See e.g. http://www.philosophypages.com/dy/p7.htm for an example.
> 
> However, John McCarthy credits both Lukasiewicz and Quine at
> http://www-formal.stanford.edu/jmc/history/lisp/node3.html , as follows:
> 
>   "This notation later came to be called ``Cambridge Polish'', because it
> resembled the prefix notation of Lukasiewicz, and because we noticed that
> Quine had also used a parenthesized prefix notation."
> 
> So McCarthy agrees about the originator of prefix notation, but attributes
> the use of a *parenthesized* prefix notation to Quine.  I've been unable to
> find any other reference to this parenthesized prefix notation, though.
> 
> In the foreword to Schonfinkel's "On the building blocks of mathematical
> logic", which was the first description of combinatory logic, Quine
> apparently suggested using a Polish-style prefix notation for function
> application, specifically to *eliminate* the need for parentheses in
> combinatory logic.  I'm basing this on a passing reference at
> http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html  : "As yet
> another applicative notation, to eliminate parentheses completely, Quine in
> his foreword to the Schoenfinkel (1924) reprint suggested using prefix for
> [function] application, thus: @fx, @@gxy and so on."

And I thought Lisp was unpopular. parentheses have been under attack for 
almost eighty years. Didn't they have parentheses-aware editors in 1924?

> 
> So it isn't clear when, if ever, Quine actually used a parenthesized prefix
> notation.  I haven't exactly done a thorough search, but I'm told it doesn't
> appear in any of Quine's books.  Does anyone know what McCarthy might be
> referring to?

You can ask him at ILC 2003. :)



-- 

  kenny tilton
  clinisys, inc
  http://www.tilton-technology.com/
  ---------------------------------------------------------------
"Career highlights? I had two. I got an intentional walk from
Sandy Koufax and I got out of a rundown against the Mets."
                                                  -- Bob Uecker