LISP program-size complexity III

摘要

We present a “parenthesis-free” dialect of LISP, in which (a) each primitive function has a fixed number of arguments, and (b) the parentheses associating a primitive function with its arguments are implicit and are omitted. The parenthesis-free complexity of an S-expression e is defined to be the minimum size in characters ∣p∣ of a parenthesis-free LISP expression p that has the value e. We develop a theory of program-size complexity for parenthesis-free LISP by showing (a) that the maximum possible parenthesis-free complexity of an n-bit string is ∼ βn, and (b) how to construct three parenthesis-free LISP halting probabilities Ωpf, Ω′pf and Ω″pf.