BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Churchill CompSci Talks
SUMMARY:The busy beaver game: a simple yet non-computable
function - Yi Cai\, Newnham College
DTSTART;TZID=Europe/London:20200205T190000
DTEND;TZID=Europe/London:20200205T193000
UID:TALK139489AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/139489
DESCRIPTION:Do you know any function that is even worse than t
he Ackermann function? The busy beaver game\, firs
t introduced by Tibor RadÃ³ in 1961\, is a fun ques
tion related to computability theory\, the halting
problem as well as complexity theory. The goal of
the game is to find the maximum number of 1s on y
our tape for your given Turing machine after it ha
lts. Although the busy beaver game is quite easy t
o understand and implement\, it can be shown to gr
ow faster asymptotically than any computable funct
ion. In this talk\, we will explore the simple ins
tance of a non-computable function and give some s
imple proof on its non-computability.
LOCATION:Wolfson Hall\, Churchill College
CONTACT:Matthew Ireland
END:VEVENT
END:VCALENDAR