School of Technology and Computer Science Seminars
Busy Beavers and Numbers Left Untouched
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)
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. |