Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Общеинститутский математический семинар Санкт-Петербургского отделения Математического института им. В. А. Стеклова РАН
14 мая 2015 г. 14:00, г. Санкт-Петербург, ПОМИ, комн. 311 (наб. р. Фонтанки, 27)
 


An asymptotic view of the theory of computability

Paul Schupp

University of Illinois at Urbana-Champaign
Видеозаписи:
Flash Video 433.8 Mb
MP4 567.7 Mb
Дополнительные материалы:
Adobe PDF 297.2 Kb

Количество просмотров:
Эта страница:343
Видеофайлы:78
Материалы:51

Paul Schupp



Аннотация: 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.

Дополнительные материалы: schupp.pdf (297.2 Kb)
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024