[Note added 9-june-2005: This analysis is not as sharp as it could be, because it isn't possible to represent arbitrary binary data as a program string without expanding it. It seems to be necessary to add primitives to the combinatory system for reading arbitrary binary data off the end of a program string. Then there wouldn't seem to be any effective procedure for telling where a program string ends, although the prefix property would be preserved.] Define a language of terms by the following: 1. X, K, and S are terms. 2. If t1 and t2 are terms, then (t1 t2) is a term. 3. All terms are generated by finitely many applications of (1) and (2). Define the small-step evaluation relation on terms by the following: 1. (X t) steps to (((t K) S) K). 2. ((K t1) t2) steps to t1. 3. (((S t1) t2) t3) steps to ((t1 t3) (t2 t3)). 4. If t1 steps to t2, then (t1 t3) steps to (t2 t3). 5. All small steps are generated by finitely many applications of (1), (2), (3), and (4). It is clear that if a term t steps to any term, it steps to a unique one. It is computable whether a term t steps to any term as well as, if so, the unique term to which it steps. We say a term t halts if there is an integer n such that every (= any) sequence of small steps starting from t consists of fewer than n steps. Define the valid program strings (each of which is a bitstring) and their interpretations by the following: 1. "0" is a program string interpreted by X. 2. If s1 and s2 are program strings interpreted by t1 and t2, respectively, then the concatenation of "1", s1, and s2 is interpreted by (t1 t2). 3. All program strings are generated by finitely many applications of (1) and (2). It is clear that each valid program string has a unique interpretation, and that no valid program string is a prefix of any other valid program string. We can also associate a unique (infinite) binary tree with the valid program strings, such that each leaf of the tree corresponds to a valid program string by its path from the root of the tree. Consider the formal sum of 2^-|s_i| if the interpretation of s_i halts, or 0 else over the sequence {s_i} of valid program strings, arranged in some standard order, |s| being the length in bits of a string s. By the prefix property, this formal sum converges absolutely to a real number omega, and thus the sum is independent of the arrangement of the valid program strings. A sequence of approximations {alpha_i} is defined by taking alpha_n as the sum of 2^-|s| if every sequence of steps from the interpretation of s consists of fewer than n steps, or 0 else over all valid program strings s of length less than n. Then each alpha_n is a (dyadic) rational number, computable given n. The {alpha_i} are monotone increasing, and omega is the least upper bound of the {alpha_i}. The challenge is to construct the best possible bounds on omega. Since X halts immediately, omega is at least 1/2. Since (X(XX)(X(XX)(XXX)(XXX))(X(XX)(XXX)(XXX))) (X(XX)(X(XX)(XXX)(XXX))(X(XX)(XXX)(XXX))) (associating to the left) does not halt, and its program string is 83 bits long, omega is at most 1-2^-83. The constant omega can also be interpreted as the probability that a randomly selected valid program string is interpreted by a halting term. Here the probability of choosing any given valid program string s is 2^-|s|. Another way to phrase the experiment is to say that, starting from the root of the infinite binary tree described above, a path down the tree is constructed by repeated fair Bernoulli trials choosing which child of a node in the path will be the next node in the path, until a leaf is reached. It is easy to show that a leaf will eventually be reached with probability 1, by considering the random walk of the parameter "excess of 1s over 0s" in the partial program strings generated as the experiment proceeds. By the syntax of valid program strings, the experiment terminates at the first moment this parameter becomes negative.