
СЕМИНАРЫ 
Колмогоровский семинар по сложности вычислений и сложности определений



Deep effectively closed sets L. Bienvenu^{} 

Аннотация: We know from Gödel's theorem that there is no deterministic algorithm to generate a coherent completion of Peano Arithmetic (PA). But could there be a probabilistic algorithm which achieves this with positive probability? As one can expect, the answer is also negative, by a result of Jockusch and Soare (1972). In the early 2000, Levin and Stephan independently improved Jocksuch and Soare's result; using essentially the same technique, but with different motivations, they respectively showed that (1) Any probabilistic algorithm has probability at most This is joint work with Chris Porter and Antoine Taveneaux. Язык доклада: английский 