Y.Y. Li, K.S. Leung, et al.
J Combin Optim
We propose an improved definition of the complexity of a formal axiomatic system: this is now taken to be the minimum size of a self-delimiting program for enumerating the set of theorems of the formal system. Using this new definition, we show (a) that no formal system of complexity n can exhibit a specific object with complexity greater than n+c, and (b) that a formal system of complexity n can determine, at most, n + c scattered bits of the halting probability ω. We also present a short, self-contained proof of (b). © 1992.
Y.Y. Li, K.S. Leung, et al.
J Combin Optim
Kenneth L. Clarkson, K. Georg Hampel, et al.
VTC Spring 2007
F.M. Schellenberg, M. Levenson, et al.
BACUS Symposium on Photomask Technology and Management 1991
M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems