Re: This Week's Finds in Mathematical Physics (Week 226)

Hello John!

John Baez wrote:
Hah! This, by the way, is the key to that puzzle I laid out:
prove that there's a constant K such that no bitstring can be
proved to have algorithmic entropy greater than K.
...
Recall that the algorithmic entropy of a bitstring is defined
as the length of the shortest program that prints it out.

Something about this doesn't make sense to me (but that may be
because it's 4 AM). What does it mean for a program to "print
out" a bit string? I see two interpretations:
1) As a substring of its output
2) As it's precise output
If we use interpretation 1 the statement is obviously correct
because I can construct a finite program that prints out any
finite bit string: it just prints out all of the natural
numbers in binary form, one after another. This is hardly
interesting, though.
If we use interpretation 2 the statement seems to be false.
Suppose such a constant K exists. Then, let us write down all
of the programs of length at most K and run them in parallel.
Given there are N such programs, we can choose some M with
2^M > N, and wait until each of them prints the M-th bit of
the output or finishes execution. Then, there is surely a
string of length M which neither of them printed and for
which this can be proved (by the very experiment I am
describing).
Maybe you're using another interpretation of "print out":
3) As a substring positioned at the end of the output
but that would be somewhat strange.

Best regards,
Squark

.

Relevant Pages

  • Re: This Weeks Finds in Mathematical Physics (Week 226)
    ... Recall that the algorithmic entropy of a bitstring is defined ... machine print the string, and nothing else, and then halt. ...
    (sci.physics.research)
  • Re: clock scan oddity
    ... the same string with the character inserted. ... - no letter gives 6 hours differnce. ... rences given by the interpretation of different letters. ...
    (comp.lang.tcl)
  • Re: Incorrect use of documentary sources
    ... an interpretation, not word to word or literal translation. ... For example; " A string ... The above poster is again abusing this forum with his use of corrupt ...
    (rec.games.mahjong)
  • Re: info dicts?
    ... In my understanding is a dictionary just a specific interpretation of a ... string though. ... dict update dictionaryVariable key varName ?key varName ...? ...
    (comp.lang.tcl)
  • Re: Anonymous string constants
    ... If you want to save a string, ... "The interpretation semantics for S" are intended to provide a simple ... mechanism for entering a string in the interpretation state. ... ==> When the possibility of overwriting a string can arise, ...
    (comp.lang.forth)
Loading