Re: ******** CAN ANYONE HERE DEFINE CHAITIN'S OMEGA ? ***********

From: |-|erc (H_at_r.c)
Date: 01/30/05 

Date: Mon, 31 Jan 2005 09:39:40 +1000

"The Ghost In The Machine" <ewill@sirius.athghost7038suus.net> wrote in
> >> >> omega_U = sum(n) ( ( Halts(f(n)) ? 1 : 0) * 2^bitsize(f(n)) )
> >> >
> >> > Say the halt sequence is
> >> >
> >> > 001001001001001001001
> >> >
> >> > what value does your formula give, for some rudimentary bitsize function?
> >> >
> >> > Herc
> >> >
> >>
> >> I don't know. I don't have the specifics handy at this point.
> >> This is one of the problems I have with Mr. Weisstein's
> >> definition; it's not quite specific enough. (He does give
> >> a reference to Sloane's papers, whoever Mr. Sloane is;
> >> I can't say I'm familiar with them.)
> >>
> >> I can define (and have defined) ad hoc machine specifications
> >> in the past; whether these lead to consistent definitions
> >> for Omega_U, I for one do not know, although I doubt it.
> >>
> >> Not that it matters. If Omega_U depends on the halting
> >> function, then Omega_U is inherently uncomputable, as
> >> the halting function is uncomputable (though it is well-defined).
> >>
> >> If you want I can exhume my machine definition (or make one
> >> comparable thereto), and then try to compute Omega_U
> >> for that machine definition. I'm not sure what that would
> >> prove, if anything.
> >>
> >
> > I gave you the initial segment of the values of Halt.
> >
> > HaltU(1) = 0
> > HaltU(2) = 0
> > HaltU(3) = 1
> > HaltU(4) = 0
> > HaltU(5) = 0
> > HaltU(6) = 1
> > ...
> >
> > omega_U = sum(n) ( ( Halts(f(n)) ? 1 : 0) * 2^bitsize(f(n)) )
> >
> > What more do you need to plug it in?
> >
> > Herc
> >
>
> If HaltU(n) = (n % 3 == 0) ? 1 : 0, then
> it depends on bitsize. Assuming bitsize = ceil(log2(n)),
> then omega_U = infinity.
>
> This is not in error although one might question the assumptions.
>

why is it not an error? why are adding exponential sums? when would it ever not be oo?

Herc

Relevant Pages