Title: Paradoxes, Computers, and Reproduction
Date & Time: Thursday, 3 February 2011, 2:00 pm to 3:00 pm, followed by discussions.
Venue: A-212 (STCS Seminar Room)
Abstract: How can one write a computer program that outputs itself? Is the sentence "this sentence is false" true or false? Can one write a program that will distinguish between programs that have infinite loops, and those that do not? Is it possible to make a machine that creates a copy of itself, or even something more complex than itself? How does one show that there are more real numbers than natural numbers? In 1969, Lawvere showed that the answers to all these questions (Kleene's recursion theorem, liar's paradox, Turing's halting problem, von Neumann's self-reproducing automata, Cantor's diagonalization argument, and, of course, Godel's first incompleteness theorem) follow from one very short result in the setting of "cartesian closed categories." I will present this result of Lawvere. If interested, you may join us for the discussion that follows.
Prerequisites: An intuitive notion of what is a computer and what is a computer program should suffice.
