Tiago Charters work gallery about blog contact

These are the some functions that implement Chaitin's proof that it is impossible to prove that any particular large program is elegant in Common Lisp (in this implementation large means greater than 17 or 18!).

(defun s-expressin-length (s)
  (length (write-to-string s)))

(defun complexity (s)
  (s-expressin-length (eval s)))

(defun is-elegant (s)
  (cond ((eq (s-expressin-length s) (complexity s))
         t)
        (t
         nil)))

(defun berry1 (lst)
  (cond ((null lst) nil)
        (t
         (cond ((and (is-elegant lst)
                     (>= (complexity lst) (s-expressin-length #'berry1)))
                #'berry1)
               (t
                'lst)))))

(defun berry (lst)
  (cond ((null lst) nil)
        (t
         (cond ((and (is-elegant (car lst))
                     (>= (complexity (car lst)) (s-expressin-length #'berry))))
                #'berry)
               (t
                (berry (cdr lst))))))

Examples

> (s-expressin-length '(car '(a b)))
12

> (complexity  '(car '(a b)))
1

> (is-elegant t)
t

> (is-elegant pi) ; pi is a number?!
t

> (is-elegant 2)
t

> (is-elegant '(car '(a b)))
nil

> (s-expressin-length '(car '(a b d e f g)))
20

> (berry1 '(car '(a b d e f g)))
nil

> (s-expressin-length #'berry1)
18

(s-expressin-length #'berry)
17

ç

---

For attribution, please cite this page as:

Charters, T., "Berry's paradox and elegant Lisp programs": https://nexp.pt/elegant.html (16-02-2026 [16:02])

---

(cc-by-sa) Tiago Charters - tiagocharters@nexp.pt