Universal (rule-bending) Code Golf solver Code golf always involves some answers that bend the rules more or less by breaking constraints that the challengers took for granted or just haven't thought about and didn't list in the rules. One of these interesting loopholes is the possibility to output more than the challenge asks for to get a better result.

Taking this to extremes, we can write an universal code golf solver that prints the desired output — if you don't care that it might take ages and outputs lots of other stuff before and after it.

All we need to output is a sequence that is guaranteed to contain every possible subsequence. For this code golf, this will be the Ehrenfeucht-Mycielski sequence:


  The sequence starts with the three bits 010; each successive digit is
  formed by finding the longest suffix of the sequence that also appears
  earlier within the sequence, and complementing the bit following the
  most recent earlier appearance of that suffix.
  
  Every finite subsequence of bits occurs contiguously, infinitely often
  within the sequence
  
  The first few digits of the sequence are:
  
  
    010011010111000100001111... (sequence A038219 in OEIS).
  


Combining 8 bits of the sequence to a byte, we'll get ASCII output that we can output to the screen or to a file and that contains every possible finite output. The program will output parts of pi, the lyrics of “Never gonna give you up”, some nice ASCII art, its own source code, and everything else you could want it to output.

For testing correctness, here are hashes for the first 256 bytes of the sequence:

MD5: 5dc589a06e5ca0cd9280a364a456d7a4
SHA-1: 657722ceef206ad22881ceba370d32c0960e267f


The first 8 bytes of the sequence in hexadecimal notation are:

4D 71 0F 65 27 46 0B 7C


Rules:


Your program must output the Ehrenfeucht-Mycielski sequence (nothing else), combining 8 bits to a byte/ASCII character.
Shortest program (character count) wins. Subtract 512 from your character count if you manage to generate the sequence in linear time per generated byte.
C, –110 chars

This version of the program uses the linear-runtime algorithm to generate the sequence. Subtracting 512 from the 402 chars in the program gives a total of negative 110.

#define C v=calloc(7,8),v-&gt;p=p
#define G(F,K)u-&gt;F[d[K]]
#define S(F,T)G(f,T)=F,G(t,T)=T,G(n,T)=
struct{int p,f[2],t[2];void*n[2];}r,*u,*v,*w;char*d,c;p,b,h,i,j,k;
main(s){for(;d=++p-s?d:realloc(d,s*=2);){d[i=p]=b;c+=c+b;p%8||putchar(c);
for(u=&amp;r;b=u-&gt;p,u-&gt;p=p,w=G(n,k=i);S(i,k)v=G(n,k),u=v)for(h=G(f,k),j=G(t,k);j&gt;h;--i,--j)
if(d[i]-d[j]){S(i,k)C;u=v;S(h,j)w;S(0,i)C;b=w-&gt;p;goto x;}S(0,i)C;x:b=1-d[b+1];}}


As per the problem, the program runs in an infinite loop, which necessitates lots of memory allocation, and using realloc() to keep the sequence contiguous can contribute to heap fragmentation. You can improve the program's memory usage by replacing calloc(7,8) on the first line with calloc(1,sizeof*v). This will help especially on a 32-bit machine, where 56 is likely too large by a factor of two.

The code is kind of unreadable, and not in an interesting way; for that I apologize. Frankly, even the ungolfed version isn't terribly clear:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

typedef struct branch branch;
typedef struct node node;

struct branch {
    int from, to;
    node *next;
};

struct node {
    int pos;
    branch br[2];
};

static node root = { 0 };

static unsigned char *data = NULL;
static int endpos = 0;
static int size = 1;

static node *mknode(void)
{
    node *n;

    n = calloc(1, sizeof *n);
    n-&gt;pos = endpos;
    return n;
}

static branch *getbranch(node *n, int p)
{
    return &amp;n-&gt;br[data[p]];
}

static void setbranch(node *n, int from, int to, node *next)
{
    n-&gt;br[data[to]].next = next;
    n-&gt;br[data[to]].from = from;
    n-&gt;br[data[to]].to = to;
}

int main(void)
{
    node *u, *v, *w;
    int follower, from, i, i0, j;
    int out, b;

    out = b = 0;
    for (;;) {
        ++endpos;
        if (endpos == size) {
            size *= 2;
            data = realloc(data, size);
        }
        data[endpos] = b;
        out = (out &lt;&lt; 1) | b;
        if (endpos % 8 == 0) {
            putchar(out);
            out = 0;
        }

        i = endpos;
        u = &amp;root;
        for (;;) {
            follower = u-&gt;pos + 1;
            u-&gt;pos = endpos;
            w = getbranch(u, i)-&gt;next;
            if (!w)
                break;
            i0 = i;
            from = getbranch(u, i0)-&gt;from;
            for (j = getbranch(u, i0)-&gt;to ; j &gt; from ; --j) {
                if (data[i] != data[j]) {
                    /* divide branch */
                    v = mknode();
                    setbranch(u, i, i0, v);
                    u = v;
                    setbranch(u, from, j, w);
                    setbranch(u, 0, i, mknode());
                    follower = w-&gt;pos + 1;
                    goto bitfound;
                }
                --i;
            }
            v = getbranch(u, i0)-&gt;next;
            setbranch(u, i, i0, v);
            u = v;
        }
        /* extend branch */
        setbranch(u, 0, i, mknode());

      bitfound:
        b = 1 - data[follower];
    }
}


(The ungolfed code above is based on the code written by Grzegorz Herman and Michael Soltys, as referenced in the problem description, and from Soltys' home page.)

Thanks to @schnaader and @r.e.s. for reporting a bug in the initial version.