Greg Chaitin on incompleteness and other wonders
Last week, there was a lot of discussion about completeness
and related topics. I don't want to reopen the discussion,
but I would like to recommend a very readable paper by
Greg Chaitin on some related topics:
http://www.umcs.maine.edu/~chaitin/lowell.html
Chaitin, Conversations with a Mathematician
Greg is the founder of algorithmic information theory,
and he is notable for publishing many readable papers
and books that explain the implications of his much less
readable research publications.
The above paper is a transcription of a lecture entitled
"A Century of Controversy over the Foundations of Mathematics",
in which he summarizes in a very readable way some of the
implications of Cantor's set theory, Russell's logical paradoxes,
Goedel's incompleteness theorem, Turing's Halting problem, and
his own work on algorithmic information theory.
For other readable papers (and books) by Chaitin, most of which
are on the web, see the web site
http://www.umcs.maine.edu/~chaitin/
G J Chaitin Home Page
Many of the topics we have been discussing on CG and SUO lists
touch on these issues, and Chaitin's papers provide some good
background for clarifying the problems and how to approach them.
John Sowa