M.B. Small, R.M. Potemski
Proceedings of SPIE 1989
We present the information-theoretic incompleteness theorems that arise in a theory of program-size complexity based on something close to real lisp. The complexity of a formal axiomatic system is defined to be the minimum size in characters of a lisp definition of the proof-checking function associated with the formal system. Using this concrete and easy-to-understand definition, we show (a) that it is difficult to exhibit complex S-expressions, and (b) that it is difficult to determine the bits of the lisp halting probability ωlisp. We also construct improved versions ω″lisp and ω″lisp of the lisp halting probability that asymptotically have maximum possible lisp complexity. © 1992.
M.B. Small, R.M. Potemski
Proceedings of SPIE 1989
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Igor Devetak, Andreas Winter
ISIT 2003
A. Grill, B.S. Meyerson, et al.
Proceedings of SPIE 1989