--- Matt Mahoney <[EMAIL PROTECTED]> wrote:
> 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).
Here are 53 more:
main(_)(){}
main(a)(){}
main(b)(){}
...
main(Z)(){}
How many halting C programs are there of length 80 bits?
> 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();}
This halts when compiled with gcc -O (stack overflow but no apparent error)
but not with -O2 or higher. Compiling with -S shows that the tail recursion
is optimized into a loop.
-- 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
