Berry's paradox and elegant Lisp programs

Berry's paradox and elegant LISP programs in Common Lisp

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

ç

Palavras chave: lisp, elegant lisp expressions, Chaitin, Berry's paradox

Última actualização/Last updated: 2012-01-08 [15:03]

1999-2011 (c) Tiago Charters de Azevedo

São permitidas cópias textuais parciais/integrais em qualquer meio com/sem alterações desde que se mantenha este aviso.

Verbatim copying and redistribution of this entire page are permitted provided this notice is preserved.