🚀 go-pugleaf

gudeman@cs.arizona.edu (David Gudeman) writes:

>In article  <15548@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>>
>>This is a common argument, but I'd like to see something a little more
>>concrete. 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.

>How about eval(P) to execute a program P in some more powerful language?

A better example is an implementation of the Knuth-Bendix completion
algorithm (for rewriting).  Or the program that searches for a pair of
embeddable trees in a stream of them.  Or a program that looks for a
witness for the intermediate Paris-Harrington theorem.

There are lots of examples of algorithms that depend for their
termination upon the well-ordered-ness of ordinals of greater height
than epsilon_0, and the fact that every primitive recursive function
sits properly below epsilon_0 tells us that we cannot hope to do all
programming just with p.r. functions.

--chet--
	--chet--
	murthy@cs.cornell.edu