Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
Message from discussion lisp style question
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
arc  
View profile  
 More options Nov 13 2012, 4:17 am
Newsgroups: comp.lang.lisp
From: arc <arc.deletet...@vorsicht-bissig.de>
Date: Tue, 13 Nov 2012 22:16:55 +1300
Local: Tues, Nov 13 2012 4:16 am
Subject: Re: lisp style question
"Pascal J. Bourguignon" <p...@informatimago.com> writes:

> arc <arc.deletet...@vorsicht-bissig.de> writes:

>>> Expressive power.  Power of being usable to write practical programs.

>> And does this have a mathematical definition?  It sounds like it's got a
>> lot to do with what humans find easy to do, so I'm doubtful...

> Yes, it also have a mathematical, information theoric definition.

Where could I find this?

>>>> Anyway, the point was the language Rivka described is inadequate to
>>>> serve as a general-purpose programming language.  Even if you expect a
>>>> lisp to be 'more powerful' than a Turing machine in some sense, you
>>>> still expect it to be at least as powerful as a Turing machine.

>>> Which is not saying much!

>> It's not saying much to say a language is not turing complete? (*laughs*)

> No, it is not saying much to say that a language IS Turing Complete.

But it is saying much to point out that it *isn't* Turing Complete? Good,
because that's what I was doing :-P

> There's no point in mentionning that a language is Turing Complete,
> because Turing Machines are Turing Complete, and are utterly  inusable
> for any practical purpose.

What Turing complete tells you is that the language can encode any
computable function (and normally it comes with a caveat, sometimes
implicit, within the limits of the space available. I'm sure you know
this and are just prentending you don't to vex me).

So we've got two dimensions to describe programming languages, power and
expressiveness:
                                  ^
                                  |expressiveness
         Rivka's 'lisp'           X Lisp
            |                     |
       X    X    X            X   |
     ini files  SQL     simply    |
                        typed λ   |
                                  X Assembly
----------------------------------|------------------->
     power                Turing-computable     Hypercomputability
                                  |
                                  X Turing Machines
                                  |
                                  X Malbolge

(OK, so they're not really entirely independent: a less powerful
language can't express a computation a more powerful language can. But
you get the idea)

By saying there's no point in saying that a language is turing-complete,
you're telling me there's no point in noting that you can't write a
programme in an ini file, or no point in telling Rivka that the language
they describe isn't any kind of general programming language.

Sometimes also it's a surprise that a language is turing complete,
because this isn't always intentional. HTML5 and CSS3 have recently been
shown to be Turing complete, for example.  

Also, discovering that the lambda calculus, recursive functions, and
Turing machines (and all sorts of other computation apparatus) compute
the same set of functions was regarded as a fundamental discovery
(maybe *the* fundamental discovery) of computer science.

So just because there are turing-complete languages that aren't useful
doesn't mean that it's a pointless thing to say.  I'm not sure why you'd
even say that.

( Do you take this attitude to everything in life? There's no point in
saying a material conducts electricity, because some materials that
conduct electricity aren't useful as electrical components? )

> And even for theorical purpose, you're probably better off sticking with
> Lambda Calculus.

Is this all just because you hate the term 'turing complete'?  Well,
I'll try to remember to call it 'lambda calculus complete' if I think
you might be reading, but 'Turing complete' is the commonly-accepted
term for what I was trying to describe.  

--
-arc.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.