Hacker News new | ask | show | jobs
by kragen 972 days ago
incidentally, this slight variant l-system, which is probably what you meant

  a where
  a -> afffb-f-fb+f+a
  b -> b+f+af-f-afffb
has the property that the axiom is a proper prefix of the axiom's expansion, which turns out to be equivalent to the property that every generation is a proper prefix of the following generation; this means that in a sense each one is "approaching a limit" of a single infinite string, in the sense that it's a successively longer prefix of that string. this infinite string, called a 'morphic word', is a fixed point of the mapping the l-system does each generation

this is literally a numerical approximation if you treat the string as a fractional number in some base, e.g., base 10 with a=1, b=2, f=3, +=4, -=5

with that interpretation, the first approximation 'a' is 0.1, the second approximation 'afffb-f-fb+f+a' is 0.13332535324341, the third approximation 'afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a' is 0.133325353243413332434135351333253532434135351333243413332535324341, and so on.

the thue-morse sequence can be generated in the same way with the l-system

    0 where 0 -> 01 and 1 -> 10
although the so-called fibonacci word is slightly simpler

    a where a -> ab and b -> a
all of the above morphic words are aperiodic, though it's trivial to design a periodic morphic word

a program to output the infinite morphic word of movement commands for the h-curve of a single triangle is

    queue = ['a'], []
    d = dict(a='afffb-f-fb+f+a', b='b+f+af-f-afffb')
    while True:
        for item in queue[0]:
            for c in item:
                n = d.get(c, c)
                yield n
                queue[1].append(n)
        queue = queue[1][::-1], queue[0]  # amortized constant time
        queue[1].clear()
this is in http://canonical.org/~kragen/sw/dev3/hcurvestream.py

which outputs about 5MB/s on this palmtop but will slow down as it runs into swap after generating less than the size of RAM in output

the output begins (via fold -w 70):

    afffb-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afff
    b-f-fb+f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-
    fb+f+a+f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-
    afffbf-f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-
    afffbfffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb
    +f+aafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a
    +f+b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf
    -f-b+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf
    ffafffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+aff
    fb+f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfff
    afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-f
    afffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b
    +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb-f-fb
    +f+af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffaf
    ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a-f-faf
    ffb-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f
    +af-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffb+f+afff
    b-f-fb+f+afffb+f+af-f-afffb-f-fb+f+af-f-afffb+f+afffb-f-fb+f+a+f+b+f+a
    f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbf-f-b+f+a
    f-f-afffb+f+afffb-f-fb+f+af-f-afffb-f-fb+f+afffb+f+af-f-afffbfffafffb-
1 comments