A brief
history of viruses, including a link to the first published paper
on them. Mentions that virus detection is undecidable.
Hungry for more on Godel's theorem? Read Chaitin's thoughtful article
and see the discussion surrounding Roger Penrose's Godelian argument that "consciousness is nonalgorithmic," promulgated in his 1987 book "The Emperor's New Mind". A purported debunking here .
Hungry for even more? See translation
of Godel's original article from 1931. Still hungry for more? Join the Kurt Godel society.
The Complexity Zoo is an ongoing survey which lists all known (493 at present time), naturally defined complexity classes and their containments. An extension of the project lists interesting problems, and what is known about what classes they lie on. Here , you can check out the results of a computer-assisted analysis to visualize the known relations, which produced this visualization .
A page about Descriptive Complexity, a field which tries to link Complexity Theory with Model Theory / Logic, and can provide some interesting characterizations of some important complexity classes.