2 papers
cs.CC2017
Plain stopping time and conditional complexities revisited
Mikhail Andreev, Gleb Posobin, Alexander Shen
In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence…
cs.CC2017
Busy beavers and Kolmogorov complexity
Mikhail Andreev
The idea to find the "maximal number that can be named" can be traced back to Archimedes (see his Psammit). From the viewpoint of computation theory the natural question is "which…