[[[ First steps with my new construction for a self-delimiting universal Turing machine. We show that H(x,y) <= H(x) + H(y) + c and determine c. Consider a bit string x of length |x|. We also show that H(x) <= 2|x| + c and that H(x) <= |x| + H(the binary string for |x|) + c and determine both these c's. ]]] [ Here is the self-delimiting universal Turing machine! ] define (U p) cadr try no-time-limit 'eval read-exp p (U bits 'cons x cons y cons z nil) (U append bits 'cons a debug read-exp bits '(b c d) ) [ The length of alpha in bits is the constant c in H(x) <= 2|x| + 2 + c. ] define alpha let (loop) let x read-bit let y read-bit if = x y cons x (loop) nil (loop) length bits alpha (U append bits alpha '(0 0 1 1 0 0 1 1 0 1) ) (U append bits alpha '(0 0 1 1 0 0 1 1 0 0) ) [ The length of beta in bits is the constant c in H(x,y) <= H(x) + H(y) + c. ] define beta cons eval read-exp cons eval read-exp nil length bits beta (U append bits beta append bits 'cons a cons b cons c nil bits 'cons x cons y cons z nil ) (U append bits beta append append bits alpha '(0 0 1 1 0 0 1 1 0 1) append bits alpha '(1 1 0 0 1 1 0 0 1 0) ) [ The length of gamma in bits is the constant c in H(x) <= |x| + H(|x|) + c ] define gamma let (loop k) if = 0 k nil cons read-bit (loop - k 1) (loop base2-to-10 eval read-exp) length bits gamma (U append bits gamma append [Arbitrary program for U to compute number of bits] bits' '(1 0 0 0) [That many bits of data] '(0 0 0 0 0 0 0 1) )