text:
C: replace AES FIPS-197 SubBytes table by constant-time code
In FIPS-197 (the Advanced Encryption Standard, known as AES), it is made heavy use of SubBytes, which could be implemented as
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};
return t[x];}

This function is not arbitrary; it is a reversible mapping, consisting of an inversion in a Galois Field followed by an affine transformation. All the details are in FIPS-197 section 5.1.1 or here section 4.2.1 (under a slightly different name).
One problem with implementation as a table is that it opens to so-called cache-timing attacks.
Thus your mission is to devise an exact replacement for the above SubBytes() function, that exhibits constant-time behavior; we'll assume that's the case when nothing depending on the input x of SubBytes is used  either:

as an array index,
as the control operand of if, while, for, case, or operator ?:;
as any operand of operators &&, ||, !, ==, !=, <, >, <=, >=, *, /, %;
as the right operand of operators >>, <<, *=, /=, %=, <<=, >>=.

The winning entry will be one with the lowest cost, obtained from the number of operators executed in the input-dependent data path, with a weight of 5 for unary operators - and ~ as well as for <<1, >>1, +1, -1; weight of 7 for all other operators, shifts with other counts, or adds/subs of other constants (type casts and promotions are free). By principle, that cost is unchanged by unrolling loops (if any), and independent of the input x. As a tie-breaker, the answer with the shortest code after removing whitespace and comments wins.
I plan to designate an entry as answer as early as I can in year 2013, UTC. I will consider answers in languages that I've some knowledge of, ranking them as a straight translation to C not optimized for size.
Apologies for the initial omission of +1 and -1 in the favored operators, of free casts and promotions, and ranking of size. Note that * is prohibited both when unary, and as multiplication.

Worth noting that lookups are free because you can inline them as constants.

"early in year 2013, UTC" – wouldn't the date be more interesting than the time zone?

@PaŭloEbermann: My intention should be clear now.

See also http://codegolf.stackexchange.com/questions/3766/implement-rijndaels-s-box

Score: 940 933 926 910, field tower approach
public class SBox2
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    private static int SubBytes(int x) {
        int fwd;
        fwd  = 0x010001 & -(x & 1); x >>= 1; //   7+5+7+5+ | 24+
        fwd ^= 0x1d010f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x4f020b & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x450201 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xce080d & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xa20f0f & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0xc60805 & -(x & 1); x >>= 1; // 7+7+5+7+5+ | 31+
        fwd ^= 0x60070e & -x;                // 7+7+5+     | 19+

        // Running total so far: 229

        int p1;
        {
            int ma = fwd;
            int mb = fwd >> 16;         // 7+         | 7+
            p1  = ma & -(mb&1); ma<<=1; //   7+5+7+5+ | 24+
            p1 ^= ma & -(mb&2); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&4); ma<<=1; // 7+7+5+7+5+ | 31+
            p1 ^= ma & -(mb&8);         // 7+7+5+7+   | 26+
            int t = p1 >> 3;            // 7+         | 7+
            p1 ^= (t >> 1) ^ (t & 0xe); // 7+5+7+7+   | 26+
        }

        // Running total so far: 229 + 152 = 381

        int y3, y2, y1, y0;
        {
            int Kinv = (fwd >> 20) ^ p1;     // 7+7+
            int w0 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w1 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w2 = Kinv & 1; Kinv >>= 1;   // 7+5+
            int w3 = Kinv & 1;               // 7+

            int t0 = w1 ^ w0 ^ (w2 & w3);      // 7+7+7+
            int t1 = w2 ^ (w0 | w3);           // 7+7+
            int t2 = t0 ^ t1;                  // 7+

            y3 = t2 ^ (t1 & (w1 & w3));        // 7+7+7+
            y2 = t0 ^ (w0 | t2);               // 7+7+
            y1 = w0 ^ w3 ^ (t1 & t0);          // 7+7+7+
            y0 = w3 ^ (t0 | (w1 ^ (w0 | w2))); // 7+7+7+7

        }

        // Running total so far: 381 + 24*7 + 3*5 = 564

        int p2;
        {
            int ma = fwd;
            p2  = ma & -y0; ma<<=1;       //   7+5+5+ | 17+
            p2 ^= ma & -y1; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y2; ma<<=1;       // 7+7+5+5+ | 24+
            p2 ^= ma & -y3;               // 7+7+5+   | 19+
            int t = p2 >> 3;              // 7+       | 7+
            p2 ^= (t >> 1) ^ (t & 0xe0e); // 7+5+7+7+ | 26
        }

        // Running total so far: 564 + 117 = 681

        int inv8;
        inv8  =  31 & -(p2 & 1);           //   7+5+7+   | 19+
        inv8 ^= 178 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 171 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  54 & -(p2 & 2); p2 >>= 6; // 7+7+5+7+7+ | 33+
        inv8 ^= 188 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^=  76 & -(p2 & 2); p2 >>= 2; // 7+7+5+7+7+ | 33+
        inv8 ^= 127 & -(p2 & 1);           // 7+7+5+7+   | 26+
        inv8 ^= 222 & -(p2 & 2);           // 7+7+5+7    | 26+

        return inv8 ^ 0x63;                // 7+         | 7+

        // Grand total: 681 + 229 = 910
    }
}

The structure is essentially the same as Boyar and Peralta's implementation - reduce inversion in GF(2^8) to inversion in GF(2^4), break it down into a linear prologue, a non-linear body, and a linear epilogue, and then minimise them separately. I pay some penalties for bit extraction, but I compensate by being able to do operations in parallel (with some judicious padding of the bits of fwd). In more detail...
Background
As mentioned in the problem description, the S-box consists of an inversion in a particular implementation of the Galois field GF(2^8) followed by an affine transformation. If you know what both of those mean, skip this section.
An affine (or linear) transformation is a function f(x) which respects f(x + y) = f(x) + f(y) and f(a*x) = a*f(x).
A field is a set F of elements with two special elements, which we'll call 0 and 1, and two operators, which we'll call + and *, which respects various properties. In this section, assume that x, y, and z are elements of F.

The elements of F form an abelian group under + with 0 as the identity: i.e. x + y is an element of F; x + 0 = 0 + x = x; each x has a corresponding -x such that x + (-x) = (-x) + x = 0; x + (y + z) = (x + y) + z; and x + y = y + x.
The elements of F other than 0 form an abelian group under * with 1 as the identity.
Multiplication distributes over addition: x * (y + z) = (x * y) + (x * z).

It turns out that there are some quite severe limitations on finite fields:

They must have a number of elements which is a power of a prime.
They are isomorphic with all other finite fields of the same size (i.e. there's really only one finite field of a given size, and any others are just relabellings; call that field GF(p^k) where p is the prime and k is the power).
The multiplicative group F\{0} under * is cyclic; i.e. there's at least one element g such that every element is a power of g.
For powers greater than 1 there is a representation as univariate polynomials of order k of the field of the prime order. E.g. GF(2^8) has a representation in terms of polynomials of x over GF(2). In fact there's usually more than one representation. Consider x^7 * x in GF(2^8); it must be equivalent to some order-7 polynomial, but which? There are a lot of choices which give the right structure; AES chooses to make x^8 = x^4 + x^3 + x + 1 (the lexicographically smallest polynomial which works).

So how do we compute an inverse in that particular representation of GF(2^8)? It's too chunky a problem to tackle directly, so we need to break it down.
Field towers: representing GF(2^8) in terms of GF(2^4)
Instead of representing GF(2^8) with polynomials of 8 terms over GF(2) we can represent it with polynomials of 2 terms over GF(2^4). This time we need to choose a linear polynomial for x^2. Suppose we choose x^2 = px + q. Then (ax + b) * (cx + d) = (ad + bc + acp)x + (bd + acq).
Is it easier to find an inverse in this representation? If (cx + d) = (ax + b)^-1 we get the simultaneous equations

ad + (b + ap)c = 0
bd +     (aq)c = 1

Let D = [b(b+ap) + a^2 q] and set c = a * D^-1; d = (b + ap) * D^-1. So we can do an inverse in GF(2^8) for the cost of a conversion to GF(2^4), an inverse and a few additions and multiplications in GF(2^4), and a conversion back. Even if we do the inverse by means of a table, we've reduced the table size from 256 to 16.
Implementation details
To construct a representation of GF(4) we can choose between three polynomials to reduce x^4:

x^4 = x + 1
x^4 = x^3 + 1
x^4 = x^3 + x^2 + x + 1

The most important difference is in the implementation of multiplication. For any of the three (which correspond to poly of 3, 9, f) the following will work:
// 14x &, 7x unary -, 3x <<1, 3x >>1, 3x >>3, 6x ^ gives score 226
int mul(int a, int b) {
    // Call current values a = a0, b = b0
    int p = a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x); a = a0 x; b = b0 div x

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^2); a = a0 x^2; b = b0 div x^2

    p ^= a & -(b & 1);
    a = ((a << 1) ^ (poly & -(a >> 3))) & 15;
    b >>= 1;
    // Now p = a0 * (b0 mod x^3); a = a0 x^3; b = b0 div x^3

    p ^= a & -(b & 1);
    // p = a0 * b0

    return p;
}

However, if we choose poly = 3 we can handle the overflow much more efficiently because it has a nice structure: there's no double-overflow, because the two inputs are both cubics and x^6 = x^2 (x + 1) is also cubic. In addition we can save the shifts of b: since we're leaving the overflow to last, a0 x^2 doesn't have any set bits corresponding to x or 1 and so we can mask it with -4 instead of -1. The result is
// 10x &, 4x unary -, 3x <<1, 1x >>1, 1x >>3, 5x ^ gives score 152
int mul(int a, int b) {
    int p;
    p  = a & -(b & 1); a <<= 1;
    p ^= a & -(b & 2); a <<= 1;
    p ^= a & -(b & 4); a <<= 1;
    p ^= a & -(b & 8);
    // Here p = a0 * b0 but with overflow, which we need to bring back down.

    int t = p >> 3;
    p ^= (t >> 1) ^ (t & 0xe);
    return p & 15;
}

We still need to choose the values of p and q for the representation of GF(2^8) over GF(2^4), but we don't have many constraints on them. The one thing that matters is that we can get a linear function from the bits of our original representation to the bits of the working representation. This matters for two reasons: firstly, it's easy to do linear transformations, whereas a non-linear transformation would require optimisation equivalent in difficulty to just optimising the entire S-box; secondly, because we can get some side benefits. To recap the structure:
GF256 SubBytes(GF256 x) {
    GF16 a, b, t, D, Dinv, c, d;

    (a, b) = f(x); // f is linear

    t = b + a * p;
    D = b * t + a * a * q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d); // finv is also linear
}

If the bits of x are x7 x6 ... x0 then since the transform is linear we get a = f({x7}0000000 + 0{x6}000000 + ... + 0000000{x0}) = f({x7}0000000) + f(0{x6}000000) + ... + f(0000000{x0}). Square it and we get a^2 = f({x7}0000000)^2 + f(0{x6}000000)^2 + ... + f(0000000{x0})^2 where the cross-terms cancel (because in GF(2), 1 + 1 = 0). So a^2 can also be computed as a linear function of x. We can augment the forward linear transform to get:
GF256 SubBytes(GF256 x) {
    GF16 a, b, t, a2q, D, Dinv, c, d;

    (a, b, t, a2q) = faug(x);

    D = b * t + a2q;
    Dinv = inverse_GF16(D);
    c = a * Dinv;
    d = t * Dinv;

    return finv(c, d);
}

and we're down to three multiplications and one addition. We can also extend the multiplication code to do the two multiplications by Dinv in parallel. So our total cost is a forward linear transformation, an addition, two multiplications, an inverse in GF(2^4), and a back linear transformation. We can roll in the post-inverse linear transformation of the S-box and get that essentially for free.
The computation of the coefficients for the linear transformations isn't very interesting, and nor is the micro-optimisation to save a mask here and a shift there. The remaining interesting part is the optimisation of inverse_GF16. There are 2^64 different functions from 4 bits to 4 bits, so a direct optimisation requires lots of memory and time. What I've done is to consider 4 functions from 4 bits to 1 bit, place a cap on the total cost permitted for any one function (with a maximum cost of 63 per function I can enumerate all suitable expressions in under a minute), and for each tuple of functions do common subexpression elimination. After 25 minutes of crunching, I find that the best inverse possible with that cap has a total cost of 133 (an average of 33.25 per bit of the output, which isn't bad considering that the cheapest expression for any individual bit is 35).
I'm still experimenting with other approaches to minimise the inversion in GF(2^4), and an approach which builds bottom-up rather than top-down has yielded an improvement from 133 to 126.

Fantastic! I confirm it works! A detail: the 8th & 1 can be trimmed (esp. if x is unsigned char; CHAR_BIT is 8 in codegolf).

@fgrieu, good point.

Score: 980=7*5+115*7+7*5+15*7, Boyar and Peralta's minimization
I found A new combinational logic minimization technique with applications to cryptology by Joan Boyar and René Peralta, which (save for the C formalism) does what's required. The technique used to derive their equations is patented by no less than the USA. I just did a straight C translation of their equations, kindly linked here.
unsigned char SubBytes_Boyar_Peralta(unsigned char x7){
  unsigned char
  x6=x7>>1,x5=x6>>1,x4=x5>>1,x3=x4>>1,x2=x3>>1,x1=x2>>1,x0=x1>>1,
  y14=x3^x5,y13=x0^x6,y9=x0^x3,y8=x0^x5,t0=x1^x2,y1=t0^x7,y4=y1^x3,y12=y13^y14,y2=y1^x0,
  y5=y1^x6,y3=y5^y8,t1=x4^y12,y15=t1^x5,y20=t1^x1,y6=y15^x7,y10=y15^t0,y11=y20^y9,y7=x7^y11,
  y17=y10^y11,y19=y10^y8,y16=t0^y11,y21=y13^y16,y18=x0^y16,t2=y12&y15,t3=y3&y6,t4=t3^t2,
  t5=y4&x7,t6=t5^t2,t7=y13&y16,t8=y5&y1,t9=t8^t7,t10=y2&y7,t11=t10^t7,t12=y9&y11,
  t13=y14&y17,t14=t13^t12,t15=y8&y10,t16=t15^t12,t17=t4^t14,t18=t6^t16,t19=t9^t14,
  t20=t11^t16,t21=t17^y20,t22=t18^y19,t23=t19^y21,t24=t20^y18,t25=t21^t22,t26=t21&t23,
  t27=t24^t26,t28=t25&t27,t29=t28^t22,t30=t23^t24,t31=t22^t26,t32=t31&t30,t33=t32^t24,
  t34=t23^t33,t35=t27^t33,t36=t24&t35,t37=t36^t34,t38=t27^t36,t39=t29&t38,t40=t25^t39,
  t41=t40^t37,t42=t29^t33,t43=t29^t40,t44=t33^t37,t45=t42^t41,z0=t44&y15,z1=t37&y6,
  z2=t33&x7,z3=t43&y16,z4=t40&y1,z5=t29&y7,z6=t42&y11,z7=t45&y17,z8=t41&y10,z9=t44&y12,
  z10=t37&y3,z11=t33&y4,z12=t43&y13,z13=t40&y5,z14=t29&y2,z15=t42&y9,z16=t45&y14,z17=t41&y8,
  t46=z15^z16,t47=z10^z11,t48=z5^z13,t49=z9^z10,t50=z2^z12,t51=z2^z5,t52=z7^z8,t53=z0^z3,
  t54=z6^z7,t55=z16^z17,t56=z12^t48,t57=t50^t53,t58=z4^t46,t59=z3^t54,t60=t46^t57,
  t61=z14^t57,t62=t52^t58,t63=t49^t58,t64=z4^t59,t65=t61^t62,t66=z1^t63,s0=t59^t63,
  s6=t56^t62,s7=t48^t60,t67=t64^t65,s3=t53^t66,s4=t51^t66,s5=t47^t65,s1=t64^s3,s2=t55^t67;
  return (((((((s0<<1|s1&1)<<1|s2&1)<<1|s3&1)<<1|s4&1)<<1|s5&1)<<1|s6&1)<<1|s7&1)^0x63;}

Wow, really works, and really cheap. When disassembling, it's indeed 144 instructions, excluding prologue, epilogie and move instructions.

Score: 10965
This uses the same principle of unrolling the array lookup. May require extra casts.
Thanks to ugoren for pointing out how to improve is_zero.
// Cost: 255 * (5+7+24+7) = 10965
unsigned char SubBytes(unsigned char x) {
    unsigned char r = 0x63;
    char c = (char)x;
    c--; r ^= is_zero(c) & (0x63^0x7c); // 5+7+24+7 inlining the final xor
    c--; r ^= is_zero(c) & (0x63^0x77); // 5+7+24+7
    // ...
    c--; r ^= is_zero(c) & (0x63^0x16); // 5+7+24+7
    return r;
}

// Cost: 24
// Returns (unsigned char)-1 when input is 0 and 0 otherwise
unsigned char is_zero(char c) {
    // Shifting a signed number right is unspecified, so use unsigned
    unsigned char u;
    c |= -c;               // 7+5+
    u = (unsigned char)c;
    u >>= (CHAR_BITS - 1); // 7+
    c = (char)u;
    // c is 0 if we want -1 and 1 otherwise.
    c--;                   // 5
    return (unsigned char)c;
}

For an integer c, (c|-c)>>31 is 0 for 0 and -1 otherwise.

@ugoren, in sensible languages, yes. In C, right shifting an unsigned type is unspecified.

I guess you mean signed. But this site isn't really famed for strict standard compliance. Also, your c >> 4 seems like signed right shift to me. And if you really insist - ((unsigned int)(c|-c))>>31 is c?1:0.

@ugoren, you're right, I meant signed. The c >>4 works with or without sign extension. But good catch on using an unsigned shift: will edit when I get home and can use a proper computer rather than a phone. Thanks.

Score: 9109, algebraic approach
I'll leave the lookup approach in case anyone can improve it drastically, but it turns out that a good algebraic approach is possible. This implementation finds the multiplicative inverse using Euclid's algorithm. I've written it in Java but in principle it can be ported to C - I've commented the parts which would change if you want to rework it using only 8-bit types.
Thanks to ugoren for pointing out how to shorten the is_nonzero check in a comment on my other answer.
public class SBox
{
    public static void main(String[] args)
    {
        for (int i = 0; i < 256; i++) {
            int s = SubBytes(i);
            System.out.format("%02x  ", s);
            if (i % 16 == 15) System.out.println();
        }
    }

    // Total cost: 9109
    public static int SubBytes(int x)
    {
        x = inv_euclid(x); // 9041
        x = affine(x);     // 68
        return x;
    }

    // Total cost: 68
    private static int affine(int s0) {
        int s = s0;
        s ^= (s0 << 1) ^ (s0 >> 7); // 5 + 7
        s ^= (s0 << 2) ^ (s0 >> 6); // 7 + 7
        s ^= (s0 << 3) ^ (s0 >> 5); // 7 + 7
        s ^= (s0 << 4) ^ (s0 >> 4); // 7 + 7
        return (s ^ 0x63) & 0xff;   // 7 + 7
    }

    // Does the inverse in the Galois field for a total cost of 24 + 9010 + 7 = 9041
    private static int inv_euclid(int s) {
        // The first part of handling the special case: cost of 24
        int zeromask = is_nonzero(s);

        // NB the special value of r would complicate the unrolling slightly with unsigned bytes
        int r = 0x11b, a = 0, b = 1;

        // Total cost of loop: 7*(29+233+566+503+28) - 503 = 9010
        for (int depth = 0; depth < 7; depth++) { // 7*(
            // Calculate mask to fake out when we're looping further than necessary: cost 29
            int mask = is_nonzero(s >> 1);

            // Cost: 233
            int ord = polynomial_order(s);

            // This next block does div/rem at a total cost of 6*(24+49) + 69 + 59 = 566
            int quot = 0, rem = r;
            for (int i = 7; i > 1; i--) {                   // 6*(
                int divmask = is_nonzero(ord & (rem >> i)); // 24+7+7
                quot ^= (1 << i) & divmask;                 // 7+0+7+ since 1<<i is inlined on unrolling
                rem ^= (s << i) & divmask;                  // 7+7+7) +
            }
            int divmask1 = is_nonzero(ord & (rem >> 1));    // 24+7+5
            quot ^= 2 & divmask1;                           // 7+7+
            rem ^= (s << 1) & divmask1;                     // 7+5+7+
            int divmask0 = is_nonzero(ord & rem);           // 24+7
            quot ^= 1 & divmask0;                           // 7+7+
            rem ^= s & divmask0;                            // 7+7

            // This next block does the rest for the cost of a mul (503) plus 28
            // When depth = 0, b = 1 so we can skip the mul on unrolling
            r = s;
            s = rem;
            quot = mul(quot, b) ^ a;
            a = b;
            b ^= (quot ^ b) & mask;
        }

        // The rest of handling the special case: cost 7
        return b & zeromask;
    }

    // Gets the highest set bit in the input. Assumes that it's always at least 1<<1
    // Cost: 233
    private static int polynomial_order(int s) {
        int ord = 2;
        ord ^= 6 & -((s >> 2) & 1);           // 7+7+5+7+7 = 33 +
        ord ^= (ord ^ 8) & -((s >> 3) & 1);   // 7+7+7+5+7+7 = 40 +
        ord ^= (ord ^ 16) & -((s >> 4) & 1);  // 40 +
        ord ^= (ord ^ 32) & -((s >> 5) & 1);  // 40 +
        ord ^= (ord ^ 64) & -((s >> 6) & 1);  // 40 +
        ord ^= (ord ^ 128) & -((s >> 7) & 1); // 40
        return ord;
    }

    // Returns 0 if c is 0 and -1 otherwise
    // Cost: 24
    private static int is_nonzero(int c) {
        c |= -c;   // 7+5+
        c >>>= 31; // 7+ (simulating a cast to unsigned and right shift by CHAR_BIT)
        c = -c;    // 5+ (could be saved assuming a particular implementation of signed right shift)
        return c;
    }

    // Performs a multiplication in the Rijndael finite field
    // Cost: 503 (496 if working with unsigned bytes)
    private static int mul(int a, int b) {
        int p = 0;
        for (int counter = 0; counter < 8; counter++) { // 8*(_+_
            p ^= a & -(b & 1);                          // +7+7+5+7
            a = (a << 1) ^ (0x1b & -(a >> 7));          // +5+7+7+5+7
            b >>= 1;                                    // +5)
        }
        p &= 0xff;                                      // +7 avoidable with unsigned bytes
        return p;
    }
}

Score: 256*(7+(8*(7+7+7)-(2+2))+5+7+7)=48640 (assuming loops unrolled)
unsigned char SubBytes(unsigned char x) {
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

unsigned char ret_val = 0;
int i,j;
for(i=0;i<256;i++) {
  unsigned char is_index = (x ^ ((unsigned char) i));
  for(j=0;j<8;j++) {
   is_index |= (is_index << (1 << j)) | (is_index >> (1 << j));
  }
  is_index = ~is_index;
  ret_val |= is_index & t[i];
}

return ret_val;}

Explanation:
Essentially an array lookup reimplemented using bitwise operators and always processing the entire array.  We loop through the array, and xor x with each index, then use bitwise operators to logically negate the result, so we get 255 when x=i and 0 otherwise. We bitwise-and this with the array-value, so that the chosen value is unchanged and the others become 0.  Then we take the bitwise-or of this array, thereby pulling out only the chosen value.
The two 1 << j operations would go away as part of unrolling the loop, replacing them with the powers of 2 from 1 through 128.

Now to see if it's possible to actually do the math using bitwise operators.

Looking through the algorithm here, I kind of doubt it'll be possible to implement the polynomial inversion without looping over all bytes at least once as a substitute for some of the polynomial-time steps. So this might well beat any "smart" solutions. I suspect tuning this constant-time array lookup is a more promising avenue.

Nice. The function rj_sbox in aes.c here might give inspiration (although, as is, it does not match the question).

Where does the -(2+2) in your scoring calculation come from? Edit: ah, inlining creates a <<1 and a >>1.

Score 1968 1692, using the lookup table
Note: This solution doesn't pass the criteria, because of w >> b.
Using the lookup table, but reading 8 bytes at a time.
3*7 + 32 * (6*7 + 2*5) + 7 = 692
unsigned char SubBytes(unsigned char x){

static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

  unsigned long long *t2 = (unsigned long long *)t;
  int a = x>>3, b=(x&7)<<3;                       // 7+7+7
  int i;
  int ret = 0;
  for (i=0;i<256/8;i++) {                         // 32 *
      unsigned long long w = t2[i];
      int badi = ((unsigned int)(a|-a))>>31;      // 7+7+5
      w &= (badi-1);                              // +7+7
      a--;                                        // +5
      ret |= w >> b;                              // +7+7
  }
  return ret & 0xff;                              // +7
}

I don't think this meets the definition of constant time in the question, because w>>b has RHS calculated from x

There are several violations: w >> b where b depends on input; also x/8, x%8, and *= (1-badi). The first one is especially likely to degenerate into a timing dependency on low-end CPUs. However, the idea of using wide variables certainly has potential.

I didn't read the instructions carefully enough. I can fix most of the problems, but w >> b is quite essential (I need to see if it can be fixed without rewriting everything.

Table lookup and mask, score = 256 * (5*7+1*5) = 10240
Uses table lookup with a mask to pick out only the result we want.  Uses the fact that j|-j is either negative (when i!=x) or zero (when i==x).  Shifting makes an all-one or all-zero mask which is used to select out only the entry we want.
static const unsigned char t[256] = {
  0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,
  0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,
  0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,
  0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,
  0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,
  0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,
  0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,
  0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,
  0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,
  0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,
  0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,
  0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,
  0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,
  0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,
  0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,
  0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};

unsigned char SubBytes(unsigned char x) {
  unsigned char r = 255;
  for (int i = 0; i < 256; i++) {
    int j = i - x;
    r &= t[i] | ((j | -j) >> 31);
  }
  return r;
}

Isn't this the same as my second answer except less optimised?

Close, I guess.  I'm using signed shift so I don't have to do the -1 at the end.


text:
Simulate the Wireworld cellular automaton
Wireworld is a cellular automaton that was designed to be resemble electrons flowing through wires. Its simple mechanics allow the construction of digital circuits.  It has even permitted the construction of an entire computer.
Your mission is to create the shortest Wireworld implementation in your language of choice.
Each cell in the grid has one out of four states.  The four states are "blank," "copper," "electron head," or "electron tail."

A blank cell will always remain a blank cell
An electron head will always become an electron tail
An electron tail will always become copper
A copper cell will become an electron head iff exactly one or two out of its eight neighbors are electron heads, otherwise it will remain copper

This competition will have a similar style to the Shortest Game of Life competition, but with a few changes.

The grid must be at least 40 by 40 cells
The edges of the grid must NOT wrap around (not a torus). Treat cells outside of the field as being constantly "blank."
It must be possible for the users to enter their own starting configuration.
Staring at blank screens is not fun.  The program must visually display the simulation as it is running.

This is code golf,  fewest bytes wins.

APL, Dyalog (131)
{h t c←1↓⍵∘=¨F←' htc'⋄⎕SM∘←1 1,⍨⊂N←F[1+⊃+/H h(t∨c≠H←c∧S↑1 1↓1 2∊⍨⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂¯1⌽¯1⊖h↑⍨2+S←25 79)×¨⍳3]⋄∇N⊣⎕DL÷4}↑{79↑⍞}¨⍳25

The output is displayed in the ⎕SM window. The simulation runs endlessly. The grid is 79x25 because that's the default size of the ⎕SM window. The electron head is h, tail is t, copper is c. The program reads the starting configuration from the keyboard as 25 lines.
Explanation:

↑{79↑⍞}¨⍳25: read the 79x25 grid
h t c←1↓⍵∘=¨F←' htc': get three matrices, one with the heads, one with the tails and one with the copper. Also set F to the string ' htc'.
⎕SM∘←1 1,⍨⊂N←F[1+⊃+/...×¨⍳3]: The "..." part is a vector of length three, where the elements are matrices showing the new heads, tails, and copper respectively. The heads are multiplied by 1, the tails by 2, and the copper by 3, then we sum these matrices together and add one, giving a matrix of indices into F. N becomes the new state, in the same format as the input, and it is shown on the ⎕SM screen starting from the top-left corner.
¯1⌽¯1⊖h↑⍨2+S←25 79: Add a border of blanks to h by growing it by two rows and columns, then rotating it one right and one down.
⊃+/+/K∘.⊖(K←2-⍳3)∘.⌽⊂: Rotate the matrix in all eight directions and then sum the resulting matrices together, giving the amount of neighbours that are heads on each position.
1 2∊⍨: Set only those positions to 1 which have 1 or 2 neighbours.
S↑1 1↓: Remove the border we added earlier.
H←c∧: The new heads are all those copper cells that have 1 or 2 head neighbours.
t∨c≠H: The new copper cells are all old tails, and all old copper cells that have not become heads.
H h(...): The new heads are H as calculated above, the new tails are the old heads, and the new copper cells are as calculated above.
∇N⊣⎕DL÷4: Wait 1/4th of a second, then run the function again on N.

I think it'd be better if it could contain a 40 by 40 grid.

ALPACA, 82 chars
ALPACA is a language specifically designed for cellular automatons.
o is nothing; c is conductor; e is electron; t is electron tail.
state o " ";
state c "c" to e when 1 e or 2 e;
state e "e" to t;
state t "t" to c.

When was this language released ? Are there any links for the language ?

@Optimizer Here you go! I didn't make the language.

Cool. Right language for the right challenge..

GolfScript (125 120 105 100 chars)
n%{.,,{1${.0=,:w[1,*]\+2*>3<}:^~`{zip^''+.4=5%'`X '@{+}*(7&1>'iX'>+=}+w,%}%"\033[H\033[J"@n*+puts 6.?.?}do

Note that I'm counting the \033 as one character each, because they can be replaced by a literal ESC character. This uses ANSI control codes, so relies on a compatible tty. Also note that frames are printed starting with the input grid.
There is some overlap with Generate a grid of sums, which also uses the Moore neighbourhood.
Encoding: blank space => ; electron head => i; electron tail => `; copper => X.
The pause between iterations is the time required to calculate 4665646656. Changing 6.?.? to another expression allows you to control the speed; the next slowest for the same character count is 7.?.?, which is much slower (the output is 22 times as big, and it's not a linear complexity calculation).
For a test case, I've been using
`iXXXXXXXXX
X   X
   XXX
X   X
i`XX XXXXXX

from the Rosetta Code Wireworld challenge.

Python (243 214)
Tried to make a cross between usability and characters. The grid is 40x40. Input is given on stdin. An electron head is h, electron tail is t, copper is c, anything else is blank.
import os
f=raw_input()
while 1:f=''.join('h'if(i=='c')&(0<sum(1 for i in[-1,1,-39,-40,-41,39,40,41]if f[e+i:e+i+1]=='h')<3)else't'if i=='h'else'c'if i=='t'else f[e]for e,i in enumerate(f));os.system('cls');print f

The while loop (line 3) uncompressed (will not work if placed in code):
while 1:
 for e,i in enumerate(f):
  if(i=='c')&(0<sum(1 for i in[-1,1,-39,-40,-41,39,40,41]if f[e+i:e+i+1]=='h')<3):f[e]='h'
  elif i=='h':f[e]='t'
  elif i=='t':f[e]='c'
  else:f[e]=f[e]  #redundant, but Python needs this to run
 os.system('cls') #cls is shorter than clear, so I used that
 print f

I think you can replace lines 5-7 with a single expression: g[e]='h'if(t=='c')&...else't'if i=='h'else'c'if i=='t'else i. Not sure if that works exactly as is, but something along those lines should work

Python 371 341 chars
Yeah, it's not that short, but it has an interactive gui!
import matplotlib.pylab as l,scipy.ndimage as i
r=round
w=l.zeros((40,40),int)-1
p=l.matshow(w,vmax=2)
c=p.figure.canvas
def h(e):
 try:w[r(e.ydata),r(e.xdata)]=[0,2,-1][e.button-1]
 except:x=i.convolve(w==2,l.ones((3,3)),int,'constant');w[:]=w/2+((w==0)&(x>0)&(x<3))*2
 p.set_data(w);c.draw()
c.mpl_connect('button_press_event',h)
l.show()

Instructions:
Click with left mouse button to place wire
Click with right mouse button to clear
Click with middle mouse button to place electron head
Click outside the axes to step the automaton

(x>0)&(x<3) -> (0<x<3). :)

C, 355 347 300 294 chars
Edit: realized I don't need feof()
Edit: Saved 47 chars! Removed the Sleep, got rid of almost all braces, combined a lot of operations.
Edit: Last one today, since I broke 300 chars. Changed printf to puts, found a cute little optimization with the first comparison.
C does not lend itself well to this sort of problem, but hey, golfing it is fun. This is a pretty brute-force implementation, but I wanted to see how far I could golf it up.
Input is a text file named i. It contains a representation of the starting state, with * for copper, + for electron head, - for electron tail, spaces for empty cells. I'm using the XOR gate from the wiki page for testing.
   ****-+**
  +        ******
   -*******      *
                ****
                *  *****
                ****
   ********      *
  +        ******
   -****+-*

char*p,t[42][42],s[42][42];
main(i,r,c,n,j)
{
  for(p=fopen("i","r");fgets(s[i++]+1,40,p););

  for(;;getch(),memcpy(s,t,1764))
    for(j=1;j<41;puts(s[j++]+1))
      for(i=1;i<41;)
      {
        p=t[j]+i;
        r=s[j][i++];
        *p=r==43?45:r;
        if(r==45)
          *p=42;
        if(r==42)
          for(r=-1,n=0;r<2;++r,*p=n&&n<3?43:42)
            for(c=-2;c<1;)
              n+=s[j+r][i+c++]==43;
      }
}

Could cond?43:42 be written 42+(cond)? And I'm sure r=s[j][i++];*p=r==43?45:r;if(r==45)*p=42; can be reduced to r=s[j][i++];*p=r==43?45:r==45?42:r; if not to r=s[j][i++]-43;*p=!r?45:r==2?42:r;

Python, 234 218 chars
import time
I=input
C=I()
H=I()
T=I()
R=range(40)
while 1:
 for y in R:print''.join(' CHT'[(C+H+2*T).count(x+y*1j)]for x in R)
 H,T=[c for c in C if 0<sum(1 for h in H if abs(c-h)<2)<3and c not in H+T],H;time.sleep(.1)

You input the board as three list of complex numbers representing the coordinates of the cells of copper (which must include the heads and tails lists), heads, and tails.  Here's an example:
[3+2j+x for x in range(8)] + [3+4j+x for x in range(8)] + [11+3j+x for x in range(6)] + [2+3j]
[3+2j]
[2+3j]

Note that we eval the input, so you can use arbitrarily complex expressions for lists of complex numbers.

QBasic, 309 bytes
Warning: the golfed version is not user-friendly: it has a weird input method, runs as an infinite loop, and doesn't have any delay (thus, runs too fast on some systems). Only run it if you know how to terminate a program in your QBasic environment. The ungolfed version is recommended (see below).
INPUT w,h
SCREEN 9
FOR y=1TO h
FOR x=1TO w
PSET(x,y),VAL(INPUT$(1))
NEXT
NEXT
DO
FOR y=1TO h
FOR x=1TO w
SCREEN,,0
c=POINT(x,y)
d=c
IF c=7THEN d=1
IF c=1THEN d=6
IF c=6THEN
n=0
FOR v=y-1TO y+1
FOR u=x-1TO x+1
n=n-(POINT(u,v)=7)
NEXT
NEXT
d=7+(n=0OR n>2)
END IF
SCREEN,,1,0
PSET(x,y),d
NEXT
NEXT
PCOPY 1,0
LOOP

To run, specify at the input prompt your configuration's width w and height h.1 Then type w*h single-digit codes for the cells (moving left to right, then top to bottom), with

0 = empty
6 = wire
7 = signal head
1 = signal tail

Once you have entered all of the cells, the simulation will begin (and continue forever, until you kill the program).
Ungolfed
A more user-friendly version. To modify the layout, modify the DATA statements at the end.
The code takes advantage of the POINT function, which reads the color value of a pixel from the screen. This means we don't have to store the cells separately as an array. To make sure that all cells update simultaneously, we perform the updates on a second "page." We can toggle the active page using a version of the SCREEN statement, and copy one page's contents to another using the PCOPY statement.
SCREEN 9

EMPTY = 0 ' Black
HEAD = 7  ' Light gray
TAIL = 1  ' Blue
WIRE = 6  ' Brown/orange

' First two data values are the width and height
READ w, h
' The rest are the initial configuration, row by row
' Read them and plot the appropriately colored pixels
FOR y = 1 TO h
  FOR x = 1 TO w
    READ state$
    IF state$ = "" THEN value = EMPTY
    IF state$ = "H" THEN value = HEAD
    IF state$ = "T" THEN value = TAIL
    IF state$ = "W" THEN value = WIRE
    PSET (x, y), value
  NEXT x
NEXT y

' Loop the simulation until user presses a key
DO UNTIL INKEY$ <> ""
  ' Store current time for delay purposes
  t# = TIMER

  FOR y = 1 TO h
    FOR x = 1 TO w
      ' Active page = display page = 0
      SCREEN , , 0
      ' Get the color value of the pixel at x,y
      oldVal = POINT(x, y)
      IF oldVal = EMPTY THEN
        newVal = EMPTY
      ELSEIF oldVal = HEAD THEN
        newVal = TAIL
      ELSEIF oldVal = TAIL THEN
        newVal = WIRE
      ELSEIF oldVal = WIRE THEN
        neighbors = 0
        FOR ny = y - 1 TO y + 1
          FOR nx = x - 1 TO x + 1
            IF POINT(nx, ny) = HEAD THEN neighbors = neighbors + 1
          NEXT nx
        NEXT ny
        IF neighbors = 1 OR neighbors = 2 THEN
          newVal = HEAD
        ELSE
          newVal = WIRE
        END IF
      END IF
      ' Active page = 1, display page = 0
      SCREEN , , 1, 0
      ' Plot the new value on page 1
      PSET (x, y), newVal
    NEXT x
  NEXT y

  ' Copy page 1 to page 0
  PCOPY 1, 0

  ' Delay
  WHILE TIMER >= t# AND t# + 0.2 > TIMER
  WEND
LOOP

DATA 8,5
DATA T,H,W,W,W,W,W,W
DATA W, , , ,W, , ,
DATA  , , ,W,W,W, ,
DATA W, , , ,W, , ,
DATA H,T,W,W, ,W,W,W

1 The maximum values for width and height depend on which screen mode is used. In SCREEN 9, width can be up to 638 and height up to 348. SCREEN 7 has a smaller resolution (max configuration size 318 by 198), but the pixels are bigger and thus easier to see (on DOS QBasic or the DOSBox emulator--unfortunately QB64 just gives a smaller window).
Example run
Ungolfed version on archive.org, with screen mode 7:

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Implementing bool() without any conditionals
Title says it all. Given some input, turn it into a boolean value (0 or 1), without using conditional statements (e.x. == > < <= >= != ~=), or any function which uses conditional statements within its implementation, such as if, while and for. Your program must work with floating points, although you get more if it works with other items.
A general rule for determining whether bool(item) is False is if the item is empty ('' is an empty string, [] is an empty list.), or if the function used to turn an item of one type into another is given no input (in Python, str() returns '', list() returns [].)
Here are (some of) the different valid types. Your program is considered to work with one type if it works with one item in the following lists:

Integers, floating points, doubles, longs
Strings
Lists, tuples, arrays (bytearrays)
Dictionaries
Functions
Objects/Classes

Program score will be calculated like this: [# of characters]-(50*[# of types]). The program with the smallest score wins the challenge.

This problem is deceptively difficult. Perhaps a more concise wording would be to disallow any language construct which passively performs a boolean conversion (as &&, ||, while, for(;foo;), etc. all do).

Would you give an example of valid input that does not use comparison operators (such as == > < <- >= !=)? I must be missing something. It seems to me that they are essential elements of the sorts of propositions one wishes to assess.

How do you measure how many types you handle?  Do types such as float/double count as a single floating-point type or two separate types?

@MrZander: I would consider a double as a float, since everything that works with doubles will work with floats too.

How can this possibly be language-agnostic? The problem definition makes various assumptions that seem to tie it to Python and close relatives, and the scoring system lets some languages claim a score of -Infinity.

@PeterTaylor as I understand it, there are only 7 different 'types' possible, ergo a maximum (or rather, minimum) of -350 bonus. Although, I do agree that Set/Frozenset only applies to very few languages, and probably shouldn't be included.

@primo: I have removed sets. I have only used Python for programming, so I have no knowledge of other programming languages :P

I suppose PHPs settype is disallowed? :)

@Leigh: Haha, yes it is disallowed.

Python - 122 chars - 50*13 types = -528
def b(x=False):
 try:return[False][x]
 except IndexError:return True
 except:
  try:return b(len(x))
  except:return True

Works for the following built-in types (as listed in §3.2 The standard type hierarchy)

NotImplemented
Ellipsis
int
long
bool
string
unicode
tuple
list
bytearray
set
frozenset
dict

Using exceptions to emulate conditionals... seems to simple, in retrospect ;)

What you have there seems to be 121 characters, not 122 :) Also, you can save one more character by passing instead of returning True and then doing that at the end.

JavaScript, -278
function bool(_,$){try{$=_.length;$._;_=$}catch(_){}return 1-isNaN(_/_)}

Doesn’t use any boolean operators! If global leaking and input is okay, then it’s even shorter, at 65 characters:
bool=eval.bind(0,'try{$=_.length;$._;_=$}catch(_){}1-isNaN(_/_)')

Works for anything with a length and all primitive types and their object wrappers.
Now you've added a list of things that count as types, but what kind of function or class should evaluate to false? This one treats functions that take no arguments as false - does that count? What about classes? What does that mean?

You have numbers, strings, arrays and dictionaries, functions, and object; giving you the best bonus: -350.  So, your score is -278.

@FakeRainBrigand: Ah, the question was updated. Thanks. But it doesn't work with functions. (Well, it does, but what's an "empty" function anyways? This one will detect a function that takes no arguments.)

MMIX (8 bytes assembled)
Assembly language has no statements.
bool    ZSNZ $0,$0,1
        POP  1,0

Scala(152 characters)
implicit def?(a:Any)={val f=false;a match{case 0=>f;case null=>f;case ""=>f;case ()=>f;case None=>f;case x:Iterable[_]=>x.exists(_=>true)case _=>true}}

Sample inputs:
scala> if(0) true else false
res0: Boolean = false

scala> if(0.0) true else false
res1: Boolean = false

scala> if(1) true else false
res2: Boolean = true

scala> if(()) true else false
res3: Boolean = false

scala> if(List()) true else false
res4: Boolean = false

scala> if(List(1)) true else false
res5: Boolean = true

scala> if(Set()) true else false
res6: Boolean = false

scala> if("") true else false
res7: Boolean = false

scala> if(Map()) true else false
res8: Boolean = false

scala> if(None) true else false
res9: Boolean = false

scala> class X
defined class X

scala> if(new X()) true else false
res10: Boolean = true

GoRuby, 19 - 50*(number of types in Ruby)
def bool(o)
   [1,[o].fle.j.sz].mi
end

Returns 0 if the passed object converts to the empty string, 1 otherwise.  Of course, Ruby doesn't treat 0 as false, so this isn't a very useful function...in fact, bool(bool(x)) is always 1.  Objects that do convert to 0 include nil,false,[], and lists containing only objects that convert to 0.

Python 85 chars - 50*20 types = -915 points
def b(x=False):
 try:return b(len(x))
 except:return{0:False,None:False}.get(x,True)

So it works for all types in the six categories in the question.
The score is therefore 85 - 50*6 = -215, or am I wrong?
Here is also my test code:
class Test(object):
  def __init__(self):
    pass

for x in [None, NotImplemented, Ellipsis,
    0,1,0L,1L,False,True,0.0,1.0,0.0j,1.0j,
    '','a',u'',u'a',
    (),(1,),[],[1],bytearray(),bytearray('31'),
    set(),set('ab'),frozenset(),frozenset('ab'),
    {},{'a':0},b, Test, Test.__init__,(a for a in 'a')]:
  print b(x), bool(x), type(x)

Think I've forgotten some types ;-)
b(x) bool(x) type(x)
False False <type 'NoneType'>
True True <type 'NotImplementedType'>
True True <type 'ellipsis'>
False False <type 'int'>
True True <type 'int'>
False False <type 'long'>
True True <type 'long'>
False False <type 'bool'>
True True <type 'bool'>
False False <type 'float'>
True True <type 'float'>
False False <type 'complex'>
True True <type 'complex'>
False False <type 'str'>
True True <type 'str'>
False False <type 'unicode'>
True True <type 'unicode'>
False False <type 'tuple'>
True True <type 'tuple'>
False False <type 'list'>
True True <type 'list'>
False False <type 'bytearray'>
True True <type 'bytearray'>
False False <type 'set'>
True True <type 'set'>
False False <type 'frozenset'>
True True <type 'frozenset'>
False False <type 'dict'>
True True <type 'dict'>
True True <type 'function'>
True True <type 'type'>
True True <type 'instancemethod'>
True True <type 'generator'>

Bash
Bash only does integer arithmetic of numbers stored in strings.  So this isn't really a proper answer as there are no floats.  But I thought this was an interesting integer-only solution:

$ bool () { echo $(( (($1 * $1) + 2) % (($1 * $1) + 1) )); }
$ for i in {-5..5}; do bool $i; done
1
1
1
1
1
0
1
1
1
1
1
$

Perl, 5 char
1-!$x

Works for integers, floating-point values, strings, and C. Although in Perl, these are all the same type.

! is a boolean operation

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Interpret whatfuck
Smallfuck is a brainfuck-like language with 1-bit cells.  It has the following instructions:
> Increment the pointer
< Decrement the pointer
* Flip the current bit
[ If the current bit is not set, jump to the instruction after the matching ]
] If the current bit is set, jump to the instruction after the matching [
    ( or just jump unconditionally to matching [ )

Whatfuck adds one more instruction:
? Nondeterministically set the current bit to 0 or 1.

A whatfuck program does not take any input.  It can result in one of 3 possibilities: 1 (accept), 0 (reject) or it may never halt.
The program will result in 1 if there exists a sequence of bits chosen for ?s which results in the program terminating with 1 as the current bit.
The program terminates with 0 if all possible choices terminate with current bit 0,
If some choices don't terminate, and all choices which terminate do so with 0, then the program will never terminate.
Your interpreter should run all possibilities simultaneously.  You can't try 0 first and then try 1, because some programs will not terminate when they should.  For example, *[?*]* will accept with the choice 1, but never terminate if you always choose 0.
As an example, here is a python 2 interpreter I wrote, not golfed
Rules

Your interpreter must accept a whatfuck program from stdin and print its result.
You may assume the whatfuck program only contains characters []<>*?
The array of bits is unbounded on both ends.
Shortest code wins.

Some Test Cases
This will fail if your code always tries 0 first
*[?*]*
1

Is there a subset of {-7,-3, 5, 8} whose sum is 3?
*<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
1

Is there a subset of {-7,-3, 5, 8} whose sum is 4?
*<<<<<<<?[<<<<<<<<<<<<<<]?[<<<<<<]?[>>>>>>>>>>]?[>>>>>>>>>>>>>>>>]<
0

Is there a way to assign boolean values to a,b and c such that
(a XOR b) AND (a XOR c) AND (b XOR c) is true?
?[*>*>*<<]?[*>*>>*<<<]?[*>>*>*<<<]>[*>[*>[*>*<]<]<]>>>
0

Python, 305 chars
P=raw_input()+'$'
S=[(0,0,[])]
F={}
R={}
i=r=0
for c in P:
 if'['==c:S+=i,
 if']'==c:j=S.pop();F[j]=R[i]=i-j
 i+=1
while S*(1-r):p,t,B=S.pop(0);c=P[p];b=B.count(t)%2;p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b;t+=(c=='>')-(c=='<');B=B+[t]*(c=='*');r|=(c=='$')&b;S+=[(p,t,B)]*(c!='$')+[(p,t,B+[t])]*(c=='?')
print r

Keeps track of the nondeterministic set of states in S, each with a code position p,  a tape position t, and a list of tape indexes B.  A tape index can appear multiple times in the list B, the tape at that index is 1 if the index appears an odd number of times in B.

Save 1 byte by replacing t+=(c=='>')-(c=='<'); with t+=c=='>';t-=c=='<';, another by replacing B=B+[t]*(c=='*') with B+=[t]*(c=='*'), and a third by replacing p+=1+F.get(p,0)*(1-b)-R.get(p,0)*b; with p+=1+F.get(p,0)*-~-b-R.get(p,0)*b;. Great answer! (Sorry, I know this answer's super old!)

Infinite tape ahoy!
Haskell, 516
i((p:l,r),(π,'<':φ))=[((l,p:r),('<':π,φ))]
i((l,p:r),(π,'>':φ))=[((p:l,r),('>':π,φ))]
i((l,p:r),(π,'*':φ))=[((l,1-p:r),('*':π,φ))]
i((l,_:r),(π,'?':φ))=[((l,b:r),('?':π,φ))|b<-[0,1]]
i(s@(l,0:r),(π,'[':φ))=[(s,m(']':π,φ)0)]
i(s,(π,'[':φ))=[(s,(']':π,φ))]
i(s,(π,']':φ))=[(s,ξ$m(']':φ,π)0)]
i _=[]
m(l,']':r)0=('[':l,r)
m(l,']':r)n=m('[':l,r)$n-1
m(l,'[':r)n=m(']':l,r)$n+1
m(l,c:r)n=m(c:l,r)n
ν=null;ο=0:ο
μ[]="0"
μ ω|ν[ψ|ψ@((_,b:_),_)<-ω,b>0,ν$i ψ]=μ$ω>>=i
μ _="1"
ξ(a,b)=(b,a)
main=interact$ \ζ->μ[((ο,ο),("",ζ))]

It's remarkable how often Haskell answers succeed in getting top votes even if there are other answers with objectively better score around...

μ              :)            ..............

Python (405 399 379)
It takes the input on one line, but I "may assume the whatfuck program only contains characters []<>*?" and newline isn't on that list :P

w,i,p,a={},0,raw_input(),[(0,0,[],[])]
for c in p:
 if c=='[':a+=i,
 if c==']':g=a.pop();w[i],w[g]=g,i
 i+=1
i,z=0,lambda l:l and l.pop()or 0
while a:
 n,c,l,r=a.pop(0)
 try:o=p[n]
 except:
        if c:i=1;break
        continue
 if o=='*':c=not c
 if o=='>':l+=c,;c=z(r)
 if o=='<':r+=c,;c=z(l)
 if o in'[]'and(']'==o)==c:n=w[n]
 if o=='?':a+=(n+1,not c,l[:],r[:]),
 a+=(n+1,c,l,r),
print i

.append(item) -> +=[item], remove k and replace all calls with a+=[...] to save a few characters.

@beary605: thanks, however I ended up using +=item, which is even shorter.


text:
print 1 to 100 without using recursion and conditions
can we print 1 to 100 without using any if conditions and loops in c&c++?
Conditon:
main point is you must not use recursion...and doesnt hardcode code in it
for e.g
print(1 2 3..etc);

print "1 to 100" or print 1 2 3 4 5 6 (etc)?

@beary605 print 1 2 3..100

Does goto count?

Do preprocessor conditions count?

C (90) (79) (59) (47) (42) (40)
static int
x=1;a(){char b[8];printf("%d\n",x++);b[24]-=5*(1-x/101);}main(){a();return 0;}

The function a which prints the numbers does not call itself! I exploited a buffer overflow and changed the return address to make the program counter go over function a again as long as I need.
I don't know if this is considered to be a recursion, but I thought it would worth trying.
This code works on my 64-bit machines with gcc 4.6, for other platforms the last statement of function a, could be a little different.
Exp1: I allocated a dummy buffer on stack b, and then addressed a passed-by-end location, which is the location of return address. I anticipated the distance between start of buffer and return address location from disassembly of function a.
Exp2: Expression 5*(1-x/101), is 5 for all x<=100 and 0 for x=101. By looking at disassembly of main (in my case), if you decrease the return address by 5, you will set the PC to calling point of a again. In the updated codes, the return value of printf is used for checking loop condition.
Update: After applying ugoren's suggestions and some other changes:
x;a(){int b[2];b[3*(printf("%d\n",++x)&2)]-=5;}main(){a();}

Update2: After Removing function a:
x;main(){int b[2];b[6^printf("%d ",++x)&4]-=7;}

Update3:
x;main(b){(&b)[1|printf("%d ",++x)&2]-=7;}

Update4: Thanks to mbz :)
x;main(b){(&b)[3|printf("%d ",++x)]-=7;}

Perhaps the most interesting answer here! Could you explain a bit about how it's supposed to work? How did you come with b[24] for the location of the PC and how can I determine what I should use instead (32-bit cygwin, gcc 4.7.3)? What is the rationale behind the magical expression 5*(1-x/101)?
Also, is the static part of x's declaration needed? I'm not fully clear on how this works but since we aren't explicitly returning from a() wouldn't even an auto variable x remain in memory? And in this case it's even a global already.
Thanks again for enlivening this dull repetitive thread.

@sundar Thank you for pointing out static. You're right, It was necessary for my previous code and I forgot to remove it. I added some small explanations, please check them out in answer :)

int b[2] would be shorter. 2. return 0; isn't needed. 3. Changing the index on b instead of the subtracted value would be shorter. (of course, every such change could change machine code and break the solution, but I think it should be OK).

Another idea - maybe exploit the fact that printf returns a higher value at 100?

@saeedn Thanks for the explanations, it's very clear now. I felt stupid after reading Exp2 though, I'd been trying to decode it as some overcomplicated int-to-float bit pattern thing like the famous "inverse square root" formula, missed this much simpler explanation. :)

@ugoren Thanks for suggestions. I tried them. The printf return value idea was nice :)

6^printf()&4 saves 2 chars. At 100, it changes b[2], which is a harmless overflow on my machine. P.S. Why don't you change the character count in the title?

The net step is to get rid of a. main can do the work alone.

@ugoren I worked on main and updated the answer ;)

Nice. I used -=4, not -=7, but I guess both work. I was going to say it's done, but I saw your \n->  change, and decided not to give up. How about making b a parameter (and using &b[...])?

@ugoren Yeah, that was good point. Unfortunately the parentheses around &b were necessary. I think it can't be shorter than this, can it?

It can be shorter. Try %2d. I couldn't get rid of the parenthesis. I tried the x[y]->y[x] trick, but it stays the same length (but even weirder than now).

@ugoren is there documentation somewhere for why that x[y] -> y[x] trick works? I remember that it works, but I don't remember why, and I can't find what to search for. (I know that it's equivalent to something which is the same as something else, which is the same as y[x], but idr what those 2 middle ones are.)

@mbomb007, both are equivalent to x[y] = *(x+y) = *(y+x) = y[x].

85
C (gcc)
#define c printf("%d ",i++);
#define b c c c c c
#define a b b b b b
main(i){a a a a}

Assuming no command line arguments were passed.

Using the preprocessor is almost like hard coding it.

agreed. This is hardwired.

C++ (159 136)
With templates.
#include<cstdio>
#define Z(A,B,C,D)template<A>struct P B{P(){C;printf("%d ",D);}};
Z(int N,,P<N-1>(),N)Z(,<1>,0,1)int main(){P<100>();}

s/class/struct/;s/public://;s/static //;s/::/()./g saves 11 characters.

C 71 70
Assuming the ? operator is allowed.
#define f(a)a a a a a
int main(i){f(f(f(printf(i<102?"%d ":0,i++);)))}

Edit: ""->0
If ? is too similar to an if statement, then use this instead (78)
#define f(a)a a a a
#define g(a)f(a)a
int main(i){f(g(g(printf("%d ",i++);)))}

? is a conditional is it not?

vignesh4303 disallowed "if conditions", not all conditionals, which is why I included both answers.

267
this is the best I can think of, assuming using the preprocessor is fine.
#include <stdio.h>
#define a(i)i,i+1,i+2,i+3
#define b(i)a(i),a(i+4),a(i+8),a(i+12)
#define c(i)b(i),b(i+16)
#define e c(1),c(33)
#define f %d %d %d %d
#define g f f f f f f f f
#define r(m) #m
#define s(m) r(m)
int main(){printf(s(g g g f),e,c(65),a(97));return 0;}

C++ (115)
#include <cstdio>
template<int i>void p(){printf("%d ",i);p<i+1>();}
template<>void p<101>(){}
int main(){p<1>();}

Isn't this recursion?

MATLAB/Octave, (5 chars)
1:100

Doesn't the question want a code in C?

PowerShell (6 characters)
1..100

Equally doable, though no shorter, with 1..1e2.

Python 3 (25)
print(list(range(1,101)))

it is a inbuilt function that uses recursion!

I guess it depends on the interpreter if range uses recursion. I don't use recursion in my solution. I don't care if the inbuilt functions use recursion. If you want to take a look at every possible interpreter / compiler, you can't answer this question with anything else than assembly.

The garbage collector uses recursion!  So does the kernel of your OS.  So, computers are not allowed.

Python 2 (12)
>>> range(1,101)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

Ruby (11)  [non-competitive]
p *(1..100)

(Thanks to histocrat)
Previous 14-character solution:
p *1.upto(100)

This is a non-competitive answer (not C/C++ as requested)

p *(1..100) saves 3 characters.

@histocrat Thanks, I updated my answer.

Can't you remove the brackets too?

Scala (22)
1 to 100 foreach print

@downvoter care to comment ?

Perl 6 (10)
print ^101

If one wants to be able to read the numbers and therefore spaces between the numbers would be nice, the following will do the trick.
say ~ ^101

Perl (65)
Here's a non-trivial Perl approach (not like say for 1 .. 100). The program uses perl's regular expression engine to count its own characters (two times), and that's the reason why I couldn't golfify the content of $k. It tries to find a (minimal, non-greedy) group of arbitrary single characters until (*FAIL).
$k='$k =~ /^(.+?)(?{print length($1) . "\n"})(*FAIL)/#'x2;eval$k;

The output is a list of all integers from 0 to 100 with newlines.

Clever solution on many levels, nice. I don't understand the *FAIL though, is it some special string to the regex engine? If not, won't the * have its usual metacharacter meaning here and mess things up?

@sundar see the "Special Backtracking Control Verbs" section in perlre :)

Pygmy, (18 characters)
alert|[1 100].fill

Python 2 (39 chars)
p=lambda d:print d+1,;map(p,range(100))

Python 3 (53 chars)
p=lambda d:print(d+1,end=' ');set(map(p,range(100)))

or print numbers on separate lines (28 char)
set(map(print,range(1,101)))

or (tested in Python 3.3.2, set items printing in ascending order - 24 chars)
print(set(range(1,101)))

Bash 13
echo {1..100}

Some more text so it posts.

JavaScript (ES6), 38 bytes
alert([...Array(101).keys()].slice(1))

Creates an array of length 101, uses the spread operator to put the array keys (0 to 100) into an array, removes the first element (0) then alerts the numbers within the array.

Python - 61
Looping? No this is list comprehension.
d=[0,1,2,3,4,5,6,7,8,9];print[x*10+y+1 for x in d for y in d]

That's stretching the "no hardcoding" pretty hard.

Hassium, 31 Bytes
func main()print(range(1, 100))

Run online and see expanded here

JAVA, 52 chars
IntStream.range(1,101).forEach(System.out::println);

Welcome to the site. I am not familiar with java but forEach looks an awful lot like a loop which seems to be forbidden by the challenge.

It's a stream function.  It performs an operation on each element of the stream.  It's not a loop.

I would disagree that a stream function is distinct from a loop but I don't think this argument is worthwhile.  This question has been closed as unclear for the very reason that "loop" is not very well defined.

This challenge restricts to C/C++, so Java is probably unacceptable here.


text:
Test if given number is a Keith number
Since Fibonacci numbers and sequences seems like a popular subject for code golf I thought that it might be a fun challenge to code golf with Keith numbers.
So I propose a challenge that is to create a function that takes an integer and gives back a true or false depending on the number is a Keith number or not.
More about Keith numbers

In recreational mathematics, a Keith number or repfigit number (short for repetitive Fibonacci-like digit) is a number in the following integer sequence:
  14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, …

Numberphile has a video explaining how to calculate a Keith number. But basically you take the digits of a number. Add them together and then take the last digits of the original number and add them to the sum of the calculation, rinse and repeat. And example to make it clear.

141 + 4 = 5
  4 + 5 = 9
  5 + 9 = 14

Input
An integer.
Output
True if the number is a Keith number. False if it's not..

Strictly speaking, "an integer" can include zero or negative numbers. I'm pretty sure neither can be a Keith Number. Do we need to account for this?

Depending on your solution single digit numbers could show up as true. So you should check for potential errors in input.

Does it have to output true / false or can it be anything truthy/falsey?

GolfScript (31 25 chars)
..[10base{.{+}*+(\}@*]?0>

Input as an integer on top of the stack. Output is 0 (false) or 1 (true). Online demo which lists the Keith numbers up to 100.

Nice idea with the 0>. Unfortunately I can +1 only once.

Python (78 75)
a=input()
n=map(int,`a`)
while a>n[0]:n=n[1:]+[sum(n)]
print(a==n[0])&(a>9)

n=n[1:]+[sum(n)] does all the magic. It takes every item but the first item of n, sticks on the sum of n (with the first item), then sets that to n.
I wish you could call list on an integer and have the digits seperated.
Returns False on all inputs below 10. Can be 8 characters shorter if it returned True.

You may save two chars if you compare with n[0] instead of n[-1].

Save five more with print 9<a==n[0].

n=n[1:]+[sum(n)] can become n=n[1:]+sum(n),

GolfScript, 32 29 characters
...[10base\{.{+}*+(\}*]&,\9>&

A GolfScript implementation which can be tested online. Input is given as top element on the stack and it returns 0 (i.e. false) or 1 respectively.

@PeterTaylor Look at the link provided where I did exactly that - and it works...

@PeterTaylor Looking at your solution I even could reduce the number of chars further in my approach.

I must have not refreshed, because my comment is applicable to version 1.

APL, 36 34 39 36 33 29 27
*+/x={(∇⍣(⊃x>¯1↑⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

Output 1 if Keith, 0 otherwise
GolfScript strikes again!!

Edit
+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

Using Right-reduction (⊢/) instead of Take minus 1 (¯1↑), directly saving 1 char and indirectly saves 1 from Disclose (⊃)
Explanation
⍎¨⍕x←⎕ takes evaluated input (treated as a number) and assign it to x. Converts it to a character array (aka "string" in other languages), and loop through each character (digit), converting it to a number. So this results in a numerical array of the digits.
{(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x} is the main "loop" function:
+/⍵↑⍨-⍴⍕x takes the last ⍴⍕x (no. of digits in x) numbers from the array and sums them.
⍵, concatenates it to the end of the array.
(x>⊢/⍵) check if the last number on the array (which doesn't have +/⍵↑⍨-⍴⍕x concatenated yet) is smaller than x and returns 1 or 0
∇⍣ executes this function on the new array that many times. So if the last number is smaller than x, this function recurs. Otherwise just return the new array
After the executing the function, the array contains the sums up to the point where 2 of the numbers are greater than or equal to x (e.g. 14 will generate 1 4 5 9 14 23, 13 will generate 1 3 4 7 11 18 29)
Finally check if each number is equal to x and output the sum of the resulting binary array.

Edit
1=+/x={(∇⍣(x>⊢/⍵))⍵,+/⍵↑⍨-⍴⍕x}⍎¨⍕x←⎕

Added 2 chars :-( to make output 0 if the input is one-digit

Yet another edit
+/x=¯1↓{(∇⍣(x>⊢/⍵))1↓⍵,+/⍵}⍎¨⍕x←⎕

Explanation
The function now drops the first number (1↓) from the array instead of taking the last ⍴⍕x (↑⍨-⍴⍕x).
However, this approach makes 1= not adequate to handle single digit numbers. So it now drops the last number from the array before checking equality to x, adding 1 char

You guessed it: EDIT
+/x=1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

Compares x to the newly-added item instead of the old last item, so dropping the first (instead of last) item before checking equality to x is suffice, saving a minus sign.
Saves another 3 by using another form of the Power operator(⍣)
And a 25-char gs answer appears (Orz)

Last edit
x∊1↓{1↓⍵,+/⍵}⍣{x≤+/⍵}⍎¨⍕x←⎕

Can't believe I missed that.
Can't golf it anymore.

You can get this down to 24 characters: x∊{1↓⍵,+/⍵}⍣{x≤⊃⍺}⍎¨⍕x←⎕. In the power function, ⍺ is the "after" value.

Common Lisp, 134
CL can be quite unreadable at times.
(defun k(n)(do((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))((>=(car a)n)(and(> n 9)(=(car a)n)))))

Some formatting to avoid horizontal scrolling:
(defun k(n)
  (do
    ((a(map'list #'digit-char-p(prin1-to-string n))(cdr(nconc a(list(apply'+ a))))))
    ((>=(car a)n)(and(> n 9)(=(car a)n)))))

Test:
(loop for i from 10 to 1000
      if (k i)
      collect i)

=> (14 19 28 47 61 75 197 742)

F# - 184 chars
I hope it's ok that I'll participate in my own challenge.
let K n=
let rec l x=if n<10 then false else match Seq.sum x with|v when v=n->true|v when v<n->l(Seq.append(Seq.skip 1 x)[Seq.sum x])|_->false
string n|>Seq.map(fun c->int c-48)|>l

Edit Fixed a bug regarding small numbers.

It's perfectly fine :)

Your solution returns true for n<10 which I think should be false.

You are right. I should look into that.

PowerShell: 120 128 123 111 110 97
$j=($i=read-host)-split''|?{$_};While($x-lt$i){$x=0;$j|%{$x+=$_};$null,$j=$j+$x}$x-eq$i-and$x-gt9

$i=read-host takes input from the user, stores it in $i.
$j=(...)-split''|?{$_} breaks up the digits from $i into an array and stores it in $j.

Thanks to Rynant for pointing out that -ne'' is unnecessary.

While($x-lt$i) sets the following Fibonnaci-like loop to run until the sum variable, $x, reaches or exceeds $i.
$x=0 zeroes out $x, so it's ready to be used for summing (necessary for when the loop comes back around).
$j|%{$x+=$_} uses a ForEach-Object loop to add up the values from $j into $x.
$null,$j=$j+$x shifts the values in $j left, discarding the first, while appending $x.

Yay! I finally figured out a shorter way to do shift-and-append, and got this script under 100!

$x-eq$i after the while loop completes, tests if the sum value, $x, equals the initial value, $i - generally indicative of a Keith Number.
-and$x-gt9 invalidates single-digit numbers, zero, and negative numbers, which cannot be Keith Numbers.
This script is a bit "messy". It can gracefully handle $i and $j being leftover, but you'll need to clear $x between runs.

Thanks to Keith Hill and mjolinor for some methods of breaking numbers into digits which were used in earlier versions of this script. While they are not in the final version, they did provide for a great learning experience.

You can remove the -ne'' so that it is just ?{$_}.

Thanks @Rynant. Looks like I can also trim it down one more by replacing $i=read-host;$j=$i-split''|?{$_}' with $j=($i=read-host)-split''|?{$_}.

K, 55
{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}

.
k)&{(x>9)&x=*|a:{(1_x),+/x}/[{~(x~*|y)|(+/y)>x}x;"I"$'$x]}'!100000
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909 31331 34285 34348 55604 62662 86935 93993

Husk, 11 bytes
S£o¡oΣ↑_L¹d

Try it online!
Returns the iteration at which the Keith number is present, otherwise 0.
This challenge is perfect for Husk.
Explanation
S£o¡oΣ↑_L¹d
   ¡o       create an infinite list, starting with
          d the digits of the input
      ↑_L¹  take length(input) numbers from the end
     Σ      and sum to compute the next number
S£o         is the input present in the list?

Ruby, 82
def keith?(x)
  l="#{x}".chars.map &:to_i
  0while(l<<(s=l.inject :+)).shift&&s<x
  (s==x)&l[1]
end

Suspect Python's a better tool for this one.

C, 123
k(v){
    int g[9],i,n,s,t=v;
    for(n=s=0;t;t/=10)s+=g[n++]=t%10;
    for(i=n;s<v;){
        i=(i+n-1)%n;
        t=g[i];g[i]=s;s=s*2-t;
    }
    return n>1&&s==v;
}

test via harness:
main(i){
    for(i=0;i<20000;i++)
        if(k(i)) printf("%d ",i);
}

gives:
14 19 28 47 61 75 197 742 1104 1537 2208 2580 3684 4788 7385 7647 7909

You can replace i=(i+n-1)%n;t=g[i];g[i]=s;s=s*2-t; with i+=n-1;t=g[i%n];g[i%n]=s;s+=s-t; and save two chars.

R, 116
Python rip-off:
a=scan();n=as.numeric(strsplit(as.character(a),"")[[1]]);while(a>n[1])n=c(n[-1],sum(n));if((n[1]==a)&&(a>9))T else F

Perl, 90
sub k{$-=shift;$==@$=split//,$-;push@$,eval join'+',@$[-$=..-1]while@$[-1]<$-;grep/$-/,@$}

A fun exercise! I know it's an old post but I noticed perl was missing!
I'm sure I can improve the way I build this from digesting the other responses more thoroughly, so I'll likely revisit this!

Smalltalk - 136 char
 [:n|s:=n asString collect:[:c|c digitValue]as:OrderedCollection.w:=s size.[n>s last]whileTrue:[s add:(s last:w)sum].^(s last=n and:n>9)]

Send this block value:

Python3 104
#BEGIN_CODE
def k(z):
 c=str(z);a=list(map(int,c));b=sum(a)
 while b<z:a=a[1:]+[b];b=sum(a)
 return(b==z)&(len(c)>1)
#END_CODE score: 104

print([i for i in filter(k, range(1,101))])  #[14, 19, 28, 47, 61, 75]

And it is a function ;)

Python - 116 chars
Not really an expert at codegolf, so there you have it- my first try.
x=input();n=`x`;d=[int(i)for i in n];f=d[-1]
while f<x:d+=[sum(d[-len(n):])];f=d[-1]
if f==x>13:print 1
else:print 0

Make 2 changes for a function:

Change print to return
Assign x to be the parameter

P.S. I second @beary605- add a built-in to separate the digits/characters/whatever.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
"Sorry, young man, but it's Turtles all the way down!"
Execute a Lindenmayer System
A Lindenmayer System (or L-system) is related to Thue and Post systems, and is used in botanical modeling and fractal generation.
An L-system is described by string-rewriting where a symbol from the symbol-alphabet is mapped to a replacement sequence of symbols. A collection of these mappings constitutes the L-system proper.
The graphical output method as devised by Prusinkiewicz interprets the resulting sequence after the mappings have been applied to an initial sequence for a specified number of iterations, as Turtle-Drawing commands: forward, backward, left, right, that kind of stuff. This may require extra code to control the scale of the drawing as different iteration counts may produce drastically differently-sized images.
Your task is to execute an L-system in the fewest number of characters. Your program must be able to render both the Dragon Curve and the Branching Stems from the Wikipedia page by providing appropriate input (file, command-line, but external to the source, please).

This is code golf.
Edit: Here are some examples I've posted around town. answer to SO/rotate-to-north {Where I first discovered the L-system}, answer to SO/how-to-program-a-fractal, answer to SO/recursion-in-postscript, comp.lang.postscript discussion/recital, postscript l-system collection, codegolf.SE/draw-a-sierpinski-triangle {origin of the competition between myself and thomasW}.

BTW, anybody know the origin of the above quote? I've heard William James, and I've heard Faraday.

Wikipedia says the origin is in dispute, best guess is Bertrand Russel.

ITYM Bertrand Russell.

Are there any limits on the size of the alphabet, number of rules, number of rounds or possible (visualization) rules (draw a straight line, push/pop position/angle, turn how many degrees etc.) If we only need to draw those two then we would need pushing & popping, drawing straight lines and being able to turn 45 degrees in both directions, only two rules and an alphabet of size 4.

@shiona The hope is that it would draw more than these two. But if you can make simplifying assumptions that hold for these two, that's ok.

Wait a moment ... I think it may actually be Max Müller. I was reading a fax of his Theosophy not too long ago.

@shiona Did I answer your question?

@luserdroog yes

Mathematica 200 198 188 171 168
Spaces added for clarity:
f[i_, b_, h_, j_, r_, n_] :=
 (a = h; p = j; s = k = {}; t = Flatten;
  (Switch[#,
      6, s = {a, p, s},
      8, {a, p, s} = s,
      _C, k = {k, Line@{p, p += {Cos@a, Sin@a}}}];
     If[# < 9, a += I^# b ]) & /@ t@Nest[# /. r &, i, n];
  Graphics@t@k)

Where:

i : Initial state;
  b : rotation angle
  h : initial angle
  j : initial position
  r : production rules
  n : iterations

Production rules grammar:

2 = Turn Left (-);
  4 = Turn Right (+);
  6 = Push and Turn Left  ("[");
  8 = Pop  and Turn Right ("]");
  C[i] = Draw (Any number of symbols)
  Any other symbol = Do Nothing, just use it in producing next state (Any number of symbols)

The {2,4,6,8} sequence is there because I'm using I^n (I = imaginary unit) to make turns.
Examples:
f[{C[1], X}, Pi/2, 0, {0, 0}, {X -> {X, 4, Y, C[1]}, Y -> {C[1], X, 2, Y}}, 10]

f[{C@1}, Pi/2, 0, {0,0}, {C@1->{C@1, 2, C@1, 4, C@1, 4, C@1, 2, C@1}}, 6]

f[{C[1]}, Pi/4, Pi/2, {0, 0}, {C[2] -> {C[2], C[2]}, C[1] -> {C[2], 6, C[1], 8, C[1]}}, 10]

f[{C[1]}, Pi/3, 0, {0, 0}, {C@1 -> {C@2, 4, C@1, 4, C@2}, C@2 -> {C@1, 2, C@2, 2, C@1}}, 10]

f[{X},5/36 Pi, Pi/3, {0,0},{X->{C@1, 4, 6, 6, X, 8, 2, X, 8, 2, C@1, 6, 2, C@1, X, 8, 4, X},
                            C@1->{C@1, C@1}}, 6]

Just modify Graphics@k by Graphics@Flatten@kif you plan to use many iterations. Otherwise a Recursion Limit will bite you and your Mma session will abort.

My macro-expansion method had a similar issue with higher iterations. The strings just become enormous. But the solution there was not to flatten. :)

+1 very nice indeed ;) Could be a cool Demonstration. Do you submit those?

@VitaliyKaurov Nope, but feel free to use it if you think it's worth the effort

@belisarius http://demonstrations.wolfram.com/GraphicalLSystems

Python, 369 294
Not a winner but I'll post what I've tried anyway.
from turtle import*
I=open('l').read().split()
s,S,p=I[0],'',[]
for j in range(8):
    for i in s:S+=eval('{'+I[1]+'}')[i]
    s,S=S,''
for k in s:
    if k=='[':p+=[heading(),pos()];continue
    if k==']':pu();goto(p.pop());seth(p.pop());pd();continue
    try:{'f':fd,'F':fd,'+':rt,'-':lt}[k](5)
    except:pass

Not good at golfing Python...... Maybe someone else can do it.
Input
Input is from an external file named "l" (no extension), with the following format:
Line 1: Initial state (Axiom)
Line 2: Comma-separated rules
Symbols
f and F: Draw forward
+: Turn right 5 degrees
-: Turn left 5 degrees
[: Save position and heading
]: Pop position and heading
Other symbols are ignored by the drawing function.
Rules
A rule is in the format "predecessor":"successor(s)"
Note that the quotes are necessary, whether single or double.
predecessor must be a single character.
Also, there are no implicit constants: You must explicitly specify a no-change rule for those.
Examples
Branching stems
------------------f
'-':'-','+':'+','[':'[',']':']','F':'FF','f':'F[+++++++++f]---------f'

Output

Note that the source is modified to get this out put ONLY TO SCALE DOWN THE GRAPH TO THE VISIBLE AREA. The console is also used to hide the "turtle".
Dragon curve
fx
'-':'-','+':'+','[':'[',']':']','f':'f','x':'x++++++++++++++++++yf','y':'fx------------------y'

Output

Again, the console is used to hide the "turtle".
Sierpinski Triangle
f------------------------F------------------------F
'-':'-','+':'+','[':'[',']':']','f':'f------------------------F++++++++++++++++++++++++f++++++++++++++++++++++++F------------------------f','F':'FF'

Output

Generations reduced to 5 here.

You can get a decent saving (I make it 32 chars) by removing the functions f, r, l; adding a dummy parameter to o and c; and then changing the pseudo-switch to {'f':fd,'F':fd,'+':rt,'-':lt,'[':o,']':c}[k](5)

You can also inline g, and I think o and c are worth eliminating with inline if statements (cheaper than the global declaration)

@PeterTaylor good work. I had an intuition that some of those functions could be inlined, but didn't know enough Python to suggest it articulately.

@luserdroog, I don't know Python either: I just did trial and error to see what worked - i.e. some of the things I tried (e.g. using lambdas for o and c directly in the pseudo-switch) gave syntax errors, but others didn't.

Hints for further golfing: 1. Change input format: Require braces around the rules and seperate axiom from rules by a space (not a newline). 2. Read from stdin: s,R,*p=input().split(). 3. Generate the final value of s by exec('s="".join(map(eval(R).get,s));'*8). 4. Leave out continue.  5. Indent only 1 space. 6. Save the space after the if by switching the sides fo the test. 7. Put k:int in the dict (first entry) and then you don't need except: try:. (I get 215 characters.)

Javascript (179 bytes)
Not completely sure this qualifies, as the rules object does all of the actual drawing.
Demo (Dragon, animated):
-- Expanded: http://jsfiddle.net/SVkMR/9/show/light
-- With Code: http://jsfiddle.net/SVkMR/9/
Minified:
function L(c,r,n){o=(function g(d,s,o,i){for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):a;return o||s;})(n,r.r[r.s]);(function z(i){r[s=o[i]]&&r[s](c)||setTimeout(z,10,i+1)})(0)}

Readable(ish):
function L(c,r,n){
    o=(function g(d,s,o,i){
        for(o=i='';a=d&&s[i++];)o+=r.r[a]?g(d-1,r.r[a]):o+=a
        return o||s
    })(n,r.r[r.s]);

    (function p(i){
        r[s=o[i]]&&r[s](c)||setTimeout(p,10,i+1)
    })(0)
}

Input:
var sierspinski = {
    r:{'A':'B-A-B','B':'A+B+A'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/3)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/3)},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c)},
    s:'A',
    a:0,
    m:1
};

var koch = {
    r: {'F':'F+F-F-F+F'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'F',
    a:0,
    m:2
};
var dragon = {
    r: {'X':'X+YF','Y':'FX-Y'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/2)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/2)},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:0,
    m:5
};

var algae = {
    r: {'A':'B[A]A','B':'BB'},
    '[':function(c){c.save();c.rotate(Math.PI/4);},  // save/restore will push/pop current state of context.
    ']':function(c){c.restore();c.rotate(-Math.PI/4);},
    'A':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    'B':function(c){this['A'](c);},
    s:'A',
    a:-Math.PI/2,
    m:1
};

var tree = {
    r:{'X':'F-[[X]+X]+F[+FX]-X','F':'FF'},
    '+':function(c){c.rotate(-this.a);c.rotate(this.a+=Math.PI/180*25)},
    '-':function(c){c.rotate(-this.a);c.rotate(this.a-=Math.PI/180*25)},
    '[':function(c){c.save();},
    ']':function(c){c.restore();},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    s:'X',
    a:-Math.PI/180*25,
    m:5
};

Usage:
var ctx = document.getElementById('l').getContext('2d'); // grab context
ctx.translate(299.5,199.5); // start drawing from center, fractional pixels because the canvas draws lines centered on the x/y coord specified
L(ctx, dragon, 8); // pass in context, rules object, and recursion cap

Bonus: Golden Spiral http://jsfiddle.net/SVkMR/35/show/light/
var golden = {
    r:{'A':'FT[TT]A','T':'+F'},
    'F':function(c){c.beginPath();c.moveTo(0,0);c.translate(this.m,0);c.lineTo(0,0);c.stroke()},
    '[':function(c){c.save();},
    ']':function(c){
        c.restore();

        c.beginPath();
        c.arc(0,-this.m,this.m,Math.PI/2,Math.PI);
        c.stroke();

        this.m+=this.d;this.d=this.m-this.d
    },
    '+':function(c){c.rotate(-Math.PI/2);},
    s:'A',
    a:-Math.PI/2,
    m:1,
    d:0
};

I think the animation more than compensates for any liberties with the rules. Good job! +1

:) Fun stuff! .

Postscript 264 298 295 255
Here's my attempt to do it differently. Rather than the macro-expansion that I usually use, this one checks the size of the execution stack to bound the recursion. If the bound is exceeded, it stops recursively examining the procedure and tries to interpret turtle commands (and discards pop pop otherwise). An advantage of this method is that it does not require enormous amounts of memory. A disadvantage is the recursion control is rather clumsy, as the stack size grows by more than just 1 from one recursion level to the next.
Edit: +34 chars for branching.
Edit: -3 chars. Redesigned to use the operand stack for recursion control. This makes the basic system much simpler. But brackets need an independent stack, so I put the saved position in the dictionary stack, and almost paid back all the savings.
Also, redesigned to use strings and integers instead of arrays and names.
Edit: -40 chars. Added two procedures for calling system names by number (I can't seem to get raw binary tokens to work. But this idiom works for me.)
/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73
*}def[/T[48{}49{}43{A<88>$}45{A<6e88>$}70{R
0<85>$}91{<1e39>$[/.[<286827>$]cvx>><0d0d>$}93{.<9c6b1e39390d>$}>>/S{dup
B eq{T<0d3e>${<643f>$}<4939>$}{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>><0d6b>$
0 S<a7>$

Semi-commented binary.
/*{<920>dup 1 4 3 roll put cvx exec}def/${//* 73 *}def %73=forall
[/T[70{R 0<85>$}48{}49{} %<85>=rlineto
43{A<88>$}45{A<6e88>$} %<88>=rotate <6e>=neg
91{<1e39>$ %<1e>=currentdict <39>=end
    [/.[<286827>$]cvx>> %<28>=currentpoint <68>=matrix <27>=currentmatrix
        <0d0d>$} %<0d>=begin
93{.<9c6b1e39390d>$}>> %<9c>=setmatrix <6b>=moveto
/S{dup B eq{T<0d3e>${<643f>$}<4939>$} %<3e>=exch <64>=load <3f>=exec <49>=forall
{exch{<643e>$ 1 add S}73 *}85 * 1 sub}>>
<0d6b>$ 0 S<a7>$  % 85=ifelse <a7>=stroke

Un-"binary".
[/T[70{R 0 rlineto}48{}49{}43{A rotate}45{A neg rotate}91{currentdict
end[/.[currentpoint matrix currentmatrix]cvx>>begin begin}93{. setmatrix
moveto currentdict end end begin}>>/S{dup B eq{T begin exch{load exec}forall
end}{exch{load exch 1 add S}forall}ifelse 1 sub }>>begin moveto 0 S stroke

It requires the L-system to be defined in a dictionary on the dictstack, with the initial string and the starting position of the turtle on the operand stack (prepended to the source, eg. gs dragon.sys lsys.ps).
Dragon Curve.
%!
[                     %begin dictionary construction
    % productions are described by integer-key/string-value pairs
    48(0+1F) %0       %ascii code for '0' defined as the string "0+1F"
    49(F0-1) %1       %  "     "   "  '1'   "     "   "    "    "F0-1"
    43(+) %+          %  "     "   "  '+' defined as itself
    45(-) %-          %  "     "   "  '-'   "     "   "
    70(F) %F          %  "     "   "  'F'   "     "   "
    % parameters
    /A 90 %angle
    /R 2  %radius
    /B 10 %maximum recursion-level
>>begin  % L-system dictionary on top of dictstack
(F0)     % initial string on stack
300 400  % starting position on stack

Branching Stems.
[
    48(F[+0]-0) %0
    49(F0-1) %1
    43(+) %+
    45(-) %-
    70(FF) %F
    91([) %[
    93(]) %]
    /A 45 %angle
    /R 5  %radius
    /B 3 %recursion
>>begin
(++0)     % initial string
300 400  % starting position

Ungolfed and commented.
[                                 % begin dictionary construction
    /T[                           % /T is the Turtle dictionary containing
                                  % integer-key/procedure-value pairs
                                  % keyed to ascii values
        70{R 0 rlineto}        %F
        48{}                   %0
        49{}                   %1
        43{A rotate}           %+
        45{A neg rotate}       %-

          % For brackets, create a dictionary containing a single procedure '.' (dot)
          % which holds a saved matrix (orientation+size) and currentpoint.
          % Since this procedure is called while the Turtle dict is on top of the
          % dictstack, the temporary dictionary is placed just under the top.
        91{currentdict end[/.[currentpoint matrix currentmatrix]cvx>>begin begin} %[
          % Right bracket: reset position and orientation,
          % pop the dict just under the top.
        93{. setmatrix moveto currentdict end end begin}    %]
    >>
    /S{ % stack contains: string recursion-level
        dup B eq{ % hit recursion bound, interpret string as turtle commands
            T begin
                exch % level string
                %dup =
                {                      % iterate through string
                    load exec          % execute turtle command by integer code
                } forall % level       % string has been consumed
            end
            %(B)= pstack
        }{ % recurse
            %(A)= pstack
            exch % level string
            { % level char                   iterate through string
                load exch % string level   process production:load string by int code
                1 add S   % string level+1   increase level and call self
            } forall                       % string has been consumed
        }ifelse
        1 sub            % return level-1
        %(C)= pstack
    }
>>begin
moveto 0 S stroke

To run it, these 3 blocks can be saved as 3 files: dragon.ps, stems.ps, lsys.ps (any of the above program blocks will work identically). Then run with gs: gs dragon.ps lsys.ps or gs stems.ps lsys.ps. They can also be concatenated first, if desired: cat dragon.ps lsys.ps | gs - or cat stems.ps lsys.ps | gs -.

No stems picture. It doesn't get any more interesting at higher depths.

Mathematica 290
This bare-bones implementation focuses on the output rather than the processing.
It does not use production rules.  So it may not be a suitable response to the challenge.
Branching stems adapted from Theo Gray's demonstration.
Code
f@{a_, b_} := {{a, #}, {b, #}} &[a + (b - a)/2 + {{0, 1/2}, {-1/2, 0}}.(b - a)]; w = Flatten;
h[s_, g_] :=Graphics[If[s == 0,Line /@ Nest[w[f /@ #, 1] &, {{{0, 0}, {1, 0}}}, g],
 MapIndexed[Line@# &, NestList[w[Map[{{#[[2]], #[[2]] + m.(#[[2]] - #[[1]])}, {#[[2]],
 #[[2]] + ({{1, -1}, {-1,1}} m).(#[[2]] - #[[1]])}} &, #], 1] &, {{{0, -1}, {0, 0}}}, g]]]]

Usage
The first parameter determines whether the Dragon Curve or Branch Stems will be displayed. The second term refers to the generation.
h[0, 5]
h[1, 5]

More Examples
GraphicsGrid@Partition[Flatten[Table[h[j, k], {j, 0, 1}, {k, 10}]], 5]

Very pretty. But wouldn't it save some bytes to pass the rule in as an argument?

If this were a general solution, perhaps one could pass a rule rather than parameters. I would have to be more knowledgeable about Lindenmayer Systems than I presently am.

I don't read mathematica. I should go learn some. (add it to the stack :) But you can interpret that to mean "whatever constitutes the description of the image, as distinct from the engine that drives it" can be factored out. If you can then modify the data to control some feature of the image, independently from touching the engine proper; I'd consider that to be "functionally equivalent" to an L-system. [That should give you lots of loopholes to work with ;)]. +1 anyway 'cause it's so pretty.

Btw I really like your choice of angle on the branches.

Your Tree isn't following the Wikipedia's production rule. You can see that noting that the tree trunk should be "growing" at each step and yours isn't. Was it done on purpose?

Good observation. (I was going to say that they were bonsai trees, but then realized that even bonsai trunks thicken over time.) I skipped a thickness parameter, regarding it as unnecessary.

Isn't it curious that many usual languages in this site aren't participating in this question?

@belisarius Yes, I wonder why?

@dude I think it's because the graphics requirements aren't well suited for them

Yea. I don't think gs or apl has such high-level graphics

Finally figured out the l-system for your tree: A->F[+A][-A] where F is move, + is rotate left 30, - is rotate right 30, and [/] are push/pop