From kragen@dnaco.net Tue Aug 25 08:20:15 1998 Date: Tue, 25 Aug 1998 08:20:14 -0400 (EDT) From: Kragen To: hugi-compo@makelist.com Subject: Re: [hugi-compo] small life entries In-Reply-To: <35E296FD.1250488F@iname.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Keywords: X-UID: 1391 Status: O X-Status: On Tue, 25 Aug 1998 iopl3DEL@iname.com wrote: > [Kragen:] > > You know, small game-of-life programs are interesting in a way small > > Pong programs are not -- Life is, I believe, theoretically equivalent > > to a Turing machine in computational power. > > A gigantic Turing machine with 2^n states, where n = total no. of > cells. :) No, I don't think so; in order to simulate a Turing machine in Life, you'd need to use big chunks of cells to represent the head and the tape cells. > > int n,p=0,s=32;char*pt;main(int > > c,char**v){n=atol(v[1]);while(s!=33){pt=v[2]+3*(n*(s-32)+v[3][p]-32);s=pt[0]; > > v[3][p]=pt[1];p+=pt[2]-'|';}puts(v[3]);} > > Then again, an assembly language program (after compilation) might > be able to beat the above. :) In size, you mean? I'm sure of it! > Unfortunately, it seems that the idea of writing compact C code has > already been hacked to death (reminds me of all those obfuscated C > programs). Yes, I was looking at the IOCCC entries when I wrote that. > What's more, making the source small doesn't help to > make the resulting program small as well: it won't be very comforting > for the user to know that the source for the above program was only > 237 bytes when he finds out that the executable is 24K (which I > got). Well, my intent in posting this was to show that it's a fairly simple problem that could be expressed in that little space, using facilities similar to what you can use in assembly. My intent in writing it was to make an IOCCC entry. :) > While we're on the subject... anybody has any ideas on how to make > the Linux kernel smaller (and yet usable)? I'm running out of them... nm -v should tell you what the symbols remaining in your vmlinux are; a simple Perl script then should be able to show you how big each routine is. That might be a starting point for future reductions. Kragen -- Kragen Sitaker We are forming cells within a global brain and we are excited that we might start to think collectively. What becomes of us still hangs crucially on how we think individually. -- Tim Berners-Lee, inventor of the Web