Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!elroy.jpl.nasa.gov!ucla-cs!oahu.cs.ucla.edu!chou
From: chou@oahu.cs.ucla.edu (Ching-Tsun Chou)
Newsgroups: comp.specification
Subject: Re: Against executable specifications (Re: specifying OBJ in itself)
Message-ID: <40570@shemp.CS.UCLA.EDU>
Date: 24 Oct 90 09:08:34 GMT
References: <21617@dime.cs.umass.edu> <40496@shemp.CS.UCLA.EDU> <21665@dime.cs.umass.edu>
Sender: news@CS.UCLA.EDU
Organization: UCLA Computer Science Department
Lines: 33
Nntp-Posting-Host: oahu.cs.ucla.edu

In article <21665@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:

[.....]

>What is the purpose of a programming language? If it is to describe
>"effective computations" in the mathematical sense, then you are correct.
>If, on the other hand, the purpose of a programing language is to describe
>computations that are feasable on digital computers, we have some immediate
>constraints. There is an article by Parikh (Journal of Symbolic Logic 1977?)
>which suggests that an arithmetic restricted to exponentially computable
>functions might be sufficient. An earlier paper, by Cobham, argues that 
>the polynomially computable functions are sufficient. 

[.....]

I never read those papers, so I can't comment on them.
But somehow I suspect that, if your programming language allows you
to write only (say) polynomial-time computable functions, there got to 
be some simple functions which cannot be written in a "natural" way,
because your program would constitute a proof of the polynomial-time
computability of the function being programmed, and we all know that
such proofs are not always easy.
While such proofs are certainly desirable, you may not want them to be
part of your specification, which presumably should convey what is to be
computed, not how the computation is to be done.
In order to be able to separate different concerns,
I'm afraid the possibility of specifying non-polynomial computability, even
non-recursiveness, in your language is something that has to be tolerated.

Incidentally, I wonder how you specify Traveling Salesman Problem if
you can only write polynomial-time computable functions.

- Ching Tsun