Nicholas Thompson wrote:
How, then, could a mathematical proof NOT be a form of algorithm?
To me, the word algorithm suggests an emphasis on clarity and economy of
effort, whereas a proof emphasizes the fact a conclusion in correct, and
why. But a problem can be cast either way.
In logic programming (Prolog):
factorial(1,1).
factorial(N,F):-
N > 1,
NN is N - 1,
factorial(NN,FF),
F is N * FF.
The point here is that given an expression like factorial(5,F) the
Prolog interpreter _solves_ for F, or, given a query like
factorial(5,100) will answer "no" (it's actually 120). The execution
trace of such a program is the proof.. (Although it would often being
intolerably long.)
In a typical imperative programming (Java), the code just moves forward
step by step until n <= 1.
The execution path is defined, instead of being deduced (or more
generally in constraint logic programming systems.. found).
public static long factorial( int n )
{
if( n <= 1 )
return 1;
else
return n * factorial( n - 1 );
}
============================================================
FRIAM Applied Complexity Group listserv
Meets Fridays 9a-11:30 at cafe at St. John's College
lectures, archives, unsubscribe, maps at http://www.friam.org
