check
Logic Seminar - David Zisselman | Einstein Institute of Mathematics

Logic Seminar - David Zisselman

Date: 
Wed, 15/03/202311:00-13:00
Location: 
Shprinzak 101
Title: Number extensions 
Abstract: 


In this talk I'll present "number extensions'' , a new technique of proof.
I will explore a new proof of both Godel's incompleteness theorems using this technique.
Next I will define the concept of "knowledge" of a function on the natural numbers and explain how this concept along with number extensions allows us to prove results in algorithms and computability. In Particular, it allows us to take an "algorithm" of a non-deterministic computation and make it into a deterministic one.

As an example, I'll show that, under some (mild) assumptions, an algorithm for factoring natural numbers in poly-logarithmic time exists.

This talk will not assume prior knowledge in logic or set theory. Participants in other fields (such as algorithm design and computability) are more than welcome to hear!