yesterday's talk of Alexey Milovanov

[Alexander Shen]

https://youtu.be/dUnSwFwBi88

Answering Allender's questions (Alexey Milovanov), 02.02.2026 - In Russian

There are two answers: 1) there exists an optimal decompressor $U$ such that for the corresponding Kolmogorov plain complexity function $C_U$ the halting problem is not reducible to the set of random (C(x) is at least |x|) strings; 2) the same but "is not reducible" is replaced by "is reducible" Some motivation and similar question were discussed, but the main argument for 1 will be explained from scratch next time (in English if needed), 09.03.2026