Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!turpin
From: turpin@cs.utexas.edu (Russell Turpin)
Newsgroups: comp.specification
Subject: Re: Against executable specifications (Re: specifying OBJ in itself)
Summary: To dream, the impossible dream ...
Message-ID: <13850@cs.utexas.edu>
Date: 22 Oct 90 22:55:50 GMT
References: <21500@dime.cs.umass.edu> <5321@uqcspe.cs.uq.oz.au> <40496@shemp.CS.UCLA.EDU>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 27

-----
In article <40496@shemp.CS.UCLA.EDU>, chou@oahu.cs.ucla.edu (Ching-Tsun Chou) writes:
> Think about this:
> 
> Can you design a programming language in which ALL and NOTHING BUT total 
> (in the sense of being convergent for all inputs) recursive functions
> can be described?

Not in any reasonable fashion.  If I had such a language, the
first program I would write would be a general Turing machine
simulator, ie, a program with a list of parameters p1, p2, ...
that describe the TM's transition states and its input tape.  Of
course, for those parameters describing Turing machines that do
not halt, the program would be rejected.  Wow!  A compiler that
solves the halting problem.  

The alternative is a programming language that does not permit
one to write a Turing machine simulator.  This is a pretty poor
excuse for a language.  

(In some unimportant senses, your request is possible.  For
example, an ordering can be described for the set of total
recursive functions, and one can then "specify" them with the
natural numbers: the program "0" corresponds to the first such
function, "1" to the second, etc.  Of course, one cannot
*execute* such programs.)

Russell