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:Machine Learning Reading Group @ CUED
SUMMARY:Logical Uncertainty - Adrià Garriga Alonso (Univer
sity of Cambridge)
DTSTART;TZID=Europe/London:20190213T134500
DTEND;TZID=Europe/London:20190213T151500
UID:TALK120358AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/120358
DESCRIPTION:Is P≠NP? Is the Riemann hypothesis true? Are there
infinitely many twin primes? These conjectures ha
ven’t been proven or disproven\, but we have quite
a bit of “evidence” for them in the form of prove
n related sentences.\n\nFor example\, there exist
many decision problems known to be in P\, and many
that known to be NP-complete\, along with schemes
for reducing problems to other problems within th
ose clusters. But no single link\, in 50 years\, h
as yet been discovered from NP-complete to P. [1]
As another example\, Zhang [2] showed that for any
n\, we can find a larger prime such that it's at
most 7·10^7 away from the next prime.\n\nThis is t
he problem of logical uncertainty: to which degree
should we believe in these logical sentences? How
should we update our beliefs based on the related
evidence? One might turn to probability theory fo
r answers. However\, the veracity of the sentences
is implied by things we assume (the ZF/C axioms)\
, rather than any data we need to observe. Probabi
lity theory thus dictates we should assign them pr
obability 1 if they are true\, and 0 if they are f
alse\, which is clearly impossible to do in genera
l for an algorithm that runs in a finite amount of
time.\n\nIn this session we will learn about the
problem of logical uncertainty\, what should a sol
ution to it look like\, and how some naive approac
hes to it fall short [3]. Then\, we will examine t
he "Logical Induction" algorithm [4]\, which satis
fies many desirable properties including being com
putable\, but unfortunately only does so asymptoti
cally and it is not usable in practice. We will co
nclude with a recap and an outline of a few extra
open problems.\n\n\n[1] Aaronson\, S. "The Scienti
fic Case for P≠NP". https://www.scottaaronson.com/
blog/?p=1720\n[2] Zhang\, Yitang. “Bounded gaps be
tween primes.” Annals of Mathematics 179.3 (2014):
1121-1174.\n[3] Demski\, A. "All Mathematicians a
re Trollable: Divergence of Naturalistic Logical U
pdates" https://agentfoundations.org/item?id=815\n
[4] Demski\, A. and Eisenstat\, S. "An Untrollable
Mathematician". https://agentfoundations.org/item
?id=1750\n[5] Garrabrant\, Scott\, et al. "Logical
induction." https://arxiv.org/abs/1609.03543 (201
6)
LOCATION:Engineering Department\, CBL Room 438
CONTACT:
END:VEVENT
END:VCALENDAR