David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
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.
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
T. Graham, A. Afzali, et al.
Microlithography 2000
Salvatore Certo, Anh Pham, et al.
Quantum Machine Intelligence