Return to Revisions

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]