Rule:3n+1

@RULE 3n+1

@TABLE

1. Rule table for 3n+1 problem
3. Starting with a single cell in state 6, this produces a graph in
4. which the n'th column tells how many iterations of f(x) = (if x is
5. even then x/2 else 3x+1) are needed to reach 1, starting from n.
6. The still-unproved Collatz conjecture states that this iteration will
7. always reach 1 eventually.
9. The copy and increment states are used to create the binary
10. representation of n in the n'th column: The 1's bit is at the
11. top, the 2's bit below that, the 4's bit below that, etc. State 1
12. represents a 0 bit, state 2 represents a 1. At the same time, an
13. iteration counter is created 3 cells above the 1's bit.
15. After that, there's no communication between columns. Each column
16. has a Turing machine whose read/write head moves up and down
17. through the number. As it moves downward, it changes x to x/2
18. if x is even or to 3x+1 if x is odd. (The number isn't changed as the
19. head moves upward.) Whenever the head reaches the top, it sends a signal
20. upward to increment the iteration counter. When the number becomes 1,
21. the Turing machine stops, leaving a single cell where the 1's bit was.
22. After that, the upward signals are eventually absorbed by the iteration
23. counter, producing the graph. (k iterations put the counter k+4 units
24. above the axis.)
26. Using a different initial pattern, the rule can produce the portion of
27. the graph starting with any given integer n: Use a column with a cell
28. in state 21, a dead cell below that, a cell in state 6 below that, and
29. the binary representation of n below that. E.g. to start at 100 (which
30. is 1100100 in binary), the column should have cells in these states,
31. from top to bottom:
32. 21, 0, 6, 1, 1, 2, 1, 1, 2, 2
34. Dean Hickerson, 10/8/2009

n_states:25 neighborhood:vonNeumann symmetries:none

1. States are:
2. 0-2 blank, 0, 1
3. 3-5 move up (blank, 0, 1)
4. 6-8 copy to next column (blank, 0, 1)
5. 9-10 increment (blank, 0)
6. 11 update (change n to n/2 or 3n+1)
7. 12 pause before copy
8. 13-14 divide by 2 (0, 1)
9. 15-20 multiply by 3, with bit and carry:
10. 15 = 0 c0, 16 = 1 c0, 17 = 0 c1, 18 = 1 c1, 19 = 0 c2, 20 = 1 c2
11. 21 iteration counter
12. 22 tell iteration counter to increment
13. 23 increment counter
14. 24 create iteration counter

var z={1} var o={2} var bit={1,2} var up={3,4,5} var copy={6,7,8} var inc={9,10} var update={11} var div2={13,14} var carry0={15,16} var carry1={17,18} var carry2={19,20} var 0carry={15,17,19} var 1carry={16,18,20} var anyN={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} var anyE={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} var anyS={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24} var anyW={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}

1. Kludge to allow a 1-bit starting pattern.

0,6,0,0,0,7 7,0,0,0,0,0

1. stop if number=1

5,0,anyE,0,anyW,1

1. move up

z,anyN,anyE,up,anyW,4 o,anyN,anyE,up,anyW,5 0,anyN,anyE,up,anyW,11 3,anyN,anyE,anyS,anyW,0 4,anyN,anyE,anyS,anyW,1 5,anyN,anyE,anyS,anyW,2

1. copy

z,copy,anyE,anyS,anyW,7 o,copy,anyE,anyS,anyW,8 6,anyN,anyE,anyS,anyW,0 7,anyN,anyE,anyS,anyW,1 8,anyN,anyE,0,anyW,5 # at bottom; copy -> move up 8,anyN,anyE,anyS,anyW,2

1. copy from above. These are the only transitions involving 2 columns.

0,anyN,anyE,anyS,7,1 0,anyN,anyE,anyS,8,2 0,anyN,anyE,anyS,6,9 # copy at top tells next column to increment

1. increment

9,0,anyE,0,0,9 # pause before starting increment 9,anyN,anyE,anyS,anyW,12 12,anyN,anyE,anyS,anyW,6 o,inc,anyE,anyS,anyW,10 z,inc,anyE,anyS,anyW,2 0,inc,anyE,anyS,anyW,2 10,anyN,anyE,anyS,anyW,1

1. divide by 2

update,anyN,anyE,anyS,anyW,0 z,update,anyE,z,anyW,13 z,update,anyE,o,anyW,14 bit,div2,anyE,z,anyW,13 bit,div2,anyE,o,anyW,14 bit,div2,anyE,0,anyW,3 # at bottom; divide becomes move up 13,anyN,anyE,anyS,anyW,1 14,anyN,anyE,anyS,anyW,2

1. 3n+1

z,carry0,anyE,anyS,anyW,15 0,carry0,anyE,anyS,anyW,3 # at bottom; multiply becomes move up o,carry0,anyE,anyS,anyW,18 z,carry1,anyE,anyS,anyW,16 0,carry1,anyE,anyS,anyW,16 o,carry1,anyE,anyS,anyW,19 o,update,anyE,anyS,anyW,19 z,carry2,anyE,anyS,anyW,17 0,carry2,anyE,anyS,anyW,17 o,carry2,anyE,anyS,anyW,20

0carry,anyN,anyE,anyS,anyW,1 1carry,anyN,anyE,anyS,anyW,2

1. count iterations

0,anyN,anyE,11,anyW,22 # create increment signal 22,anyN,anyE,anyS,anyW,0 0,anyN,anyE,22,anyW,22 # signal moves up 21,0,anyE,22,anyW,23 # counter absorbs signal 23,0,anyE,0,anyW,0 0,0,anyE,23,anyW,21 # counter increments

1. create iteration counters

0,0,0,9,0,24 24,0,0,9,0,0 0,0,0,24,anyW,21

@COLORS

1. written by Langtons-Ant-gen.py

0 48 48 48 1 0 64 128 2 0 255 255 3 148 148 148 4 128 255 0 5 255 0 128 6 0 128 255 7 1 159 0 8 159 0 1 9 255 254 96 10 0 1 159 11 255 255 255 12 254 96 255 13 126 125 21 14 21 126 125 15 125 21 126 16 255 116 116 17 116 255 116 18 116 116 255 19 228 227 0 20 28 255 27 21 255 27 28 22 0 228 227 23 227 0 228 24 27 28 255 25 59 59 59 26 234 195 176 27 175 196 255 28 171 194 68 29 194 68 171 30 68 171 194 31 72 184 71 32 184 71 72 33 71 72 184 34 169 255 188 35 252 179 63 36 63 252 179 37 179 63 252 38 80 9 0 39 0 80 9 40 9 0 80 41 255 175 250 42 199 134 213 43 115 100 95 44 188 163 0 45 0 188 163 46 163 0 188 47 203 73 0 48 0 203 73 49 73 0 203 50 94 189 0 51 189 0 94