Introduction
Introduction
In general case rewriting system is a set of objects and relations on how to transform those objects.The definition of Mathematica function SubstitutionSystem is closest to s.c. L-system and morphic words.Even the simplest rules can produce interesting, strikingly different results.Clear visualization of such results is turtle graphic (AnglePath for WM).Here we will consider relatively simple transformations with alphabet {0,1}.Let’s take a rule 001, 110 and start with the symbol 0.Application of rule is described in SequenceReplace Details:Rule goes through a list, testing sequences that start at each successive element position. On each sequence, it tries in turn each of the transformation rules that were specified. If any of the rules apply, it replaces the sequence, then continues to go through the list, starting at the element position after the end of the sequence. So we have sequentially: 0 ⟶ 01 ⟶ 0101 ⟶ 01010101 ⟶ …Result is simple periodic sequence that appears with AnglePath[π/3] as regular hexagon:Just change one character: 001, 101, and we get a well-known rewriting Thue–Morse than produce fractal sequence with a lot of interesting properties and appears with turtle graphic as Koch curve:Another small changes, and strange, complicated figures appear: What structures can be created with (not too big) substitution rules?How can they be classified?If you’d like to see right now more visualizations, please go to the
Gallery section
.Here we make definitions for all the necessary functions.Rules definition
Rules definition
◼
Alphabet is a set of any different symbols.
Following the "simple into the complex" principle, here we will consider only the {0,1} alphabet . Also, it is very convenient for rules mass generation.
Following the "simple into the complex" principle, here we will consider only the {0,1} alphabet . Also, it is very convenient for rules mass generation.
◼
Word is sequence of symbols, may be empty.
◼
Rule is a ordered list of replacements (sub-rules) "word word": , , ...}
{
lefthandside
1
righthandside
1
lhs
2
rhs
2
◼
LHS may be any non-empty word , not just one symbol.
All LHS in rule have to be different.
All LHS in rule have to be different.
◼
RHS may be any word, even empty. RHS in rule may be duplicated.
◼
Initial state may be any, and as the observations show, general conclusions do not depend on the particular initial state. But to make substitution starts for sure, we will assume init =
lhs
1
◼
Rules representation
Rules representation
◼
Mainly we'll use normal Mathematica form:
{{0, 0} {1}, {1} {0, 1}}, {{0, 0} {}, {1, 1} {0}} etc.
{{0, 0} {1}, {1} {0, 1}}, {{0, 0} {}, {1, 1} {0}} etc.
◼
SequenceReplace needs a next form: {0,0} -> Sequence[1], {1}->Sequence[0,1]}
◼
Visual is a string form: 00"", 110
Rules generation
Rules generation
Rules are generated as combinations of all valid LHS and RHS.
Set signature σ as
Set signature σ as
σ=,=,
{,…,}
σ
1
σ
N
σ
k
L,R
len
k
L,R
len
k
Here N - number of replacements, — lengths of LHS and RHS in i replacement.
For example, Thue-Morse system has a signature {{1,2}, {1,2}}, and signature {{1,2}, {2,0}, {1,1}} will for example match a rule 001, 11"", 10
We will study only systems with N ⩽ 3 &&⩽2. But they are producing impressive results!
L,R
len
i
For example, Thue-Morse system has a signature {{1,2}, {1,2}}, and signature {{1,2}, {2,0}, {1,1}} will for example match a rule 001, 11"", 10
We will study only systems with N ⩽ 3 &&
L,R
len
Rules validation
Rules validation
For combinatorial analysis purposes, we can easily generate all possible rules for given signature. But now we’re interested in nontrivial sequences as the results of applying the rules. Therefore, some of the substitutions should be filtered at the generation stage.
◼
Duplicated LHS — remove all but first.
◼
Signature with empty LHS are not allowed.
◼
Tautologies (duplicated sub-rules) — remove all but first.
In[]:=
ClearAll[validRule,validRulesGen];validRulesGen[σ_]/;Depth[σ]!=3||Not@AllTrue[σ[[All,1]],#∈PositiveIntegers&]||Not@AllTrue[σ[[All,2]],#∈NonNegativeIntegers&]:=(Print["Invalid signature"];Abort[]);validRule[σ_,len_,num_]:=With[{rawRule=Partition[TakeList[PadLeft[IntegerDigits[num,2],len],Flatten@σ],2]},DeleteDuplicatesBy[DeleteCases[rawRule,s_/;First@s==Last@s],First]]; validRulesGen[σ_]:=Module{len=Total@Flatten@σ,indexes,ruleNums,rule,res},WriteString["stdout","Number of all rules: ",ruleNums=2^len]; res=DeleteDuplicates ReapDo rule=validRule[σ,len,ind]; If[rule!={},Sow[First@#Last@#&/@rule]] ,{ind,ruleNums}[[2,1]];WriteString["stdout"," >> Number of valid rules: ",Length@res,"\n"];res;
Get all valid rules with the signature of Thue-Morse (with filtering, so resulting signature may have less rank):
In[]:=
s={{1,2},{1,2}};TextGrid[Partition[ruleToStr/@validRulesGen[s],5],Frame->All]
Number of all rules: 64 >> Number of valid rules: 40
Out[]=
000 | 000, 100 | 000, 101 | 000, 110 | 000, 111 |
001 | 001, 100 | 001, 101 | 001, 110 | 001, 111 |
010 | 010, 100 | 010, 101 | 010, 110 | 010, 111 |
011 | 011, 100 | 011, 101 | 011, 110 | 011, 111 |
100, 000 | 100, 001 | 100, 010 | 100, 011 | 100 |
101, 000 | 101, 001 | 101, 010 | 101, 011 | 101 |
110, 000 | 110, 001 | 110, 010 | 110, 011 | 110 |
111, 000 | 111, 001 | 111, 010 | 111, 011 | 111 |
Sequence generation
Sequence generation
Simple, without filter
Simple, without filter
seqGen[rule, n] starts with rule's first LHS and output n-th result of SequenceReplace iterations.
seqGen[rule, n, True] output list of all n iterations.
seqGen[rule, n, True||False, init] starts with init.
seqGen[rule, n, True] output list of all n iterations.
seqGen[rule, n, True||False, init] starts with init.
In[]:=
ClearAll[seqGen];seqGen[rule_List,numIters_Integer,genList_:False,init_:None]:=With{r=ruleToSeq@rule,genFun=If[genList,NestList,Nest],start=If[init===None,rule〚1,1〛,init]}, genFun[SequenceReplace[#,r]&,start,numIters];
Length limitation and repeat detection
Length limitation and repeat detection
seqGenBeforeRepeat[rule, maxIter, maxLen] starts with rule's first LHS. Iterations stop when the length exceeds maxLen OR if results repeated OR after maxIters runs. Output prepended with flag "Were repeating detected?"
In[]:=
ClearAll[seqGenBeforeRepeat];seqGenBeforeRepeat[rule_,maxIters_,maxLen_]:=Module[{flag=True,r=ruleToSeq@rule,res},res=NestWhile[SequenceReplace[#,r]&,r〚1,1〛,((flag=UnsameQ[##])&&Length@Last[{##}]<maxLen)&,All,maxIters,1];{flag,res}];
Graphics presentation
Graphics presentation
Rules selection
Rules selection
Our task is to find interesting substitutions, i.e. those that generate infinitely growing, aperiodic sequences with a complex turtle graphic. Repeating the results as a whole has already been filtered out in the process of creating rules.
However, for example, the rule 111 is valid and generates infinitely increasing sequence. But each result is strictly periodic with period 1 and is therefore clearly uninteresting. The analysis of complexity and repetition in sequences is a complex area. Here we apply the built-in function FindTransientRepeat as follows.
Set threshold λ.
1. If Length@Last@FTR@seq == 0, than sequence is aperiodic (at this stage), therefore interesting.
2. If Length@Last@FTR@seq > λ, than at some point it's periodic, but with a sufficiently large period, which might also be interesting.
Set threshold λ.
1. If Length@Last@FTR@seq == 0, than sequence is aperiodic (at this stage), therefore interesting.
2. If Length@Last@FTR@seq > λ, than at some point it's periodic, but with a sufficiently large period, which might also be interesting.
We can analyze not only a single signature, but also the union of valid rules of multiple signatures. Let pick some promising examples:
Number of all rules: 1024 >> Number of valid rules: 520
Number of all rules: 256 >> Number of valid rules: 160
Number of all rules: 256 >> Number of valid rules: 208
Number of all rules: 256 >> Number of valid rules: 160
Number of all rules: 256 >> Number of valid rules: 208
Select those that give aperiodic results:
Look at turtle graphics:
Look at some selected process in dynamic:
Let’s create a qualitative image of process, which someone found most interesting
(this example takes 5-7 sec):
(this example takes 5-7 sec):
Further studies
Further studies
I’m already preparing notebook where properties of the resulting sequences will be discussed in more detail - growth rate, spectrum, randomness etc.
Gallery
Gallery
It is very difficult to systematize possible types of emerging sequences and turtle graphics. However, based on the information already available in mathematics, the following can be distinguished types of "interesting" rules and resulting sequences.
Finite non-trivial figures
Finite non-trivial figures
Infinite figures
Infinite figures
Simple fractals
Simple fractals
Complex fractals
Complex fractals
Rauzy-like fractals
Rauzy-like fractals
Infinite plane tesselations
Infinite plane tesselations
Flights
Flights
3D example
3D example
3D example
Back to the top
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Substitution systems simples rules for infinite aperiodic sequences and complex turtle diagrams
by Denis Ivanov
Wolfram Community, STAFF PICKS, May 9, 2024
https://community.wolfram.com/groups/-/m/t/3173124
by Denis Ivanov
Wolfram Community, STAFF PICKS, May 9, 2024
https://community.wolfram.com/groups/-/m/t/3173124