School of Technology and Computer Science Seminars

Paradoxes, Computers, and Reproduction

by Dr. Manoj Gopalkrishnan (School of Technology and Computer Sciecne)

Thursday, February 3, 2011 from to (Asia/Kolkata)
at Colaba Campus ( A-212 )
Description
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.
Organised by John Barretto