On the Irrelevance of Godel for Real World Computation
···
-------------------------------------------------------
There is a fundamental problem with applying Godel's famous theorems to <any>
real world system: in order for the theorems to hold, the notational systems in question must be potentially infinite. Finite notational systems
(e.g. sequences of symbols with finite string lengths) do not yield
indeterminate results -- since the set of all strings is surveyable, a
determination can be made (given adequate processing time, another
issue altogether) of whether a given set of operations is consistent.
Since all real world computing devices because of their physical limitations,
must be finite state automata, Godel's conclusions do not hold for them.
There are other "semantic" problems with Godel's theorems which were pointed
out by Wittgenstein in his Remarks on the Foundations of Mathematics (see the
excellent discussions in S.G. Shanker's Wittgenstein and the Turning Point in
the Philosophy of Mathematics, 1987, SUNY Press and in Shanker's anthology,
Godel's Theorem in Focus. The notion of an infinite "proof" violates the
concept of a proof as a demonstration that can be consistently replicated by a
community of observers -- if the "proof" is potentially infinite, the proof
cannot be replicated by finite observers.
There are much better groundings for a concept of "self-reference" than Godel.
The "nets with loops" of McCulloch and Pitts (1943), for example, can actually
be built (in contrast to the potentially infinite constructions of Godel). The
nervous system is replete with recurrent connections, and these seem to be
much firmer ground on which to base notions of "self-reference" than
etherial ideas involving infinite sets (which can never be realized or even
exhaustively described). We want to avoid the descent into mysticism if
we can.
When I was a graduate student taking a class on computability, I asked myself
whether there would be any real world situations in which computability
considerations would come into play (ruling out some sort of computation which
could otherwise be accomplished with limited memory and processing steps),
and I could think of none. After much more thought, I have come to
believe that Godel's theorem is completely irrelevant to real world
computation, but I'm open to suggestion. I'm not alone in this opinion,
as Bertrand Russell also seems to have had doubts about the relevance of
Godel (see Shanker's essay in the anthology cited above).
Does anyone out there know of a concrete sitation where computability
actually matters (as opposed to considerations of computational complexity)?
The arguments I have made fall under the rubric of a "strict finitist"
or "constructivist" philosophy of mathematics. A comprehensive finitist
position has yet to be well-articulated, but the Shanker books above should
give those interested an entry point into the literature. Nelson Goodman's
essay "A world of individuals" reprinted in Benaceraff & Putnam's anthology
on philosophy of mathematics (in the First Edition, not the mutilated Second
Edition) is quite clear, as well as Paul Bernays' "On platonism in mathematics"
(same volume). Recently Brian Rotman has published a critique of various
notions of infinity (1993, Stanford U. Press, I forget the title), and it
does a very good job of deconstructing the whole edifice.
In summary, in the real world "computational complexity" constraints count
for everything, while "computability" constraints count for nothing.
I also have very strong criticisms of the definition of emergence being
discussed -- but these will have to wait.
-- Peter Cariani
eplunix!peter@eddie.mit.edu