Re: an true information theory
From: John Wilkins (johnSPAM_at_wilkins.id.au)
Date: 02/23/05
- Next message: Wayne Brown: "Re: From sign conventions to Galois Theory"
- Previous message: Sumo: "Re: Probability theory in (0,1) (Was Re: does sqrt(2) exist in CM?)"
- In reply to: examachine_at_gmail.com: "Re: an true information theory"
- Next in thread: examachine_at_gmail.com: "Re: an true information theory"
- Reply: examachine_at_gmail.com: "Re: an true information theory"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 23 Feb 2005 11:05:48 +1100
<examachine@gmail.com> wrote:
> 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?
Not that I know, but if you have a *real* UTM then of *course* you can
pass Omega to it :-)
Still, I will have to take your word for it. My schtick is biology, not
math.
>
> Regards,
>
> --
> Eray Ozkural
-- John S. Wilkins john@wilkins.id.au AA#2207 web: www.wilkins.id.au blog: evolvethought.blogspot.com Fiat lunch!
- Next message: Wayne Brown: "Re: From sign conventions to Galois Theory"
- Previous message: Sumo: "Re: Probability theory in (0,1) (Was Re: does sqrt(2) exist in CM?)"
- In reply to: examachine_at_gmail.com: "Re: an true information theory"
- Next in thread: examachine_at_gmail.com: "Re: an true information theory"
- Reply: examachine_at_gmail.com: "Re: an true information theory"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
