also sprach Sarad AV <[EMAIL PROTECTED]> [2003.08.16.1321 +0200]: > f(x)=2x for all x=0,1,2,... ; > f(x)=2x+1 for all x=0,1,2,...;
You need an extra bit to store which of the two is used. Otherwise, > f(x)=2x > > =2*5 > =10 for x=5; > > Decimal number 5 can be represented in binary as 101. ... you can't decompress five as you don't know if it's 10 or 11. and it's exactly this 2^0 bit which your compression kicks off. you need it, can't do without. [...] > If the input programmes are picked truely randomly,then I know 16 > of the programs will halt(i.e 50% of the programs halt). Look at it differently: you have a 50% chance of guessing whether a given program from the sack will halt or not. This sheds some different light onto the issue, doesn't it? I raise a different question: are there more programs that halt than programs that don't halt, or the other way around, or are they equal in number? > So where is the redundancy in different instances of > the halting problem? I don't see any redundancy. It's simple, if I am correct. The redundancy simply makes you care less about the specific instance you are looking at. > 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. Same deal, unless you are counting pairs, in which case you cannot distinguish between the members of a pair. You need an extra bit to tell a head from a tail. > 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? With 5 bits, you can count to 31, so you need 6. Just my two tails. -- martin; (greetings from the heart of the sun.) \____ echo mailto: !#^."<*>"|tr "<*> mailto:"; [EMAIL PROTECTED] invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! "i love deadlines. i like the whooshing sound they make as they fly by." -- douglas adams
pgp00000.pgp
Description: PGP signature
