by Professor Rod Downey
Abstract: Given a sequence like 000000000000000000, it does not seem random whereas one obtained by coin tosses does. An elementary fact from statistics says that both of the sequences would be equally likely. Algorithmic radomness seeks to reconcile these two facts and seeks to give meaning to questions like: what does it mean for a real or string to be random? What does it mean for an individual sequence to be partially random? Does randomness give more or less computational power etc. We survey recent work in this area.
The talk will be aimed at a general audience, and no knowledge of logic or statistics is assumed. It will be aimed at advanced undergraduates or beginning graduate students.
For More Information: Contact: David Wood: email@example.com