ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Q-Toothpicks (as seen on Nathaniel's blog)

For discussion of other cellular automata.

Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 25th, 2011, 2:01 pm

http://www.nathanieljohnston.com/2011/03/the-q-toothpick-cellular-automaton/

I've made a ruletable, you can download it here: http://cl.ly/0f202M2R0U3B0U172m2M
Here is an "explanation" of sorts of how I made the ruletable, in case you want to improve it or add new rules: http://pastebin.ca/2069071

So, on to the ruletable:

Nathaniel claims at the end of his article that objects made by multiple copies of his fifth object (which i'm calling the "mouth") are the only objects traced by this automata. This is not true. Objects made of multiple hearts flipped are also traced by this automaton, the first one starting on gen 32 (edit: 31):

x = 8, y = 4, rule = QTPCA
DCDCDCDC$A2.BA2.B$DCD2.CDC$ABABABAB!


(as an image: http://cl.ly/2q2y1Q362K0s0Z1f000N)
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby Nathaniel » May 25th, 2011, 3:21 pm

Fantastic work! I've updated the blog post to point to this thread. Have you found any other shapes by any chance? Any idea how the entire family of shapes can be characterized?
User avatar
Nathaniel
Site Admin
 
Posts: 407
Joined: December 10th, 2008, 3:48 pm
Location: New Brunswick, Canada

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 25th, 2011, 3:55 pm

First of all, I'm trying to classify the different patterns that may emerge:

Closed patterns: are patterns in which the ending of every Q-toothpick coincides with the start of another Q-toothpick on the corner of the grid tile.
Open patterns: are patterns in which the ending of every Q-toothpick does not coincide with the start of another Q-toothpick on the corner of the grid tile.
Organic patterns: are patterns which can be represented by removing Q-toothpicks from an infinite tiling of Q-circles over the plane.
Non-organic patterns: are patterns which can not be represented by removing Q-toothpicks from an infinite tiling of Q-circles over the plane.

I'm sure that non-organic patterns can be further classified, but I don't think they're relevant to the study of this automata.

And their properties:

Open organic patterns will always change in the next generation until they turn into one or more closed patterns (which may never happen; in that case they will expand infinitely).

Closed organic patterns which are not made of multiple closed organic patterns are called objects.

Organic patterns have a fascinating property called duality. The dual of an object is made by replacing every Q-toothpick with the Q-toothpick that goes from and to the same corners of the grid, but passing near the opposite corner. In QTPCA.table, that means replacing every 1 with a 3, every 2 with a 4, every 3 with a 1 and every 4 with a 2.

"Flipping" a pattern in Golly over both axis (that is, rotating it 90º twice) will return its dual object rotated 180º.

The dual of the circle is the star.
The dual of the bomb (the nameless blob from Nathaniel's post that forms the diagonal) is the bomb itself rotated 180º:

x = 7, y = 3, rule = QTPCA
CD2.AB$B.B.D.D$.DC2.BA!


The dual of the candybar is the peanut. (The peanut can be seen as a double bomb)

x = 10, y = 4, rule = QTPCA
AB4.CD$D.D3.B.B$.B.B3.D.D$2.DC4.BA!


The dual of this pattern is the pattern itself rotated 90º (I haven't named this one yet)
x = 4, y = 4, rule = QTPCA
.AB$C2.D$B2.A$.DC!
Last edited by ebcube on May 25th, 2011, 6:14 pm, edited 2 times in total.
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 25th, 2011, 3:56 pm

Nathaniel wrote:Fantastic work! I've updated the blog post to point to this thread. Have you found any other shapes by any chance? Any idea how the entire family of shapes can be characterized?


The patterns I posted previously have been either drawn by myself or generated with new seeds, not from the single Q-toothpick.
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 25th, 2011, 4:29 pm

Simple organic seeds and their characteristic (unique?) patterns:

2 toothpicks -> generates mosquito head (whose dual looks like 2 hearts + 1 bomb)

x = 14, y = 6, rule = QTPCA
10.CD$3.A5.A2.B$8.C3.C$.A6.B3.B$9.DCD.D$12.BA!


6 toothpicks -> generates maple leaf

x = 24, y = 11, rule = QTPCA
10.A5.CD2.CD$15.A2.BA2.B$8.A5.C7.C$14.B7.B$6.A8.D7.D$15.A7.A$4.A9.C7.
C$14.B7.B$2.A12.DCD2.CD.D$18.BA2.BA$A!


open loop -> generates the nameless object I drew on previous post whose dual was 90º itself + 2 ghosts (which is the dual of the heart; I called it ghost because it looks like one of pac-man's ghosts)

x = 20, y = 4, rule = QTPCA
10.CD6.CD$A.AB5.A2.B4.A.A$DC.C5.D2.C4.D.D$10.BA6.BA!
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 25th, 2011, 6:13 pm

Amazing properties of duality, #1:

[From now on, I'm calling the patterns whose dual is a 180º rotation of itself "mirror-dual", and those whose dual is a 90º rotation of itself "rotation-dual".

I'm also calling a rotation of the pattern in the plane 90º "intuitive rotation" or just "rotation", and a rotation of the pattern in QTPCA.table on Golly 90º "golly-rotation". Same for "flip" and "golly-flip".

A "golly-dual" is the dual of a pattern rotated (intuitively rotated) 180º. It is also the result of a double (2*90º) golly-rotation]

Question: Do infinite mirror-dual organic patterns exist?
Answer: Definitely yes.
Proof #1: Put a pattern and its dual together, displaced diagonally such as that:

a) both patterns don't overlap (except on the edges)
b) the pattern formed by both patterns together is still organic

Erase the internal edges. Voila! You now have a mirror-dual pattern.

Examples:

x = 17, y = 10, rule = QTPCA
AB2.CD2.AB$DC2.BA2.DCD$9.BA3$ABAB3.AB3.ABAB$D2.C2.C2.D2.D2.C$.BA3.BAB
A3.B.B$13.C2.D$13.BABA!


Proof #2: Take any existing mirror-dual pattern, and add circles and stars to its edges such as that every circle or star you add has at least one edge or corner in common with the original pattern. If you do it right, you'll need the same number of stars and circles to surround the pattern completely.

Erase the internal edges. Voila! You now have a mirror-dual pattern.

Examples:

x = 27, y = 19, rule = QTPCA
10.AB7.AB$9.CDCD5.C2.D$3.AB3.ABABAB3.A4.B$3.D.D2.DCD.DCD2.D5.D$4.BA3.
BABABA3.B4.A$10.DCDC5.D2.C$11.BA7.BA4$9.ABAB7.ABAB$8.CDCDCD5.C4.D$ABA
B3.ABABABAB3.A6.B$D2.C3.DCD2.CDC3.D6.C$.B.B4.BAB.BAB4.B5.B$.C2.D3.CDC
2.DCD3.C6.D$.BABA3.BABABABA3.B6.A$9.DCDCDC5.D4.C$10.BABA7.BABA!


Proof #3: Take any open pattern.

Create it's golly-dual.

Paste both together and remove internal edges. Voila!

(This might yield weird results that fit my definition of closed pattern, but not the intuitive definition of closed pattern)

Characteristics of a mirror-dual pattern:

Its golly-dual is equal to itself.

Its golly-flip under the X axis and its golly-flip under the Y axis yields the same result. Also, both its clockwise and counter-clockwise golly rotations yield the same result.

Any mirror-dual pattern can be decomposed, by means of drawing internal edges, into two patterns which are dual to each other.
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby 137ben » May 26th, 2011, 10:47 pm

Starting from a small random pattern, the limiting density seems to be roughly .68.
Starting from a random infinite pattern, the limiting density seems to be roughly .72.

Proof #1: Put a pattern and its dual together, displaced diagonally such as that:

a) both patterns don't overlap (except on the edges)
b) the pattern formed by both patterns together is still organic


Can this always be done?
Answer: yes. Select an edge at the boundary of the initial object. If this edge faces "outwards" in the primal object, then it will face "inwards" in the dual object, and so "fit" the primal and dual objects together along this edge. Since any finite object has a boundary edge, the two criteria can always be met in this way.

I would suggest a new golly script that makes the dual object of any pattern.
137ben
 
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby ebcube » May 27th, 2011, 10:14 am

If I knew how to make scripts... It just has to take the selected object and replace state 1 with 3, 2 with 4, 3 with 1 and 4 with 2.

Also, script for intuitive rotation/counter-rotation: golly-rotate/golly-counter-rotate the object, then replace every state with the previous / next state.
ebcube
 
Posts: 124
Joined: February 27th, 2010, 2:11 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby 137ben » June 12th, 2011, 8:03 pm

A pattern does not need to be organic to have a stable dual. For example:
x = 2, y = 2, rule = QTPCA
CB$DC!


For that matter, self-dual inorganic patterns exist:
x = 8, y = 3, rule = QTPCA
.AD3.CB$C.A2.A.C$DC3.BA!
137ben
 
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby edwardfanboy » October 5th, 2011, 9:43 pm

Here is a Golly-friendly version of the Q-Toothpicks ruletable posted on Nathaniel's blog for
everyone:
# Q-toothpicks
#
# rules: 16
#
# Golly rule-table format.
# Each rule: C,N,NE,E,SE,S,SW,W,NW,C'
#
# Default for transitions not listed: no change
#
# Variables are bound within each transition.
# For example, if a={1,2} then 4,a,0->a represents
# two transitions: 4,1,0->1 and 4,2,0->2
# (This is why we need to repeat the variables below.
#  In this case the method isn't really helping.)
#
# A ruletable-like version (it should be right, but I haven’t tested it)
# 0 is void
# 1 is a line from bottom-left to top-right via top-left
# 2 is a line from top-left to bottom-right via top-right (= 1 rotated 90º)
# 3 is a line from top-right to bottom-left via bottom-right (= 1 rotated 180º)
# 4 is a line from bottom-right to top-left via bottom-left (= 1 rotated 270º)
n_states:5
neighborhood:Moore
symmetries:rotate4
var a = {0,1,2,3,4}
var b = {0,1,2,3,4}
var c = {0,1,2,3,4}
var d = {0,1,2,3,4}
var e = {0,1,2,3,4}

0,0,1,0,a,b,c,d,e,3
0,a,b,0,2,0,c,d,e,4
0,a,b,c,d,0,3,0,e,1
0,0,a,b,c,d,e,0,4,2

0,a,b,c,d,0,1,0,e,3
0,0,a,b,c,d,e,0,2,4
0,0,3,0,a,b,c,d,e,1
0,a,b,0,4,0,c,d,e,2

0,0,a,b,c,d,e,1,0,2
0,2,0,0,a,b,c,d,e,3
0,a,b,3,0,0,c,d,e,4
0,a,b,c,d,4,0,0,e,1

0,1,a,b,c,d,e,0,0,4
0,0,0,2,a,b,c,d,e,1
0,a,b,0,0,3,c,d,e,2
0,a,b,c,d,0,0,4,e,3

P.S. This info came from the ruletable "Wireworld".

EDIT: It doesn't seem to work. Please correct any of my errors.
Don't crash people's ideas:
If you're going to say one of my (or anyone else's) things is stupid,
think of ways to improve it or show me (or whoever you are insulting) something better.

See two Von Neumann neighborhood rules I made for circuits and arrows
edwardfanboy
 
Posts: 80
Joined: September 16th, 2011, 10:29 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby Omar » October 15th, 2011, 9:59 am

Note that every object is a closed region which contains 2^k virtual circles with radius 1 and 2^k-1 virtual diamonds, for example: a 2x2-object is a closed region which contains exactly four virtual circles and three virtual diamonds, a 2x4-object is a closed region which contains exactly 8 virtual circles and 7 virtual diamonds, etc. Note that a "heart" can be considered a 1x2-object which contains two virtual circles and a virtual diamond.
Omar
 
Posts: 2
Joined: October 15th, 2011, 9:50 am

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby Wojowu » October 15th, 2011, 1:28 pm

For that matter, self-dual inorganic patterns exist:
x = 8, y = 3, rule = QTPCA
.AD3.CB$C.A2.A.C$DC3.BA!

I've found smaller inorganic self-dual pattern
x = 2, y = 2, rule = QTPCA
AB$BA!

Also, I found that density of pattern starting from one toothpick is 2/3 in densest moment (in generations of 2^n) when it makes filled square and approximately 0.47 in least dense moment (gen 2^(n-8)*413). I don't know why then. I seen that then boundary is very convoluted.
First question ever. Often referred to as The Question. When this question is asked in right place in right time, no one can lie. No one can abstain. But when The Question is asked, silence will fall. Silence must fall. The Question is: Doctor Who?
User avatar
Wojowu
 
Posts: 210
Joined: October 1st, 2011, 1:24 pm

Re: Q-Toothpicks (as seen on Nathaniel's blog)

Postby Omar » September 27th, 2012, 7:13 pm

It appears that the number of hearts present in the n-th generation (Sloane's A188346) equals the number of rectangles of area = 2 present in the (n - 2)nd generation of the toothpick structure of Sloane's A139250, assuming the toothpicks have length 2, if n >= 3.
Omar
 
Posts: 2
Joined: October 15th, 2011, 9:50 am


Return to Other Cellular Automata

Who is online

Users browsing this forum: LaundryPizza03, Ronan and 2 guests