|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Topological arguments in Kolmogorov complexity
If you have a question about this talk, please contact Mustapha Amrani.
Semantics and Syntax: A Legacy of Alan Turing
We show how topological arguments (simple facts about non-homotopic mappings) can be used to prove result about Kolmogorov complexity. In particular, we show that for every string x of complexity at least n +c log n one can find a string y such that both conditional complexities C(x|y) and C(y|x) are equal to n+O(1).
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsSpecial Lecture Mathematical Modeling Cavendish Astrophysics Seminars
Other talksFlexible Electronics Based On Polycrystalline Silicon And Integration Technologies For Smart Electronic Systems Packing of wires in cavities and growing surfaces Inheritance of the Human Genome The influence of the Amundsen-Bellingshausen Seas Low on the climate of West Antarctica and its representation in coupled climate model simulations Building Information Modelling: 2016 and Beyond Perturbative tools in the LHC era