🚀 go-pugleaf

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