🚀 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

In article <22132@megaron.cs.arizona.edu> 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?
>-- 
>					David Gudeman
>Department of Computer Science
>The University of Arizona        gudeman@cs.arizona.edu
>Tucson, AZ 85721                 noao!arizona!gudeman


1. Not a very concrete example. Why do we need the more powerful language?
The question here is whether or not we need non-p.r. functions to
write programs? 

2. We can easily write eval_{k,C}(P) where 
eval_{k,C} must complete within  AckermansFunction(k,C*Length(P)) 
steps. If we cannot write such a function, then is eval(P) feasible?

In article <42209@cornell.UUCP> murthy@algron.cs.cornell.edu (Chet Murthy) writes:
>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--


And 
In article <10838@medusa.cs.purdue.edu> gb@cs.purdue.edu (Gerald Baumgartner) writes:
>Since there is still `term rewriting' in the subject: take the
>Knuth-Bendix algorithm for transforming rewrite rule systems into a
>canonical form. It is a straightforward algorithm if you write it with
>a while-loop or with recursion. You'll have trouble writing it with PR
>constructs since no general bound is known.
>

I'm not arguing that one can dispense with all but p.r. mathematics. I'm
questioning the need for anything beyond p.r. functions in 
a *programming language*. Since, programming languages are usually intended
as aids in describing computations that we desire a digital computer to
perform, it is not clear to me why we need to be able to describe
computations that are not feasible.  One can write a p.r. function which
computes a bounded Knuth-Bendix algorithm say KB(r,p,q), where "r"
bounds the number of steps. Suppose we write a program in a language which
allows expression of unbounded algorithms and have an unbounded version of
knuth bendix KB'(p,q). What is the formal semantics of this function?
Is it that the algorithm will be executed until termination?
If so, the program is not intended for any existing or proposed digital
computer that I know of.  If KB'(p,q) is intended for the class of
mundane digital computers than the
proposed semantics is incorrect --- a programmer who believes the formal
semantics will be deceived, his/her program will behave in a manner not 
matching the formal semantics. The p.r. version provides the programmer with
a better grasp of the actual nature of digital computation. The programmer
is forced to consider the case where time runs out. 

>This Groebner basis algorithm has a similar structure as the
>Knuth-Bendix algorithm (Knuth-Bendix can be simulated by Groebner
>basis algorithm, probably vice versa). The Groebner basis algorithm
>runs in doubly exponential time (double exp. in the degree of the
>polynomials and exponential in the number of polys or so) and still it
>is useful (at least many mathematicians are using it).

BTW, I'm sure you know that double exponential functions are p.r.

>The algorithm
>is around since 1967, it took some 10 years until a bound was
>discovered for the case of polys of degree at most 2. There is still
>no bound known for the general case. Without a bound for the running
>time you cannot program this algorithm using PR constructs.
>

But when you compute the algorithm on a real computer, you do have bounds
on time and storage. Thus, even without a known bound, you implicitly 
program the algorithm in a bounded way. Why is it better to use implicit
bounds?

[more, similar examples deleted].

In article <15639@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>Since, programming languages are usually intended
>as aids in describing computations that we desire a digital computer to
>perform, it is not clear to me why we need to be able to describe
>computations that are not feasible.
>[...] Suppose we write a program in a language which
>allows expression of unbounded algorithms and have an unbounded version of
>knuth bendix KB'(p,q). What is the formal semantics of this function?
>Is it that the algorithm will be executed until termination?
>If so, the program is not intended for any existing or proposed digital
>computer that I know of.  [...]
>But when you compute the algorithm on a real computer, you do have bounds
>on time and storage. Thus, even without a known bound, you implicitly 
>program the algorithm in a bounded way. Why is it better to use implicit
>bounds?

Theoretically, you are right, and we can do without such things as
turing machines, lambda-calculus, and languages which are modelled by
these, since these can `execute' algorithms which are unbounded in 
space and/or time.
In this view, any digital computer is just a finite state machine, the
state being represented by the contents of memory and registers (and I/O
devices). This can be coded as a natural number (take the binary number
represented by all the bits in the system).

This is, however, not a very practical way of programming your computer.
In most cases, one prefers to think of a digital computer as modelling a
turing machine, or a lambda-calculus reduction machine. This allows you
to express algorithms in a more or less concise way, and doesn't force
the algorithm designer to account for memory or time limitations.

It is `impossible' to program the Knuth-Bendix algorithm on a
digital computer, since it has finite memory. Fortunately, in many cases
(theoretically, `many' should read `almost none'...)
the program doesn't run out of memory, and our finite state machine
does a good job in pretending it has infinite storage.

It is better to use implicit bounds because, even though a computer
memory is always finite, one may always buy a faster computer with more
memory, and change those bounds.
Thus, the formal semantics of the program KB'(p,q) is:
 Choose non-deterministically between 
 - KB(p,q)
 - an "out of memory" error
 - the user gets frustrated from waiting and kills the process.
The outcome depends on your particular system, and your patience...
It's the best you can get, I'm afraid :-) .

Nico Verwer                                       |  verwer@cs.ruu.nl
Dept. of Computer Science, University of Utrecht  |  +31 30 533921
p.o. box 80.089 
3508 TB Utrecht
The Netherlands

yodaiken@freal.cs.umass.edu (victor yodaiken) writes:

>t arguing that one can dispense with all but p.r. mathematics. I'm
>questioning the need for anything beyond p.r. functions in 
>a *programming language*.

If it's a while loop, then it's not p.r. Look for one program with a while
loop which cannot be a simple for loop.

-- 
===============================================================================
Steve (really "D. E.") Stevenson           steve@hubcap.clemson.edu
Department of Computer Science,            (803)656-5880.mabell
Clemson University, Clemson, SC 29634-1906

In article <15594@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>The question here is whether or not we need non-p.r. functions to
>write programs? 

That is one question, and several examples have been posted; another is,
why should even a p.r. function necessarily be programmed in p.r.?

--
Richard Kennaway          SYS, University of East Anglia, Norwich, U.K.
Internet:  jrk@sys.uea.ac.uk		uucp:  ...mcvax!ukc!uea-sys!jrk

yodaiken@freal.cs.umass.edu (victor yodaiken) writes:

>I'm not arguing that one can dispense with all but p.r. mathematics. I'm
>questioning the need for anything beyond p.r. functions in 
>a *programming language*. Since, programming languages are usually intended
>as aids in describing computations that we desire a digital computer to
>perform, it is not clear to me why we need to be able to describe
>computations that are not feasible.  One can write a p.r. function which
>computes a bounded Knuth-Bendix algorithm say KB(r,p,q), where "r"
>bounds the number of steps. Suppose we write a program in a language which
>allows expression of unbounded algorithms and have an unbounded version of
>knuth bendix KB'(p,q). What is the formal semantics of this function?
>Is it that the algorithm will be executed until termination?
>If so, the program is not intended for any existing or proposed digital
>computer that I know of.  If KB'(p,q) is intended for the class of
>mundane digital computers than the
>proposed semantics is incorrect --- a programmer who believes the formal
>semantics will be deceived, his/her program will behave in a manner not 
>matching the formal semantics. The p.r. version provides the programmer with
>a better grasp of the actual nature of digital computation. The programmer
>is forced to consider the case where time runs out. 

The beef I have with just prim. rec. is not about nontermination.  If
every algorithm had to have a bound, I'd be happy.  But prim. rec.
does not encompass all recursive functions, or even all
computationally interesting recursive functions.

>>The algorithm
>>is around since 1967, it took some 10 years until a bound was
>>discovered for the case of polys of degree at most 2. There is still
>>no bound known for the general case. Without a bound for the running
>>time you cannot program this algorithm using PR constructs.
>>

>But when you compute the algorithm on a real computer, you do have bounds
>on time and storage. Thus, even without a known bound, you implicitly 
>program the algorithm in a bounded way. Why is it better to use implicit
>bounds?

But your bound might not be p.r.  You bound might be some ordinal
ABOVE epsilon_0.  Such a program would still be bounded, still be
terminating, still efficient for the average case, but not provably
p.r.  To exclude such algorithms simply because they can't be coded
using primitive recursion seems a bit extreme.
	--chet--
	murthy@cs.cornell.edu

In article <15639@dime.cs.umass.edu> yodaiken@freal.cs.umass.edu (victor yodaiken) writes:
>In article <10838@medusa.cs.purdue.edu> gb@cs.purdue.edu (Gerald Baumgartner) writes:
>>This Groebner basis algorithm has a similar structure as the
>>Knuth-Bendix algorithm (Knuth-Bendix can be simulated by Groebner
>>basis algorithm, probably vice versa). The Groebner basis algorithm
>>runs in doubly exponential time (double exp. in the degree of the
>>polynomials and exponential in the number of polys or so) and still it
>>is useful (at least many mathematicians are using it).
>
>BTW, I'm sure you know that double exponential functions are p.r.

But I need to know more than just the asymptotical behaviour to use
it for a bound.

>But when you compute the algorithm on a real computer, you do have bounds
>on time and storage. Thus, even without a known bound, you implicitly 
>program the algorithm in a bounded way. Why is it better to use implicit
>bounds?

The usual way to run this algorithm on more difficult examples is to
start it and see whether you get a useful result before the machine
crashes the next time. I've seen useful results after 1-2 weeks of CPU
time on a Microvax II.

(BTW, you might have used the algorithm already, it's built in in
Mathematica, for simplifying systems of poly equations.)

Sure you can use bounds on the running time (say 1 year). But with
algorithms whose running time is completely unpredictable (that's how
it appears to the user) why not use the natural bound of waiting until
the next downtime of the machine.

I don't think your proposed PR constructs are a bad thing, but I'd like
to have non-PR constructs as well.

Gerald

--
Gerald Baumgartner
Dept. of Computer Sciences, Purdue University, W. Lafayette, IN 47907
Internet: gb@cs.purdue.edu  UUCP: ...!{decwrl,gatech,ucbvax}!purdue!gb