BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Logical Uncertainty - Adrià Garriga Alonso (University of Cambrid
 ge)
DTSTART:20190213T134500Z
DTEND:20190213T151500Z
UID:TALK120358@talks.cam.ac.uk
CONTACT:75379
DESCRIPTION:Is P≠NP? Is the Riemann hypothesis true? Are there infinitel
 y many twin primes? These conjectures haven’t been proven or disproven\,
  but we have quite a bit of “evidence” for them in the form of proven 
 related sentences.\n\nFor example\, there exist many decision problems kno
 wn to be in P\, and many that known to be NP-complete\, along with schemes
  for reducing problems to other problems within those clusters. But no sin
 gle link\, in 50 years\, has yet been discovered from NP-complete to P. [1
 ] As another example\, Zhang [2] showed that for any n\, we can find a lar
 ger prime such that it's at most 7·10^7 away from the next prime.\n\nThis
  is the 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 for answers. Howeve
 r\, the veracity of the sentences is implied by things we assume (the ZF/C
  axioms)\, rather than any data we need to observe. Probability theory thu
 s dictates we should assign them probability 1 if they are true\, and 0 if
  they are false\, which is clearly impossible to do in general for an algo
 rithm that runs in a finite amount of time.\n\nIn this session we will lea
 rn about the problem of logical uncertainty\, what should a solution to it
  look like\, and how some naive approaches to it fall short [3]. Then\, we
  will examine the "Logical Induction" algorithm [4]\, which satisfies many
  desirable properties including being computable\, but unfortunately only 
 does so asymptotically and it is not usable in practice. We will conclude 
 with a recap and an outline of a few extra open problems.\n\n\n[1] Aaronso
 n\, S. "The Scientific Case for P≠NP". https://www.scottaaronson.com/blo
 g/?p=1720\n[2] Zhang\, Yitang. “Bounded gaps between primes.” Annals o
 f Mathematics 179.3 (2014): 1121-1174.\n[3] Demski\, A. "All Mathematician
 s are Trollable: Divergence of Naturalistic Logical Updates" https://agent
 foundations.org/item?id=815\n[4] Demski\, A. and Eisenstat\, S. "An Untrol
 lable Mathematician". https://agentfoundations.org/item?id=1750\n[5] Garra
 brant\, Scott\, et al. "Logical induction." https://arxiv.org/abs/1609.035
 43 (2016)
LOCATION:Engineering Department\, CBL Room 438
END:VEVENT
END:VCALENDAR