Return to Answer

Python, 0 (limit of (65+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(%s+1)%%0x10...0L;print r%%(r,n)';n=(0xF...FL+1)%0x10...0L;print r%(r,n) 

there are 10ⁿ programs of length at most 65+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] 

Python, 0 (limit of (68+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(0x%XL+1)%%0x10...0L;print r%%(r,n)';n=(0xF...FL+1)%0x10...0L;print r%(r,n) 

there are 16ⁿ programs of length at most 68+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] 

Python, 0 (limit of (65+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(%s+1)%%0x10...0L;print r%%(r,n)';n=(0x9...9L+1)%0x10...0L;print r%(r,n) 

there are 10ⁿ programs of length at most 65+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] 

Python, 0 (limit of (65+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(%s+1)%%0x10...0L;print r%%(r,n)';n=(0xF...FL+1)%0x10...0L;print r%(r,n) 

there are 10ⁿ programs of length at most 65+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] 

Python, 0 (in limit)

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(%s+1)%%100;print r%%(r,n)';n=(5+1)%100;print r%(r,n) 

there are 100 programs of length at most 66, for a score of about 0.66. Change that 100 to an arbitrary long, and there are 10ⁿ programs of length O( n), giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] 

Python, 0 (limit of (65+3 n )/(16ⁿ))

If two abstract syntax trees are different if they have different constants,

r='r=%r;n=(%s+1)%%0x10...0L;print r%%(r,n)';n=(0x9...9L+1)%0x10...0L;print r%(r,n) 

there are 10ⁿ programs of length at most 65+3n, giving asymptotic score of 0.

If you want programs with variable structure, we can implement a binary adder on n bits. Here, there are 2ⁿ programs of length O( n²). Goes in a cycle due to dropped carry bit.

s=""" print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1] """ print 's='+'"'+'"'+'"'+s+'"'+'"'+'"' n=lambda m:reduce(lambda (s,c),y:(s+(c^y,),c&y),m,((),1))[0] print s[:112] t=(0,)+(0,)*10 for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): t=n(t) for i in range(2): pass for i in range(2): t=n(t) for i in range(2): pass for i in range(2): pass for i in range(2): pass for i in range(2): t=n(t) t=n(t) print "t=(%s,)+(0,)*%s"%(t[0],len(t)-1) for i in range(len(t)-1): print i*' '+'for i in range(2):' print ' '+i*' '+['pass','t=n(t)'][t[i+1]] print s[113:-1]