What is the simplest digital signature algorithm known? The hardest part about this question is explaining what I mean by simple. I'm measuring simplicity as, simply, the amount of lines of code it takes to implement that algorithm in a simple programming language - say, the untyped lambda calculus, Scheme, vanilla ES5 JavaScript. Of course, this is not possible to measure directly, but some things are just obvious. For example, any algorithm depending on any kind of algebra (multiplication, exponentiation, division, modulus, whatever) is not simple because implementing Bignum takes an obscene ton of lines itself!

For example, this wikipedia article claims the Schnorr signature is the simplest known scheme, polluting the Google results with such a blatantly wrong claim, because this proposal can clearly be implemented with much less code in absolutely any language without native big-integers.

That is why ECDSA, DSA, RSA aren't simple, they depend on way too many number-theoretic functions. I'm looking for a signature scheme that emerges from some kind of natural process, for example, L-systems, cellular automatas. Those are truly simple to implement in any kind of language, no dependencies!

So, what is the simplest digital signature algorithm known?
Let's first clear up one thing. We want a secure signature scheme. (And by secure, we mean a scheme that is widely accepted as being secure by experts in the field, that is, cryptologists.) That means we can restrict attention schemes from the cryptographic literature that have reasonable security arguments, which rules out most stuff based on cellular automata etc.

There are as you say many notions of simplicity.

If you want to measure lines of code, you could begin by noting that any reasonable signature scheme will almost certainly employ a hash function. Which means that signature schemes based on hash functions should be fairly compact, especially schemes like Lamport one-time signatures. If you want to move beyond one-time schemes, things become more complicated, but perhaps not too much as measured by lines of code.

However, many languages today provide built-in (or nearly built-in) bignum arithmetic, which means that a scheme like Schnorr suddenly becomes extremely easy to implement, once you have a hash function implementation.

An even simpler scheme (probably) is RSA-FDH, which is nearly trivial once you have a hash function implementation and bignum arithmetic.

Another interesting metric is understanding, either the mechanics of the system or its security. On both of those metrics, RSA-FDH scores extremely high. All you need to understand the mechanics of the system is basic number theory. The intuitive security argument is easy to understand. The security proof is also fairly easy to understand (once you understand the intuition behind security proofs and random oracles).

The mechanics of Schnorr signatures are somewhat more complicated, especially if you use elliptic curves. I hesitate to say anything at all about the intuitive security of Schnorr signatures (I find that the only intuition is that its security is non-obvious). The security proof is much more complicated than the RSA-FDH proof.

Some schemes based on bilinear pairings are deceptively easy to describe, but only if you hide most of the complexity involved.

The mechanics of hash-based signatures are often fairly involved and complicated, and the security proofs I have seen have been fairly complicated.

A third metric is how easy it is to make a secure implementation. This is equivalent to a huge can of worms, which among other things involves your entire tool chain. You may suddenly find that your actual cryptographic schemes matters much less than the language you write in. Historically, Schnorr-like schemes have proven very difficult to implement, while something like RSA-FDH should be much easier. (However, I am not an implementation expert, so don't trust me here.)