Let's Talk About Lambda Functions!

Michael Chermside mcherm at destiny.com
Fri Aug 2 18:10:17 CEST 2002


James J. Besemer writes:
> > The lambda calculus is equal in power to the Turing machine.  In the
> > important sense, no implementable language is more powerful
 >
> I agree your statement is true, though I dispute that this is
> "the important sense" for evaluating the "power" of languages.
> The conclusion actually is of very little practical importance,
> as it doesn't give us any means of discriminating one language
> from another.  It says they're all equal when we know quite
> the opposite is true.  The practical value of the mathematical
> theory may only be perhaps to help distinguish the possible
> from the impossible -- what's computable from what's not --
> but those boundaries are far from our present domain of
> discourse.

I would phrase that slightly differently. I would say that the fact that 
all meaningful languages are turing-equivalent is extremely important. 
It means that when one argues about languages, arguments based on 
"language A can do more than language B" are all bogus... in this sense, 
the languages are all equivalent. Therefore, the kinds of arguments that 
one SHOULD use for comparing languages are ones like this:

   * A is FASTER than B (for certain problems)
   * A takes LESS TIME TO CODE than B (for certain programmers)
   * A is EASIER TO READ than B (for certain kinds of programs)
   * A gives SHORTER PROGRAMS than B (takes fewer lines to implement)
   * A has BETTER LIBRARIES than B (so I can use existing code)
   * A ENCOURAGES SOME STYLE more than B (a style that I prefer)
   * A is MORE WIDELY ACCEPTED than B (so my boss approves the project)

Argued on these terms, of course, Python does very well on all but the 
first and last. (And is improving rapidly on both of those!)

So I agree with your key point -- it's the USABILITY that we should be 
discussing -- I just think that turing equivalence is the REASON we 
should discuss usability, instead if being irrelevent.

-- Michael Chermside





More information about the Python-list mailing list