--- Shane Legg <[EMAIL PROTECTED]> wrote:
> On 6/8/07, Matt Mahoney <[EMAIL PROTECTED]> wrote:
>
> > "The author has received reliable information, from a Source who wishes to
> > > remain anonymous, that the decimal expansion of Omega begins
> > >
> > > Omega = 0.9999998020554253273471801908..."
> >
> > For which choice of universal Turing machine?
>
>
>
> It's actually 0.00787499699781238...
>
> At least when based on the Turing machine described here:
>
> http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf
>
> Shane
It seems you could get fairly accurate approximations of Omega for other
languages like C using this approach. For example, there is (AFAIK) only one
C program of length 64 bits or less that halts:
main(){}
and you could possibly prove upper bounds on longer programs. Here are some
halting programs of length 72 bits:
;main(){}
main(){;}
main(){};
main(){}
main (){}
main( ){}
main() {}
main(){ }
main(){}
and others replacing the space with any of the ASCII codes 9, 10, 11, 12, or
13 (at least for gcc). That is 39 (unless I missed some). I think with some
work you could prove about 66 bits of Omega_C:
.0000000000000000000000000000000000000000000000000000000000000100
or 20 decimal digits:
.00000000000000000005
What is the shortest C program that does not halt? Here are some 136 bit
programs:
main(){while(1);}
main(){a:goto a;}
And a 128 bit program:
main(){for(;;);}
The following 120 bit program might run forever in some implementations:
main(){main();}
What is the shortest halting program in Java? I can find 2916 programs of
length 360 bits, but nothing shorter, for example:
class _{public static void main(String[]$){}}
unless you count programs that throw exceptions as legal, in which case you
can have 72 bits:
class x{}
-- Matt Mahoney, [EMAIL PROTECTED]
-----
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=231415&user_secret=e9e40a7e
