School of Technology and Computer Science Seminars

Busy Beavers and Numbers Left Untouch​ed

by Mr. Suhail Sherif (School of Technology and Computer Science, TIFR)

Friday, October 10, 2014 from to (Asia/Kolkata)
at D-405 (D-Block Seminar Room)
Description
In the first half of this talk, I will talk about the halting problem and show that there are well defined functions f:N->N that no computable function can dominate. In the second half, I will introduce Kolmogorov complexity and present Chaitin's Incompleteness theorem. If time permits, I will also show a proof of Goodstein's theorem.