M. Shub, B. Weiss
Ergodic Theory and Dynamical Systems
Paper
LISP program-size complexity IV
Abstract
We present a new "character-string" oriented dialect of LISP in which the natural LISP halting probability asymptotically has maximum possible LISP complexity. © 1992.
Related
Sankar Basu
Journal of the Franklin Institute
A.R. Conn, Nick Gould, et al.
Mathematics of Computation
Richard M. Karp, Raymond E. Miller
Journal of Computer and System Sciences