"Not 2^100?"


by Eric Rogstad Jun 27 2016

Although the halting problem means we can't prove it doesn't happen, it would nonetheless be extremely surprising if some 100\-state Turing machine turned out to print the exact text of Shakespeare's Romeo and Juliet\. Unless something was specifically generated by a simple algorithm, the Vast supermajority of data structures that look like they have high algorithmic complexity actually do have high algorithmic complexity\. Since there are at most $~$2^{101}$~$ programs that can be specified with at most 100 bits \(in any particular language\), we can't fit all the 1000\-bit data structures into all the 100\-bit programs\. While Romeo and Juliet is certainly highly compressible, relative to most random bitstrings of the same length, it would be shocking for it to compress all the way down to a 100\-state Turing machine\. There just aren't enough 100\-state Turing machines for one of their outputs to be Romeo and Juliet\. Similarly, if you start with a 10 kilobyte text file, and 7zip compresses it down to 2 kilobytes, no amount of time spent trying to further compress the file using other compression programs will ever get that file down to 1 byte\. For any given compressor there's at most 256 starting files that can ever be compressed down to 1 byte, and your 10\-kilobyte text file almost certainly isn't one of them\.

Not 2^100?


Eliezer Yudkowsky

2^100 + 2^99 + 2^98… + 1 = 2^101 - 1.

Eric Rogstad

Is there a difference between any particular 99-bit program and a 100-bit program with a 0 as the first bit?

Eliezer Yudkowsky

Yes. That includes both the case where the length is specified outside the program, and the case where we use a prefix-free encoding. Actually I'm not sure what you're asking here - why wouldn't prepending 0 to a program change its behavior in whatever Universal Turing Machine you used? If the first bit always has to be 1, it might as well be omitted.

Eric Rogstad

Aren't programs for Turing machines specified as marks on an infinite tape?

I was interpreting 100-bit program as one where up to 100 cells on the tape have marks in them (and there's only one kind of mark, so a cell can only have a mark or not). Maybe I've got the wrong picture though. I haven't studied Turing machines in much depth.