Re: an true information theory

examachine_at_gmail.com
Date: 02/22/05 

Date: 22 Feb 2005 02:24:45 -0800

examachine@gmail.com wrote:
> Note that algorithmic entropy is a syntactic theory. It says nothing
> about meaning, unless you apply it there. The relation between Omega
> and H(s) is obvious, H(s/Omega)=O(1), is that what you mean?

An error. I surely meant H( H(s) / Omega ) = O(1), that is: given an
oracle for the halting problem, there is a short constant program that
can enumerate the halting programs and find the length of the shortest
program that computes s.

This may have sounded confusing, so, here is a bit of explanation.

For lack of a better definition, I give pseudo-code, in AIT style. Note
that this is not really a computer program. You can't pass an infinite
string like Omega to a computer program. I'm pushing the defs a little
to make the point.

compute-H(s, Omega)
n <- 1
while true
  find all halting programs up to n-bits using Omega
  for each such program p in order of increasing size
    if U(p) = s
      return |p|
  n <- n + 1

where U(x) is the universal computer chosen.

The bit "find all halting programs up to n-bits using Omega" is
actually very easy. Time-share all 2^n programs. You know the first
n-bits of Omega, which tells you k programs halt. Keep running the
programs until exactly k programs halt, this is the set of halting
programs that you were looking for.

As you can see, this is not a grossly efficient procedure, but it's a
constant program. Anyway, it's a trivial observation, but perhaps there
is a better way to show it?

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: an true information theory
    ... The relation between Omega ... > can enumerate the halting programs and find the length of the shortest ... > that this is not really a computer program. ... which tells you k programs halt. ...
    (comp.theory)
  • Re: an true information theory
    ... The relation between Omega ... > can enumerate the halting programs and find the length of the shortest ... > that this is not really a computer program. ... which tells you k programs halt. ...
    (sci.math)
  • Re: an true information theory
    ... The relation between Omega ... can enumerate the halting programs and find the length of the shortest ... that this is not really a computer program. ... The bit "find all halting programs up to n-bits using Omega" is ...
    (comp.theory)