LISP Interpreter Run [omega.l] [Omega in the limit from below!] [Generate all bit strings of length k.] define (all-bit-strings-of-size k) if = 0 k '(()) (extend-by-one-bit (all-bit-strings-of-size - k 1)) define all-bit-strings-of-size value (lambda (k) (if (= 0 k) (' (())) (extend-by-one-bi t (all-bit-strings-of-size (- k 1))))) [Append 0 and 1 to each element of list.] define (extend-by-one-bit x) if atom x nil cons append car x '(0) cons append car x '(1) (extend-by-one-bit cdr x) define extend-by-one-bit value (lambda (x) (if (atom x) nil (cons (append (car x) (' (0))) (cons (append (car x) (' (1))) (extend-b y-one-bit (cdr x)))))) (extend-by-one-bit'((a)(b))) expression (extend-by-one-bit (' ((a) (b)))) value ((a 0) (a 1) (b 0) (b 1)) (all-bit-strings-of-size 0) expression (all-bit-strings-of-size 0) value (()) (all-bit-strings-of-size 1) expression (all-bit-strings-of-size 1) value ((0) (1)) (all-bit-strings-of-size 2) expression (all-bit-strings-of-size 2) value ((0 0) (0 1) (1 0) (1 1)) (all-bit-strings-of-size 3) expression (all-bit-strings-of-size 3) value ((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) ( 1 1 0) (1 1 1)) [Count programs in list p that halt within time t.] define (count-halt p t) if atom p 0 + if = success display car try t 'eval debug read-exp car p 1 0 (count-halt cdr p t) define count-halt value (lambda (p t) (if (atom p) 0 (+ (if (= success (di splay (car (try t (' (eval (debug (read-exp)))) (c ar p))))) 1 0) (count-halt (cdr p) t)))) (count-halt cons bits '+ 10 15 cons bits 'let(f)(f)(f) nil 99) expression (count-halt (cons (bits (' (+ 10 15))) (cons (bits (' ((' (lambda (f) (f))) (' (lambda () (f)))))) n il)) 99) debug (+ 10 15) display success debug ((' (lambda (f) (f))) (' (lambda () (f)))) display failure value 1 (count-halt cons append bits 'read-bit '(1) cons append bits 'read-exp '(1) nil 99) expression (count-halt (cons (append (bits (' (read-bit))) (' (1))) (cons (append (bits (' (read-exp))) (' (1)) ) nil)) 99) debug (read-bit) display success debug (read-exp) display failure value 1 [The kth lower bound on Omega] [is the number of k-bit strings that halt on U within time k] [divided by 2 raised to the power k.] define (omega k) cons (count-halt (all-bit-strings-of-size k) k) cons / cons ^ 2 k nil define omega value (lambda (k) (cons (count-halt (all-bit-strings-of- size k) k) (cons / (cons (^ 2 k) nil)))) (omega 0) expression (omega 0) display failure value (0 / 1) (omega 1) expression (omega 1) display failure display failure value (0 / 2) (omega 2) expression (omega 2) display failure display failure display failure display failure value (0 / 4) (omega 3) expression (omega 3) display failure display failure display failure display failure display failure display failure display failure display failure value (0 / 8) (omega 8) expression (omega 8) display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure debug () display success display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure display failure value (1 / 256) End of LISP Run Elapsed time is 1 seconds.