One Dimensional Life

What is a 1D automaton?

Consider an infinite series of locations placed along an infinite, one-dimensional line. Each location can be either off or on, and the whole line 'evolves' through 'generations' where each cell takes up a new state that depends only on the previous state of itself and its neighbours to left & right.

There's a lot of fun in programming this situation, and all the possibilities. Wikipedia is very good- but don't look there until you've programmed it yourself!!

Of course, you won't be programming an infinite 1D line, but one of finite length. Short lines ( say 20-cell sections) allow drawing on screen as decent-sized squares or circles. Wider screens could allow up to say 1920 cells- or bigger if you allowed panning.

Here's a longer sequence, represented at pixel level...

This evolves after two steps to...

but keeps changing forever.

Further considerations

What to use as an initial seed generation is also not trivial. You can try starting with regular or irregular patterns. A 50% random probability that a given cell is off or on is a good start. Another is runs of offs or ons that have decreasing probability as the sequence gets longer.

You also may now have realised that if you look only at a limited range of cells, you'll have to decide how to treat the two end-marker cells, which have only themselves and ONE neighbour as 'parents'. You could pretend that there is ALWAYS a cell at each end which stays as an off or an on. More helpfully, think of your chosen width as looping back and closing on itself. The rightmost cell has as parents itself and its lefthand neighbour AND the most leftward cell in your row. Similarly the first cell has itself and a righthand neighbour, plus the extreme righthand one. This is described as 'toroidal topology'.

By now you may have realised that by animating the generation sequence,

or stacking each generation of the 1D line vertically on a screen you can 'see' its evolution easily.

Results

It turns out that certain patterns crop up regularly for different rules. Common behaviours include:-

  • All cells die out (or all become on) forever.

  • A pattern becomes static and never changes further once that state is reached.

  • A pattern steps left or right one place per generation. ( as above)

    However the most interesting cases are where no stable state is reached, and instead a chaotic pattern goes on forever.

    Some of the possibilities, as shown in my Ubuntu directory..


    Finding a 'rule' for the computation.

    The possibilities for a particular case are set out like the table below. The desired outputs together form a binary number, whose decimal equivalent is used as the 'Rule Number' for it.

    Since a toroidal geometry wraps round, I particularly like being able to design automaton lamp-shades!


    The Liberty BASIC code I used.

        '   *******************************************************************
        '   **       oneD_automaton17_mono.bas    generate 1D automata       **
        '   **              tenochtitlanuk JohnF June 21 2014                **
        '   **                  See Wikipedia & Wolfram                      **
        '   *******************************************************************
    
    '   To-dos
    '       Call ImageMagick to make animation, & call Web browser to display.
    '       I'd accidentally backwards-labelled the rule descriptor. Now corrected.
    '       Set whether to randomize the starting pattern in different ways..
    
    '   Further work needed, including the following...
    '       Various lines remmed, that enable saving whole evolution or an animation.
    '       Ditto lines which create different start patterns.
    '       Also lines- presently incomplete/experimental- which automatically describe the type.
    
          nomainwin
    
          global       alphanum$
          alphanum$    ="0123456789abcdefghijklmnopqrstuvwxyz"
    
          WindowWidth  = 1120
          WindowHeight =  720
    
          graphicbox #w.gb,        5,   5, 1100, 670
    
    
          open "1D Automaton v8.00" for window as #w
    
          #w "trapclose [quit]"
    
          #w.gb "down ; size 2 ; color cyan"
          #w.gb "font arial 16 bold"
    
          width  =360
    
    [forever]
          'rule =int( 256 *rnd( 1))  '   74 ' 57 ' 105 ' 110 ' 126 etc 0<-->255
          for rule =0 to 255
    
          scan
    
          #w.gb "cls ; up ; goto 6 8 ; down ; backcolor 200 200 200 ; fill black ; color 200 200 200 ; boxfilled 1088 640 ; flush"
    
          'randomize( 0.123456789) '   rnd( 1))
    
          rule$ =toBase$( 2, rule)
    
          #w.gb "color black"
          #w.gb "up ; goto 820 630 ; down"
          #w.gb "\ Rule "; rule
          #w.gb "up ; goto 920 630 ; down"
          #w.gb "\ "; rule$; " "
          #w.gb "flush"
    
          c =1
    
          now$ =""
    goto [skip]
          for j =1 to width
              if rnd( 1) <0.7 then
                  if c =1 then now$ =now$ +"1"
                  if c =0 then now$ =now$ +"0"
              else
                  if c =1 then c =0: now$ =now$ +"0" else c =1: now$ =now$ +"1"
              end if
          next j
    
          now$ =left$( now$, 40) +stringChar$( 10, "10") +mid$( now$, 61, 50) +stringChar$( 60, "1") +mid$( now$, 141, 50) +stringChar$( 60, "0") +mid$( now$, 281)
    
    [skip]      now$ =stringChar$( 179, "0") +"1" +stringChar$( 180, "0")
    
          ln        =len( now$)
          diag$     =""
          l         =0
          r         =0
    
          for generation =0 to 189
              scan
    
              for cell =1 to width
                  if mid$( now$, cell, 1) ="1" then
                      if generation = 0 then #w.gb "color 20 20 255" else #w.gb "color black"
                      #w.gb "set "; 5 +3 *cell; " "; 10 +generation *3
                      #w.gb "color red ; up ; goto "; 5 +3 *cell; " "; 1
                      #w.gb "down ; goto "; 5 +3 *cell; " "; 5
                      #w.gb "color black"
                  else
                      #w.gb "color 200 200 200"
                      #w.gb "set "; 5 +3 *cell; " "; 10 +generation *3
                      #w.gb "color black ; up ; goto "; 5 +3 *cell; " "; 1
                      #w.gb "down ; goto "; 5 +3 *cell; " "; 5
                  end if
              next cell
    
              'timer 1000, [a]
              'wait
            [a] 'timer 0
    
              #w.gb "flush"
    
              'timer 1000, [b]
              'wait
            [b] 'timer 0
    
              next$ = ""
    
              for cell =1 to width
                  if cell =1     then lhn$ =mid$( now$, width, 1) else lhn$ =mid$( now$, cell -1, 1)
                  if cell =width then rhn$ =left$( now$, 1)       else rhn$ =mid$( now$, cell +1, 1)
                  above$    =mid$( now$, cell, 1)
                  parent$   =lhn$ +above$ +rhn$
    
                  select case parent$
                      case "000"
                          child$ =mid$( rule$, 8, 1)
                      case "001"
                          child$ =mid$( rule$, 7, 1)
                      case "010"
                          child$ =mid$( rule$, 6, 1)
                      case "011"
                          child$ =mid$( rule$, 6, 1)
                      case "100"
                          child$ =mid$( rule$, 4, 1)
                      case "101"
                          child$ =mid$( rule$, 3, 1)
                      case "110"
                          child$ =mid$( rule$, 2, 1)
                      case "111"
                          child$ =mid$( rule$, 1, 1)
                  end select
    
                  next$ =next$ +child$
              next cell
    
              penultimate$ =now$
    
              if next$ =now$ then
                  #w.gb "up ; goto 520 630 ; down": #w.gb "\ STATIC"
              else
                  'flag =0
                  if mid$( next$, 2, 100) =mid$( now$, 3, 100) then #w.gb "up ; goto 450 630 ; down": #w.gb "\ Left  diagonal   ": l =1
                  if mid$( next$, 2, 100) =mid$( now$, 1, 100) then #w.gb "up ; goto 450 630 ; down": #w.gb "\ Right diagonal   ": r =1
              end if
    
              if mid$( next$, 2, len( next$) -1) =mid$( oppo$( now$), 2, len( next$) -1) then #w.gb "up ; goto 220 630 ; down": #w.gb "\ alternating in place"
    
              if mid$( next$, 2, len( next$) -1) =mid$( oppo$( now$), 1, len( next$) -2) then #w.gb "up ; goto 220 630 ; down": #w.gb "\ alternating and R-shift"
    
              if mid$( next$, 2, len( next$) -1) =mid$( oppo$( now$), 3, len( next$)   ) then #w.gb "up ; goto 220 630 ; down": #w.gb "\ alternating and L-shift"
    
              temp$ =now$: now$  =next$: next$ =temp$   '   swap so now$ can be re-used to create next generation
    
              if not( instr( now$, "1")) then #w.gb "up ; goto 100 630 ; down": #w.gb "\ SOLID '1's.   "
    
              if not( instr( now$, "0")) then #w.gb "up ; goto 100 630 ; down": #w.gb "\ SOLID '0's.   "
    
              if instr( now$, "1") =0 then
                  #w.gb "up ; goto 100 630 ; down"
                  #w.gb "\ TERMINATED   "
                  terminated =1
                  #w.gb "up ; goto 100 630 ; down"
                  #w.gb "\                          "
                  exit for   '   all cells dead....
              end if
    
              '#w.gb "flush"
              '#w.gb "getbmp scr 0 2 1150 6"
              'bmpsave "scr", "screens/automaton" +right$( "000" +str$( generation), 3) +".bmp"
    
            next generation
    
            if flag =1 then flag =0: #w.gb "up ; goto 200 630 ; down": #w.gb "\ STATIC "
            if terminated <>1 and now$ <>next$ then #w.gb "up ; goto 300 630 ; down": #w.gb "\ ??CHAOTIC "
            if instr( now$, "0") <>0 then #w.gb "up ; goto 920 630 ; down": #w.gb "\                    "
            if mid$( next$, 2, len( next$) -2) =mid$( penultimate$, 4, len( next$) -4) then #w.gb "up ; goto 220 630 ; down": #w.gb "\ alternating and LL-shift"
    
            #w.gb "flush"
            #w.gb "getbmp scr 0 5 1150 660"
            bmpsave "scr", "screens/automaton_1_" +right$( "000" +str$( rule), 3) +".bmp"
    
            timer 2000, [onward]
            wait
          [onward]
            timer 0
            terminated =0
        'goto [forever]
        next rule
    
        wait
    
     [quit]
        close #w
        end
    '   ___________________________________________________________________________________________________
        function oppo$( in$)
            for i =1 to len( in$)
                if mid$( in$, i, 1) ="1" then oppo$ =oppo$ +"0" else oppo$ =oppo$ +"1"
            next i
        end function
    
        function toBase$( base, number) '   Convert decimal variable to number string.
            toBase$             =""
            for i =10 to 1 step -1
                remainder   =number mod base
                toBase$     =mid$( alphanum$, remainder +1, 1) +toBase$
                number      =int( number /base)
                if number <1 then exit for
            next i
            toBase$ =right$( "00000000" +toBase$, 8)
        end function
    
        function decFromBin( in$)   '   given 3 char string rep'g a binary number, return the number
            a =0
            for j =1 to 3
                a =a +val( mid$( in$, j, 1)) *2^( 3 -j)
            next j
            decFromBin =a
        end function
    
        function stringChar$( n, ch$)
            for i =1 to n
                stringChar$ =stringChar$ +ch$
            next i
        end function