🚀 go-pugleaf

Someone (Victor?) writes:

>>>What's an example of a function that is of real interest
>>>to a programmer, and that cannot be  expressed cleanly as a p.r. function.

>In article <10929@alice.UUCP> td@alice.UUCP (Tom Duff) writes:

>>[Inflammatory remarks deleted]
>>Is your lisp interpreter primitive-recursive?
>>[Non-function examples deleted]

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

>I've never used a computer that was not finite state, so I assume all the
>programs that run on the computer are certainly primitive-recursive.
>Counter-example?

Tom Duff was only answering the question; a (pure) Lisp interpreter is
	(a) ``a function of real interest to a programmer'' and 
	(b) ``cannot be expressed cleanly [or not] by as a p.r. function''.
The fact that no complete Lisp interpreter will fit on a real computer
misses the point that he answered the question.  Arguments that people
ought to be satisfied with ``not-quite Lisp interpreters'' are interesting,
but miss the point that people really are interested in real Lisp interpreters.

Here are some points in this discussion I haven't seen mentioned (perhaps
because everyone knows them; I am rather new to this subject, so they
are new to me):
	--So far all the examples have been of nontotal functions, like
	  interpreters.  P.r. does not cover all total g.r. functions.
	  Ackerman's function is a classic counterexample.
	--As has been pointed out, Blum showed that the size of the smallest
	  p.r. program for a p.r. function may be much much bigger than the
	  size of the smallest g.r. program for the same function.
	  But 
		(a) this is only so for functions with a high time
		    complexity (Constable), and
		(b) the run time of the p.r. program can be within a
		    linear factor of the run time of the g.r. program
		    (Constable and Borodin).
	-- No one has mentioned any programmer-friendly language proposals
	   that admit only always-terminating programs.  Nor even recursive
	   programming constructs, other than for-loops, that guarantee
	   termination.  Are there any?  (Let me know by email if you
	   think this net discussion is silly).

My apologies for taking this discussion seriously.

Theo Norvell

Disclaimer:  I don't claim to be an expert on this subject.  I may have
misstated the results.