Welcome to Effective Randomness and W Number Home

Random sequences were first introduced by von Mises in 1919 as a foundation for probability theory. von Mises thought that random sequences were a type of disordered sequences (stochastic approach). Ville constructed a counter example in 1939 to show that von Mises approach is not a good choice. Later, a complete different approach (entropy based) to the definition of random sequences was proposed by Kolmogorov and Chaitin independently, and was further developed by Levin, Schnorr and others (more introduction here). Finally, Martin-Loef (then a student of Kolmogorov) developed a third approach (typicalness based) to the definition of random sequences in 1966. In 1970s, Schnorr tried to give a uniform approach to the definition of random sequences using martingales. Later, Lutz introduced these concepts to the computational complexity theory. A long open question in this area had been the following one: were recursive martingale based random sequences the same as effective non-constructivity based random sequences? van Lambalgen (1987) and Jack Lutz (1992) have conjectured that they are different. Indeed, this problem had been open since Schnorr's work in 1971. van Lambalgen and Lutz re-examined this problem due to its increasing importance in the complexity theory at that time. Many researchers in this area had tried to solve this problem without success. Using a novel construction, I showed that these two concepts are indeed different in 1995.

Chaitin called the halting probability of a universal self-delimiting Turing machine the W number. W number is the most complicated computable number since it is random. When working with Chaitin in IBM Watson research, Solovay defined the concept of W-like number. Roughly speaking, a real number is W-like if its approximation dominates the approximation of all other computable real numbers. Solovay showed that Chaitin's W number is W-like. When I worked with Professor Chris Calude in Auckalnd University (New Zealand), we showed that indeed, each W-like number is a W number. My contributions to "effective randomness and W numbers have appeared in the following publications:

To better serve the researchers who are interested in the effective randomness and W numbers, I designed this web page for informaiton related to my publications (in particular, a list of these papers that cited my results or used my approach). Your feedback on the web site is important for its accuracy, completeness and relevance. I welcome your comments and suggestions.

Thank you,

Yongge Wang

You are visitor # since 01/06.