Re: Don Knuth - Uncompressable sequences

On Mar 23, 8:46 am, Josiah Carlson <josiah.carl...@xxxxxxxxxxxxx>
tan_st...@xxxxxxxxx wrote:
Algorithmically, is it not possible that there exists an oracle, that
given a sha or other hash of the input sequence, can predict or
reconstruct the original sequence regardless of the length of the
original sequence?

No. There only exists 2^160 sha1 hashes. Under the assumption that it
produces as few collisions as possible, you would only be able to
identify the 2^160 unique 20 byte files. Even if you specified the
length (and assuming that the sha1 hash was uniformly distributed), you
would have 256 possible matches for a 21 byte file with a particular
sha1 hash, 65536 for a 22 byte file, etc.

Despite what the internet says, Bruce Schneier does not see sha1 as an
invertible compression algorithm. :)

- Josiah

This makes me wonder... if the start point of the universe were
treated as a compressed string, then somehow there exists some
compression algorithm the universe is using that is causing that small
piece of information to expand constantly, into something that
obviously isn't just noise. While I understand the math behind why an
oracle could not magically map small numbers to all possible
combinations of strings greater than what the hash can represent, I
still must admit that I am confused by how, if evolution and the
theory of the universe is true, how so much expansion has been done
from possibly just one bit of information in the beginning.

Unless the universe were a program as big as itself. In which case,
who created that program and how big were they?

Can all this must mean only one thing... there must be a god, and the
theories of the universe are wrong?

I think I need to lay off the bong :)