Next talk on Kolmogorov seminar

[Nikolay Vereshchagin]

Date: November 20, 2023. 

Time: 18:30 (Moscow time), 16:30 (CET).

Speaker: Nikolay Vereshchagin

Title: Improving Solovay’s theorem

Abstract: 

Let CE(S) denote the length of the shortest program enumerating a (computably enumerable) set S. Let AE(S) stand for the probability that the universal randomised Turing machine enumerates S. It is easy to show that if AE(S) is positive then S is a c.e. set. Solovay proved a quantitative version of this statement: if AE(S)>1/2^k then CE(S)<3k. Recently Shekhovtsov and Zakharov improved Solovay’s theorem by replacing the constant 3 by the constant 2 in this inequality. It remains unknown whether we can further reduce this constant.

In the talk, the proof of Shekhovtsov — Zakharov’s theorem will be presented.

Zoom link: https://us06web.zoom.us/j/82818031821?pwd=VjBMWUtvWHJmc3hybGNNWmg5QTFKQT09

[Nikolay Vereshchagin]

correct Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

--
Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/74b3d1f5-1a9d-4c23-ab54-d435ae7e8611n%40googlegroups.com.

--

Н.В.

[Nikolay Vereshchagin]

On November 27 at 18:30 (Moscow time), 16:30 (CET) there will be the continuation of Nikolay Vereshchagin's talk on "Improving Solovay’s theorem".

Zoom link: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09

On Wed, 15 Nov 2023 at 12:20, Nikolay Vereshchagin <nikolay.ve...@gmail.com> wrote:

--

Вы получили это сообщение, поскольку подписаны на группу "Kolmogorov seminar on complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/74b3d1f5-1a9d-4c23-ab54-d435ae7e8611n%40googlegroups.com.

--

Н.В.