Thanks! I came across it while trying to calculate an upper bound on Chaitin's Omega number for Chris Barker's language Iota. Programs in Iota are completely binary trees (that is, 0 or two children). Internal nodes (1's) apply the left branch to the right, and leaf nodes (0's) are a universal combinator. Omega is inf ___ \
(number of n-bit self-delimiting programs that halt) / 2^n /__ n=1
In Iota, programs are self-delimiting--as soon as there are more leaf nodes than internal nodes, you know you're done. The number of ways to do that for a bit string of length 2n+1 is C(n). The probability that a string starts with a prefix containing more zeros than ones approaches certainty. So I guess the limit is another way of saying, "You can't make a syntax error in Iota!" ----- Original Message Follows -----
about :
inf ___ \ C(n)
---- = 2. /__ 4^n n=0
The limit is 2.
C(n) is slightly lower than 4^n, while the principal term is 4^n, eventually the sum converge to 2, I am not a combinatorist or a wilf-zeilbergerologist but I can say that there is probably a variety of ways to show that.
As a number theorist I would suggest, the series slowly increases so it means you can apply lots of tests for series on it validating the convergence of the sum.
simon plouffe
-- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039