hi, I was reading the following paper Complexity, Vol. 7, No. 5, May/June 2002, pp. 14-21 PARADOXES OF RANDOMNESS Gregory Chaitin http://www.cs.umaine.edu/~chaitin/summer.html Under the sub heading- Program-Size Complexity,it says "Okay, so what does it mean then for a number to be interesting or uninteresting, now that I'm giving you a better idea of what I'm talking about. Well, interesting means it stands out some way from the herd, and uninteresting means it can't be distinguished really, it's sort of an average, typical number, one that isn't worth a second glance. So how do you define that mathematically using this notion of the size of computer programs? Well, it's very simple: a number is uninteresting or algorithmically random or irreducible or incompressible if there's no way to name it that's more concise than just writing out the number directly. That's the idea. In other words, if the most concise computer program for calculating a number just says to print 123796402, in that case, if that's the best you can do, then that number is uninteresting. And that's typically what happens. On the other hand, if there is a small, concise computer program that calculates the number, that's atypical, that means that it has some quality or characteristic that enables you to pick it out and to compress it into a smaller algorithmic description. So that's unusual, that's an interesting number. " How ever if i take the set of positive whole numbers(zero included),i.e S={0,1,2,...} ,I can compress every positive whole number using a computer program which says f(x)=2x for all x=0,1,2,... ; f(x)=2x+1 for all x=0,1,2,...; and i simply put it an infinite loop shown in the following pseudo code int x=0; while(1) { generate f(x)=2x; generate f(x)=2x+1; } In this way we can compress all the positive whole numbers because say i have a number 10. I try to find if it is interesting or not. decimal 10 = 1010 in binary it takes 4 bits to store decimal number 10 I can write a computer program to generate decimal 10 using f(x)=2x =2*5 =10 for x=5; Decimal number 5 can be represented in binary as 101. So we have 3 bits to represent 5. Using these 3 bits of information,i can get the decimal number 10,when i use f(x)=2x; Similarly-any positive whole number can be compressed using the above pseudo code. This is because Any whole number multiplied by 2 will give an extra bit eg, I have f(x)=2x I choose x=2, 10 in binary(2 bits). 2*2=4 , 100 in binary(3 bits). There is an extra bit that gets added ,when we multiply by 2. I am sure that this is very obvious indeed. So this way I can compress any positive whole number and thus I can show all the whole numbers are interesting contradicting the claim in the paper that most of the whole numbers are uninteresting numbers. He uses this concept of uninteresting numbers to demonstrate algorithmic randomness. The paper further says- "Once you set up this theory properly, it turns out that most numbers, the great majority of positive integers, are uninteresting. You can prove that as a theorem. It's not a hard theorem, it's a counting argument. There can't be a lot of interesting numbers, because there aren't enough concise programs. You know, there are a lot of positive integers, and if you look at programs with the same size in bits, there are only about as many programs of the same size as there are integers, and if the programs have to be smaller, then there just aren't enough of them to name all of those different positive integers." But we already have developed a small concise,as in the pseudo code shown above,that generates me any number of whole numbers. This contradicts the above argumeny. Further down,under the sub heading Redundant,he says- "Is this K bits of mathematical information? K instances of the halting problem will give us K bits of Turing's number. Are these K bits independent pieces of information? Well, the answer is no, they never are. Why not? Because you don't really need to know K yes/no answers, it's not really K full bits of information. There's a lot less information. It can be compressed. Why? " All logs are base 2. "And this is going to be a number between zero and K, a number that's between zero and K. 0 # # that halt # K And if you write this number in binary it's really only about log K bits. # that halt = log K bits " Now how can there be redundancy in various instances of a halting problem. Say-i have a sack with 64 programmes of which ,i know that 32 of them will halt and 32 of them will not halt.I pick,without any order, 32 programs from my sack to check whether they halt or not. If the input programmes are picked truely randomly,then I know 16 of the programs will halt(i.e 50% of the programs halt). So where is the redundancy in different instances of the halting problem? I don't see any redundancy. If the input programs are picked independently,i.e without any mathametcial structure,the output is by no means reduntant. In the section-Redundant,he obtains a real number called k,which he transforms to k bits of information. Then he says that there is redundancy in the output and says that there is only log k(base 2) bits of information. Here he treats k as a real number and says that-he only needs log k(base 2) bits to represent the whole number k. But that is the minimum number of bits that is required to hold the real number in binary representation in its information theorotical sense. What does it have to do with algorithmic randomness? it comes to such a question- I do a fair coin throwing experiment with 64 coins. To represent 64 coins,i need 5 bits of information. If the experiment is truely random,i will get 32 of them as heads and 32 of them as tails-though I dont know which all are heads and which all are tails. now-I see which all are heads.While counting,when I get 32 heads,I can stop counting,since i know the remaining 32 coins are tails. To represent 32 coins-i need 5 bits of information. Since the experiment is truely random-i know half of them will be heads,so in this case using 5 bits of information,i can determine all the coins that are heads and that are tails. So-the question is what is the minimum number of bits or entropy required to determine which all coins are heads and which all coins are tails,is it 5 bits or 6 bits of information? What chaitin does in his k instance halting problem -is he compresses the 6 bits to 5 bits,if we draw an equivalent with our coin tossing experiment,which we can,as it is equivalent to the coin tossing problem. It appears that it is on these lines he obtains the omega notation,though the exact details are not given in this paper. This is what I think.I would like to know more. Regards Sarath. __________________________________ Do you Yahoo!? Yahoo! SiteBuilder - Free, easy-to-use web site design software http://sitebuilder.yahoo.com