Thanks, I was pretty messed up just now after watching the movie Pi, now I'm even worse....
In "Pi", the math is from the Dover book by Jahnke and Emde and the formula for the ratio of the sides of the rectangle is wrong.
The world's smallest self-replicating program
41–50 of 65 posts
Re: The world's smallest self-replicating program
#42Earlier quoted context omitted.
Actually, there was a story about somebody selling 0-byte executable for DOS allowing you to resume programs because of some peculiarity.
I'll be darned if I can find the URL to the story, but it is a brilliant application of giving the customer what they wanted. The short of it is that when you dropped back to the command line, early versions of DOS didn't clear the memory. That meant that the program really just went into stasis, but in practice it meant restarting; see, the program ran off the floppy then, so to save or load to another disk was tric…
Here you go: http://peetm.com/blog/?p=55
Re: The world's smallest self-replicating program
#43Earlier quoted context omitted.
Hehe funny that you mention phiX174 in the context of programming, that virus is amazing... Part of the reason phiX174 is so small is that it is "compressed" by having overlapping genes; in one area, three genes overlap in the same place! This is possible because there are 6 valid reading frames (direction and start point) for reading DNA: {forward or backward} x {address % 3 == 0, 1, or 2}. In college I actually got…
Hm, I used to work for Clyde Hutchison (and Ham Smith)... They told me that it didn't work when they made a naive decompression. Was there something they missed?
Did their naive decompression make the genome longer? If so, it probably didn't fit in the capsid. In our version, we had to provide one of the genes (gene F) in a plasmid in the host cell, in order to reduce the length of the decompressed genome to fit inside the capsid. See this section of our paper:
[The naive] decompression added 909 nucleotides to the wild-type genome. We next addressed practical constraints arising from the length of DNA that can be physically packaged within a øX174 capsid without impacts to reproductive fitness. Previous work has shown that the length of a øX174 genome, when packaged in vitro, must be kept within a few percent of the 5386 nucleotide wild-type length in order to avoid any significant fitness decrease ( Aoyama and Hayashi, 1985). Similar results were shown in vivo ( Russell and Muller, 1984). To reduce the decompressed genome length we removed the first 916 nucleotides of gene F, encoding the coat protein ( Air et al., 1978). We chose gene F because a plasmid containing a restriction fragment encoding wild-type gene F was able to complement two conditional gene F mutations ( Avoort et al., 1983). Additionally, the gene F coding sequence is greater than the total of the combined increases needed to implement the øX174.1 genome design. The truncated gene F version of the decompressed genome was named øX174.1f. To complement øX174.1f when transformed into host cells we designed a medium copy vector expressing gene F under control of a rhamnose-inducible promoter ( Fig. S1).
Re: The world's smallest self-replicating program
#44Earlier quoted context omitted.
Hehe funny that you mention phiX174 in the context of programming, that virus is amazing... Part of the reason phiX174 is so small is that it is "compressed" by having overlapping genes; in one area, three genes overlap in the same place! This is possible because there are 6 valid reading frames (direction and start point) for reading DNA: {forward or backward} x {address % 3 == 0, 1, or 2}. In college I actually got…
That's pretty amazing. I'm guessing DNA compactness is a survival advantage for viruses, and that's how this emerged? Is gene overlap common in other species?
Gene overlap is extremely rare actually! When phiX174 was first discovered, some researchers wondered if such a complexly intertwined system could even have evolved naturally, or if it might suggest that the virus was hand-engineered: http://adsabs.harvard.edu/abs/1979Icar...38..148Y
Re: The world's smallest self-replicating program
#45I'm not sure I understand how it's "self replicating"? An empty file, compiled or not, won't replicate itself. The Makefile to compile the empty c file is also rather large, but even it must be executed in a loop. Can someone explain the basis of this contest and how this c file is "self-replicating"?
It's abuse of the contest rules, which encouraged at the IOCCC. You just have to be absolutely certain that it really IS "technically valid"[1] or it risks disqualification.
This one abuses the idea that they specify how the contest will be judged, which this "program" satisfies, as long as you don't look at the source.
$ make smr
cp smr.c smr
chmod +x smr
$ ./smr > smr.dup
$ diff smr smr.dup
$ echo $?
0
$ stat -c "%s" smr.c
0
$ gcc -Wall -c smr.c
$ echo $?
0
$ stat -c "%s" smr.o
927
http://www.ioccc.org/1994/smr.hint
[1] the best kind of "valid" :)
Re: The world's smallest self-replicating program
#46lol not quite in the spirit of the challenge.
Forcing the creation of a new contest rule is a tradition in the IOCCC.
Speaking of rule abuse, I love this recent entry, which uses the IOCCC's own tool to calculate the size... and abuses a bug in it! It's mainly for a joke, though there IS a huge program-size abuse in the custom BIOS the program uses.
http://www.ioccc.org/2013/cable3/hint.html
*RULE 2 ABUSE DISCLAIMER*
- cable3.c is 4043 bytes in length (half an 8086)
- iocccsize -i Re: The world's smallest self-replicating program
#47Earlier quoted context omitted.
Hm, I used to work for Clyde Hutchison (and Ham Smith)... They told me that it didn't work when they made a naive decompression. Was there something they missed?
Did their naive decompression make the genome longer? If so, it probably didn't fit in the capsid. In our version, we had to provide one of the genes (gene F) in a plasmid in the host cell, in order to reduce the length of the decompressed genome to fit inside the capsid. See this section of our paper: [The naive] decompression added 909 nucleotides to the wild-type genome. We next addressed practical constraints ari…
ah, ok, had no idea that the capsid was that sensitive to genome length! Thanks! So it really did compress it for a useful purpose.
Re: The world's smallest self-replicating program
#48Earlier quoted context omitted.
Hehe funny that you mention phiX174 in the context of programming, that virus is amazing... Part of the reason phiX174 is so small is that it is "compressed" by having overlapping genes; in one area, three genes overlap in the same place! This is possible because there are 6 valid reading frames (direction and start point) for reading DNA: {forward or backward} x {address % 3 == 0, 1, or 2}. In college I actually got…
That's pretty amazing. I'm guessing DNA compactness is a survival advantage for viruses, and that's how this emerged? Is gene overlap common in other species?
I would think the opposite may be true, given that compressed information tends to be more sensitive to error, than uncompressed.
Re: The world's smallest self-replicating program
#49phiX174 virus - one of the world's smallest self-replicating programs :-) http://www.ncbi.nlm.nih.gov/nuccore/NC_001422.1 Enterobacteria phage phiX174 sensu lato, complete genome 5386 bp ss-DNA
Hehe funny that you mention phiX174 in the context of programming, that virus is amazing... Part of the reason phiX174 is so small is that it is "compressed" by having overlapping genes; in one area, three genes overlap in the same place! This is possible because there are 6 valid reading frames (direction and start point) for reading DNA: {forward or backward} x {address % 3 == 0, 1, or 2}. In college I actually got…
Overlapping instructions/data is something also commonly encountered in tiny demos (512b and below), e.g. http://meatfighter.com/puls/ and http://finalpatch.blogspot.ca/2014/06/dissecting-128-byte-ra...
I have no doubt that viruses of the computer kind also have made use of such techniques; and overlapping for obfuscation, not size-optimisation, is also a commonly seen trick in malware.
Re: The world's smallest self-replicating program
#50Earlier quoted context omitted.
No, without a shebang it is interpreted as a shell script.
Correct. A file will only be considered a binary executable if it has a proper header (ELF, Mach-O, etc) The default if no header and no shebang is to treat it like a shell script. In fact, an empty executable file has been used to implement /bin/true on some old systems. Why take the added cost of a disk seek when just the information in the inode will do?
>In fact, an empty executable file has been used to implement /bin/true on some old systems. Why take the added cost of a disk seek when just the information in the inode will do?
why is this only on old systems? it seems very efficient.