The world's smallest self-replicating program

[corwinbad]

phiX174 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

[jonmrodriguez]

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 to take part in refactoring that virus' genome into a decompressed version with no gene overlaps. And it worked! The decompressed version is still a functioning phage, and since there are no longer gene overlaps, future genetic engineers will have a much easier time modifying the phage as they see fit.

http://www.sciencedirect.com/science/article/pii/S0042682212...

[TazeTSchnitzel]

The Makefile is the most interesting part: http://www.ioccc.org/1994/Makefile

  smr: smr.c
  	@${RM} -rf smr
  	${CP} smr.c smr
  	${CHMOD} +x smr

Apparently, an empty file marked as executable will execute!

[TillE]

Because it's being interpreted as a shell script, I assume.

[Alupis]

I'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"?

[pdkl95]

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

Also, it is a valid C file!

    $ stat -c "%s" smr.c
    0
    $ gcc -Wall -c smr.c
    $ echo $?
    0
    $ stat -c "%s" smr.o
    927

The judge's comments for this one explain this in a bit more detail:

http://www.ioccc.org/1994/smr.hint

[1] the best kind of "valid" :)

[fsniper]

If you also look into the Makefile accompanied, it's just copying itself to smr file and giving it executable rights. So smr.c when built outputs it's source code.

The makefile is not large. It's a makefile for all the entries for 1994 competition. And it's only 4 lines for smr.c

[michael_fine]

I think what they were referring to was a quine

[avmich]

There is PDP-11 command (one word, 16 bits) which makes a copy of itself into a previous word (with address, in bytes, less by two) and passes the control to the new copy. Octal 103737... or something like that.

Doesn't require make :) or cp and is pretty active - fills up all the memory space below the starting point in no time.

[51Cards]

For those not understanding and wanting to see the "source" for this entry... it was a Zero byte file.

[TazeTSchnitzel]

Download here: http://www.ioccc.org/1994/smr.c

[silverfox17]

I hang out on /r/dailyprogrammer sometimes - they had a challenge about these types of programs the other day and called them "quines." Check through some of these if you're interested, a few are 2 characters long (not sure how many bytes that is): http://www.reddit.com/r/dailyprogrammer/comments/2n11w8/2014...

[TheSoftwareGuy]

2 characters is usually 2 bytes, unless they are using some weird unicode format, in which case it shouldn't be longer than 8 i think.

[sysk]

Is the copyright notice supposed to apply to the empty program?

[mojuba]

Not sure about the copyright, but I wouldn't be surprised if someone patented it in the US.

[mct]

I once wrote an implementation of the classic Redcode "Imp" program in x86 assembly. It does not satisfy the requirements of this contest, but it does act as the Imp program, perpetually copying itself through RAM. :-)

I just uploaded it to https://github.com/mct/assembly-toys/tree/master/imp

[ismailmechbal]

Related to this article is "Ken Thompson" reflections on Trusting Trust http://cm.bell-labs.com/who/ken/trust.html

[kremlin]

lol not quite in the spirit of the challenge.

[pdkl95]

Forcing the creation of a new contest rule is a tradition in the IOCCC.

[FireRabbit]

In redcode

    mov 0,1

is the smallest self-replicating program

[NaNaN]

Really a good joke for “Every TEXT is a quine.”

[Varcht]

Thanks, I was pretty messed up just now after watching the movie Pi, now I'm even worse....

[mjcohen]

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.

[disputin]

Isn't this a quine, rather than a self-replicating program? A quine produces the source, and a self-replicating program should produce an executable - no? This seems to be a fallacy of equivocation.

[palunon]

If you run it, it will replicate itself...

  $ ./smr >smr.out
  $ diff smr smr.out

[TazeTSchnitzel]

quines are a subset of self-replicating programs.

[chaosfox]

  smr: smr.c
  	@${RM} -rf smr
  	${CP} smr.c smr
  	${CHMOD} +x smr

this is bullshit if you ask me..

[simarpreet007]

Agreed, WTF.