computability, what computers can do

Don Mikulecky (mikulecky%VCUVAX.BITNET@letterbox.rl.ac.uk)
Tue, 5 Sep 1995 11:14:32 -0400


The limits to what computers can do are very severe. To see this, I recommend
two books which are really astounding:
1)Algorithmic Information Theory, by G. J. Chaitin, Cambridge Univ. Press,
1987.
2)Information-theoretic incompleteness, by G. J. Chaitin.

Here's a synopsis from Casti's book "Complexification":
p 143....section title: " Out-Goedeling Goedel"
"Using the notion of the shortest program that will print out a
given number as a way to characterize the complexity of that number, we can
get a precise mathematical handle on the idea of a random, or
incompressible, number.
We call a number random if there is no program for calculating it whose
length is shorter than the length of the number itself. Expressed another
way, a number is random if it is maximally complex. Here, of course, we
take the length of the a number to be the number of bits (digits) in its
binary expression.
But do random numbers really exist? The surprising fact is that
almost all numbers are random!.............Ther starting point for Chaitin's
remarkable results is the seemingly innocent query "What is the smallest
number that cannot be expressed in a finite number of words?"...........
More generally, this result shows that even though there clearly
exist numbers of all levels of complexity, it is impossible to prove this
fact.............
....somewhat informally, Chaitin's Theorem says that no program can
calculate a number more complex than itself. "

Chaitin's work is somewhat mind-boggling in it's impact on what we can
expect EVER to come from computers. Certainly, we can not expect them to
reproduce themselves, given these limits.
If that's not enough, try this article:

"Misled by Metaphors: two tools that don't always work" by A.K. Dewdney in
"The machine as metaphor and tool" (Haken, Karlqvist, and Svedin, eds.)
Springer-verlag, 1993.

Here are some excerpts:
"The history of artificial intelligence... can be divided roughly
into two ages...... the cybernetic age runs from 1945 to 1968, ........and the
cognative age from roughly 1960 to the present.......
......of course our brains and the whole process of evolution are
vastly more complicated than formal networks or toy evolutionary systems."
I won't take up more space with quotes. Suffice it to say that at
least one author is convinced that cybernetics is not only not the approach
to issues like living vs nonliving, cognition, evolution, developmental
biology, etc., but
also that it died some years ago. So maybe we do need a new science after all?
Best wishes, Don Mikulecky
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! Don Mikulecky, First International Laboratory for the Application of !
! Analysis Situs to Physiology (FILASAP) !
! Medical College of Virginia Commonwealth University !
! Mikulecky@gems.vcu.edu !
!**********************************************************************!
! An idea is not responsible for who happens to be carrying it !
! at the moment. It must stand or fall on its own merits. !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!