Replies

Thank you for your post!

I said: Indeed, an infinite binary set will contain all possible combinations.

You said: No. The set (0,0,0,0,0....) will not.

Ok, you got me. I was trying to simplify your statement to gore3000 back at 560. You said:

Simple Rule: concatenate the integers base two: 110111001001.... Treat blocks of eight as Ascii encoding. Everything ever written will be in the sequence: the works of Shakespeare, a description of design of a Sherman tank, this thread, a description of every living thing.

Earlier, I tried to simplify that phrasing with "random finite bit streams" which would have helped your argument because Kolmogorov Complexity could be calculated on finite bitstreams, but you objected. And this time, in yet another attempt to simplify and make it work, I again tried to let the bitstream be random and infinite (though I failed to use the word "random.")

I give up trying to simplify and help your algorithm! So going back to your statement at 560:

concatenate the integers base two: 110111001001

I did, with a slight difference as follows, not concantenated:

1
10 11
100 101 110 111
1000 1001 1010 1011 1100 1101 1110 1111
10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111
100000 100001 100010 100011 100100 100101 100110 100111 101000 101001 101010 101011 101100 101101 101110 101111 110000 110001 110010 110011 110100 110101 110110 110111 111000 111001 111010 111011 111100 111101 111111
etc.

Obviously, as the power of two increases the pattern widens placing zero compliments at greater distance. The zero compliment itself is a non-printable character which would never show in Shakespeare and thus Shakespeare could not be found until well after the width of the power of two exceeded the length of the whole manuscript!!! And even in that extreme, by blocking at 8, you would still have zeros compliments and thus, never get Shakespeare.

If it were truly random and infinite, I’d agree that Shakespeare would eventually show up. With this algorithm, no it would not.

Moreover, Kolmogorov Complexity could not be calculated unless the program halts.

On post 613 you said:

All these models of computation do compute exactly the same set of functions though. So far, there is no example of a function that is not computable by a Turing machine but computable by other means. (Not for lack of trying, though.)

The complexity is also the same up to an additive constant.

What I have discovered this weekend is that there is a tremendous disagreement on formulations to determine complexity! This pdf gives over 40 different formulations. Jeepers!

It occurred to me that I may have left the Lurkers with a false impression in my post to y'all last night - so I want to clarify this point:

The zeroes compliment (all 1's) is unprintable, but so are the zeroes themselves (all 0's).

In fact of the 256 possible combinations (zero relative) in an 8 bit ASCII representation, 166 are unprintable or not likely to appear in any Shakespeare manuscript (such as the square root sign.) Included among the 90 which are printable, are such improbable (for Shakespeare) characters as the backslash.

So although one can see from the progression of the powers of two in the above list, that the last binary representation in a "row" will always be "all ones" ... when collected in groups of 8, that is only 1 of the 166 possible non-Shakespearean characters.

IOW, to get Shakespeare - for the full character length of the manuscript, none of those 166 may appear and combination of the other 90 must be in the exact order.

But the output pattern of the algorithm is so structured that the greater the power of two, the longer the high order bits will remain "1" in the the count-up for the row, i.e. the deviation occurs to the right until the next lowest "1" registers on the left. When it reaches all ones, the number of bits increase, and a new row starts.

Thus we would see frequent occurrence of zeros compliments throughout the output bitstream.