Re: My claim on Omega's defn

From: Arthur Fischer (arthurfischer_at_sym.ca)
Date: 01/31/05 

Date: Sun, 30 Jan 2005 22:24:03 -0500

|-|erc wrote:

> "Arthur Fischer" <arthurfischer@sym.ca> wrote in
>
>>|-|erc wrote:
>>
>>>Omega = sum( p halts) 1 / (2 ^ size(p))
>>>
>>> [big snip]
>>>
>>>Even with infinitesimally small total probability of halting, Omega will not converge and will equal oo.
>>
>>
>>You seem to be missing the point that the domain of the universal
>>self-delimiting TM U is taken to be prefix-free --- ie, the encoding of
>>halting TMs is such that if x is the encoding of some halting TM, then
>>no proper prefix of x is a encoding. Basically, any branch of the
>>infinite-binary tree will contain at most one such encoding, and so to
>>simply say that there are 2^n encoding with n bits is just being
>>ignorant. If follows via Kraft's inequality that Chaitin's Omega will
>>be bounded.
>
>
> So all Omega means is there exists 1 program of that size that halts.

No, what it does mean is that the set of encodings of programs is sparse
(quite possibly meagre) is the space of all finite binary strings. It
is a perhaps unnatural condition, but its what was done to ensure that
the "Omega series" converges.

> What a load of crap, I could design an arbirtrary UTM where Omega = 1.
>
> It skips 100% of programs without any reason.

Then this number really doesn't mean anything. We could all come up
with our own numerical constants, but unless there's a reason for them,
no-one will care. It's the natural interpretation that Chaitin was able
to get that makes it extremely worthwhile.

__
Arthur

Relevant Pages

  • Re: My claim on Omegas defn
    ... >>halting TMs is such that if x is the encoding of some halting TM, ... >>no proper prefix of x is a encoding. ... > So all Omega means is there exists 1 program of that size that halts. ... > It skips 100% of programs without any reason. ...
    (sci.math)
  • Re: My claim on Omegas defn
    ... >>halting TMs is such that if x is the encoding of some halting TM, ... >>no proper prefix of x is a encoding. ... > So all Omega means is there exists 1 program of that size that halts. ... > It skips 100% of programs without any reason. ...
    (comp.theory)
  • Re: Case-sensitivity as option?
    ... The reason why we chose case insensitivity in Gforth is to allow to ... in one encoding, but the system works with a different encoding). ... names might look strange when using a Latin-1 font (and vice versa for ...
    (comp.lang.forth)
  • Re: Unicode support
    ... I convert string to the form it was in the script file, ... Really, matter is more complicated, because if encoding system happens ... Second problem is that if I want for some reason to change encoding ... So I have to embed actual value of [encoding system] into procedure body ...
    (comp.lang.tcl)
  • Re: RESULT : Create moderated newsgroup uk.rec.cycling.moderatedPASSES 128:24
    ... For the obvious reason that HTML is not plain text, ... This is the reason for the UUEncoding (or more fashionably these days yenc ... encoding) of 8 bit binaries before posting them. ... Now HTML certainly qualifies as a form of encoding. ...
    (uk.net.news.config)