Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




General Mathematics Seminar of the St. Petersburg Division of Steklov Institute of Mathematics, Russian Academy of Sciences
May 14, 2015 14:00, St. Petersburg, POMI, room 311 (27 Fontanka)
 


An asymptotic view of the theory of computability

Paul Schupp

University of Illinois at Urbana-Champaign
Video records:
Flash Video 433.8 Mb
MP4 567.7 Mb
Supplementary materials:
Adobe PDF 297.2 Kb

Number of views:
This page:320
Video files:75
Materials:55

Paul Schupp



Abstract: In recent years the asymptotic-generic point of view of geometric group theory has led to new developments in the theory of computability. I will try to explain this starting from basics. The talk will be for a general audience.
The basic idea is to use asymptotic density as a measure of “for almost all”. A set $A$ is generically computable if there is a partial algorithm $\phi$ for $A$ whose domain has asymptotic density 1. A set $A$ is coarsely computable if there is a computable set $C$ such that the symmetric difference of $A$ and $C$ has density 0. Natural questions from this point of view turn out to be very closely linked to classical ideas in computability theory.
For example, a c.e. degree $d$ is not low if and only if $d$ contains a c.e. set $A$ with density 1 which does not have any computable subset of density 1. It turns out that there is a very tight connection between the position of a set in the arithmetic hierarchy and the complexities of its densities as real numbers.

Supplementary materials: schupp.pdf (297.2 Kb)
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024