Date: Sat, 23 Feb 2002 18:48:41 -0800
From: Dana Dahlstrom 
To: Joseph Goguen 
Subject: General Problem Solver
Content-Disposition: inline
User-Agent: Mutt/

I wanted to understand Stansifer's assertion on page 163 that the
two-line procedure GPS, using call-by-name, can ``compute any computable
function using a single assignment statement [8].''

So I looked up Stansifer's [8], which turned out to be an article
entitled ``ALGOL 60 Confidential'' by Knuth and Merner in the June 1961
issue of CACM. The relevant part is section 9:


9.  An Innerproduct Procedure

Here is a generalization of the innerproduct procedure given in
paragraph 5.4.2 of the ALGOL Report; we modestly call it GPS, for
General Problem Solver:

real procedure GPS(I,N,Z,V); real I,N,Z,V;
  begin for I := 1 step 1 until N do Z := V; GPS := 1 end;

Is not that the most harmless looking procedure you ever saw? Wait a
minute, there is a lot of danger lurking in the call-by-name parameters.

If we wish to calculate the innerproduct of the N-place vectors A and B,
we simply write:

Z := 0; I := GPS (I,N, Z,Z+A [I] × B [I])

But we can do much better than that. Suppose we want to multiply the
array A[1:m, 1:n] by B[1:n, 1:p] and store the result in C[1:m, 1:p].
This can also be done using GPS, by writing

I := GPS (I, 1.0, C[1,1], 0.0) × GPS(I, (m-1) × GPS(J,(p-1) ×
  GPS(K, n, C[I, J], C[I, J] + A[I, K] × B[K, J]), C[I, J + 1],
  0.0), C[I + 1,1], 0.0);

Test that one out on your ALGOL translator. You can also do problems
which are quite unrelated to matrix multiplication with GPS. For
example, the following will set P equal to the mth prime number:

I := GPS(I, if I = 0 then -1.0 else I, P, if I = 1 then 1.0 else
  if GPS(A,I,Z, if A = 1 then 1.0 else
    if entier (A) × (entier(I)÷entier(A))=entier(I) && A < I
    then 0.0 else Z) = Z then
    (if P < m then P + 1 else I × GPS(A, 1.0, I, 0.0)) else P).

In fact, using GPS we can actually compute any computable function (see
[8]), using a single ALGOL assignment statement.


So Knuth and Merten don't prove it either, but cite their own [8]:

8. DAWS, MARTEN. Computability and Unsolvability. McGraw-Hill, 1958. 

I haven't tracked down the book, but I think I know enough not to be
particularly taken with the omnipotence of the GPS procedure. :)


Dana Dahlstrom
Ph.D. Student, Computer Science and Engineering
University of California, San Diego

(Remember, reality is only an approximation of theory.)