How to obtain a recursively enumerable subshift with a bidimensional SFT (ANR Subtile meeting, LAMFA Amiens) N. Aubrun and M. Sablik IGM, University Paris-Est and LATP, University of Provence October 22, 2009 N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 1 / 26 Outline 1 Subshifts and tilings Denitions Four classes of operations on subshifts 2 The main result A simulation result Sketch of the proof 3 Computation zones for Turing machines Adding Turing machine calculations in computation zones 4 Turing machines calculations The machines MF and MSearch 5 The nal construction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 1 / 26 Subshifts and classes of subshifts Zd , A nite alphabet F a set of d -dimensional nite patterns conguration c ∈ AZ subshift dened by the set of forbidden patterns F : d XF = {c ∈ AZd /∀p ∈ F , p does not appear in c } ⊆ AZd N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 2 / 26 Subshifts and classes of subshifts Zd , A nite alphabet F a set of d -dimensional nite patterns conguration c ∈ AZ subshift dened by the set of forbidden patterns F : d XF = {c ∈ AZd /∀p ∈ F , p does not appear in c } ⊆ AZd Σ fullshift ⇔ Σ = XF , F = ∅ Σ subshift of nite type (SFT) ⇔ ∃F nite set of patterns, Σ = XF tilings ≈ 2-dimensional SFT Σ recursively enumerable (RE) subshift ⇔ ∃F RE set of patterns, Σ = XF . N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 2 / 26 An example of 2-dimensional SFT F= N. Aubrun and M. Sablik () ß ™ , How to obtain a RE subshift ? October 22, 2009 3 / 26 An example of 2-dimensional SFT F= ß ™ , ⇓ .. . .. . XF : ... , ... ... .. . N. Aubrun and M. Sablik () ... .. . How to obtain a RE subshift ? October 22, 2009 3 / 26 Operations on subshifts, simulation S = set of all subshifts (all dimensions and alphabets) Operation on subshifts: I I op : S → S or op : S × S → S Closure of a class of subshifts U under a set of operations Op : C lOp (U) = smallest set stable by Op which contains U. T simulates T0 by Op if T0 ∈ C lOp (T) (denoted by T0 ≤Op T). C lOp (T) = {T0 : T0 ≤Op T}. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 4 / 26 Product operation P Denition If Σ = XF ⊆ AZ and Σ0 = XF 0 ⊆ BZ are two subshifts with the same dimension: d d d Σ × Σ0 = XF ×F 0 ⊆ (A × B)Z . N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 5 / 26 Product operation P Denition If Σ = XF ⊆ AZ and Σ0 = XF 0 ⊆ BZ are two subshifts with the same dimension: d d d Σ × Σ0 = XF ×F 0 ⊆ (A × B)Z . Σ = XF ⊆ {a, b , c }Z 2 F= ß x a a x , y b Σ0 = XF 0 ⊆ F0 = b x , y c , ß N. Aubrun and M. Sablik () Z2 ™ , ™ c y Σ × Σ0 ⊆ {a, b , c , a, b , c }Z 2 ⇒ F × F0 = ß x a How to obtain a RE subshift ? a x , y a a x , y a a ,... y October 22, 2009 ™ 5 / 26 Product operation P Denition If Σ = XF ⊆ AZ and Σ0 = XF 0 ⊆ BZ are two subshifts with the same dimension: d d d Σ × Σ0 = XF ×F 0 ⊆ (A × B)Z . Σ = XF ⊆ {a, b , c }Z 2 F= ß x a a x , y b Σ0 = XF 0 ⊆ F0 = b x , y c , ß Remark : N. Aubrun and M. Sablik () Z2 ™ , ™ c y Σ × Σ0 ⊆ {a, b , c , a, b , c }Z 2 ⇒ F × F0 = ß C lP (SFT ) = SFT x a How to obtain a RE subshift ? a x , y a a x , y a a ,... y October 22, 2009 ™ 5 / 26 Finite type operation FT Denition If Σ = XF ⊆ AZ is a subshift and F 0 a nite set of patterns : d φFT (F 0 , Σ) = XF ∪F 0 . N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 6 / 26 Finite type operation FT Denition If Σ = XF ⊆ AZ is a subshift and F 0 a nite set of patterns : d φFT (F 0 , Σ) = XF ∪F 0 . Remark : N. Aubrun and M. Sablik () C lFT (FS) = SFT How to obtain a RE subshift ? October 22, 2009 6 / 26 Factor operation F Denition If Σ ⊆ AZ is a subshift and Π : AZ → BZ a morphism (continue and d σ ◦ Π = Π ◦ σ ), Π(Σ) ⊆ B Z is a factor of Σ. d N. Aubrun and M. Sablik () d d How to obtain a RE subshift ? October 22, 2009 7 / 26 Factor operation F Denition If Σ ⊆ AZ is a subshift and Π : AZ → BZ a morphism (continue and d σ ◦ Π = Π ◦ σ ), Π(Σ) ⊆ B Z is a factor of Σ. d d d Example : A = {0, 1, 2} and Σ ⊆ AZ Σ = X{00,22,01,12} and Π(0) = Π(2) = 0,Π(1) = 1 ⇒ Π(Σ) = {x ∈ {0, 1, 2}Z / blocks of consecutive 0 are of even length} N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 7 / 26 Factor operation F Denition If Σ ⊆ AZ is a subshift and Π : AZ → BZ a morphism (continue and d σ ◦ Π = Π ◦ σ ), Π(Σ) ⊆ B Z is a factor of Σ. d d d Example : A = {0, 1, 2} and Σ ⊆ AZ Σ = X{00,22,01,12} and Π(0) = Π(2) = 0,Π(1) = 1 ⇒ Π(Σ) = {x ∈ {0, 1, 2}Z / blocks of consecutive 0 are of even length} Remark : SFT ( C lF (SFT ). C lF (SFT ) is the class of soc subshifts. In dimension 1, soc subshifts are XL where L is regular. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 7 / 26 Subaction operation SA Denition G a subgroupe of Zd generated u1, u2, . . . , ud (d ≤ d ). If Σ ⊆ AZd is a subshift: n d φSA (G, Σ) = y ∈ AZ : ∃x ∈ Σ tel que ∀i1 , . . . , id ∈ Zd , 0 0 0 0 0 yi1 ,...,id 0 = xi1 u1 +···+id 0 ud 0 . N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 8 / 26 Example of sub-action F= ß ™ , , , ,..., G = {(i , i ) ∈ Z2, i ∈ Z} N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 9 / 26 Example of sub-action F= ß ™ , , , ,..., G = {(i , i ) ∈ Z2, i ∈ Z} G φSA ( , XF ) = X¶ N. Aubrun and M. Sablik () , How to obtain a RE subshift ? i ,i =0...2 © October 22, 2009 9 / 26 Some simulation results SFT ( C lSA (SFT ) C lSA (SFT ) =?? C lSA (RE ) = RE C lF ,SA (SFT ) = RE (Hochman) N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 10 / 26 Outline 1 Subshifts and tilings Denitions Four classes of operations on subshifts 2 The main result A simulation result Sketch of the proof 3 Computation zones for Turing machines Adding Turing machine calculations in computation zones 4 Turing machines calculations The machines MF and MSearch 5 The nal construction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 10 / 26 The main result Theorem (Hochman) Any RE subshift of dimension d can be obtain with factor and subaction operations from an SFT of dimension d + 2. C lF ,SA (SFT ∩ Sd +2 ) ∩ S≤d = RE ∩ S≤d N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 11 / 26 The main result Theorem (Hochman) Any RE subshift of dimension d can be obtain with factor and subaction operations from an SFT of dimension d + 2. C lF ,SA (SFT ∩ Sd +2 ) ∩ S≤d = RE ∩ S≤d Theorem (A&S) Any RE subshift of dimension d can be obtain with factor and subaction operations from an SFT of dimension d+1. C lF ,SA (SFT ∩ Sd +1 ) ∩ S≤d = RE ∩ S≤d N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 11 / 26 Some elements of the proof We want to simulate a RE subshift Σ ⊆ AΣ Z with a 2-dimensional SFT (particular case d = 1, but easy to generalize). We need two Turing machines: MF : enumerates forbidden patterns for Σ and chacks the validity of Σ MSearch : explore the bits of AΣ Z N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 12 / 26 Coding a Turing machine with a SFT Denition: Turing machine A Turing machine is M = (Q , Γ, ], q0 , δ, QF ) where: Q is a nite set of states; q0 ∈ Q is the initial state; Γ is a nite alphabet; ]∈ / Γ is the blank symbol δ : Q × Γ → Q × Γ × {←, · , →} is the transition function; F ⊂ QF is the set of nal states. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 13 / 26 Coding a Turing machine with a SFT Denition: Turing machine A Turing machine is M = (Q , Γ, ], q0 , δ, QF ) where: Q is a nite set of states; q0 ∈ Q is the initial state; Γ is a nite alphabet; ]∈ / Γ is the blank symbol δ : Q × Γ → Q × Γ × {←, · , →} is the transition function; F ⊂ QF is the set of nal states. The rule δ(q1 , x ) = (q2 , y , ←) will be coded by: (q2 , z ) z ⇒ subshift of nite type N. Aubrun and M. Sablik () y z0 (q1 , x ) z 0 TM for a Turing machine M How to obtain a RE subshift ? October 22, 2009 13 / 26 Coding a Turing machine with a SFT Denition: Turing machine A Turing machine is M = (Q , Γ, ], q0 , δ, QF ) where: Q is a nite set of states; q0 ∈ Q is the initial state; Γ is a nite alphabet; ]∈ / Γ is the blank symbol δ : Q × Γ → Q × Γ × {←, · , →} is the transition function; F ⊂ QF is the set of nal states. The rule δ(q1 , x ) = (q2 , y , ←) will be coded by: (q2 , z ) z y z0 (q1 , x ) z 0 TM for a Turing machine M Problem : beginning of the calculation, multiple heads, . . . ⇒ subshift of nite type N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 13 / 26 Dierent levels of the construction We construct a 2-dimensional soc subshift: level 1: some x ∈ AΣZ (a potential x ∈ Σ), level 2: computation zones, used by machines MF and MSearch, level 3: Turing machines MF , and communication with MSearch, level 4: Turing machines MSearch and internal communication between them. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 14 / 26 Level 1: a potential x ∈ Σ fullshift AΣ Z nite type condition y(i ,j ) = y(i ,j +1) same conguration x ∈ AΣ Z on every row 2 rst level T1 = φFT Åß a , a 6= b ∈ AΣ b ™ , AΣ Z 2 ã ⇒ We want to exclude forbidden patterns of Σ. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 15 / 26 Outline 1 Subshifts and tilings Denitions Four classes of operations on subshifts 2 The main result A simulation result Sketch of the proof 3 Computation zones for Turing machines Adding Turing machine calculations in computation zones 4 Turing machines calculations The machines MF and MSearch 5 The nal construction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 15 / 26 Initialization of a TM calculation If a particular tile appears once, it can be used to initialize a calculation: But it is impossible to force the presence of one copy of a particular tile with a subshift (compacity). N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 16 / 26 Substitutive soc subshifts a substitution is a function s : A → AUk where Uk = [1; k ] × [1; k ] a s-pattern is a pattern obtained by iteration of the substitution s on a letter the subshift generated by a substitution s is the set of congurations x such that any pattern that appears in x also appears in a s -pattern Theorem (Mozes) If a substitution satises some good properties, then the subshift it generates is a soc subshift. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 17 / 26 The substitution ˜s Mozes theorem ⇒ soc subshift TSquares N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 18 / 26 The substitutive subshift TSquares subshift TSquares : N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 19 / 26 The substitutive subshift TSquares subshift TSquares : N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 19 / 26 The substitutive subshift TSquares subshift TSquares : : computation tile (Turing machine calculation) : obstruction tile (communication inside a same zone) N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 19 / 26 Computation and obstruction tiles a a a a a a a (q0 , ]) a a a (q0 , ]) (q1 , ]) ] (q0 , ]) (q0 , ]) (q1 , ]) ] (q0 , ]) N. Aubrun and M. Sablik () a a a a a b b b b (q1 , ]) (q1 , ]) (q1 , ]) ] k k k (q2 , ]) ] ] ] ] k a (q0 , ]) (q2 , ]) ] a (q0 , ]) ] How to obtain a RE subshift ? k (q1 , ]) ] (q2 , ]) ] (q1 , ]) ] ] (q3 , ]) (q3 , ]) (q3 , ]) ] ] ] ] ] October 22, 2009 20 / 26 The computation zones: stripes N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 21 / 26 Using computation zones (stripes) condition Clock : a clock is increased at each calculation step, and clock≥ 0 condition Init : the entry word where clock= 0 is the empty word, and the tape is initially lled with ] symbol; condition Head : the initial state q0 appears where clock= 0; condition Stop : when a side of a stripe is reached by the head of the machine, the calculation stops and the tape content is just copied out (clock is no longer increased); condition Final : when a nal state is reached, the tape content is just copied out for next steps of calculation (clock is no longer increased); condition Transfer : when the head reaches an obstruction zone, the information is transferred (horizontally or vertically) to the next computation tile. N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 22 / 26 Using computation zones (stripes) condition Clock : a clock is increased at each calculation step, and clock≥ 0 condition Init : the entry word where clock= 0 is the empty word, and the tape is initially lled with ] symbol; condition Head : the initial state q0 appears where clock= 0; condition Stop : when a side of a stripe is reached by the head of the machine, the calculation stops and the tape content is just copied out (clock is no longer increased); condition Final : when a nal state is reached, the tape content is just copied out for next steps of calculation (clock is no longer increased); condition Transfer : when the head reaches an obstruction zone, the information is transferred (horizontally or vertically) to the next computation tile. Dene the SFT TM , zones for a Turing machine M: TM,zones = φFT ({Clock, Head, Init, Stop, Final, Transfer}, φP (TSquares, TM)) N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 22 / 26 Outline 1 Subshifts and tilings Denitions Four classes of operations on subshifts 2 The main result A simulation result Sketch of the proof 3 Computation zones for Turing machines Adding Turing machine calculations in computation zones 4 Turing machines calculations The machines MF and MSearch 5 The nal construction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 22 / 26 Level 3: Enumeration of forbidden patterns MF generates forbidden patterns for Σ MF is given a responsibility zone, and ensure no forbidden pattern appear in it N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 23 / 26 Level 3: Enumeration of forbidden patterns MF generates forbidden patterns for Σ MF is given a responsibility zone, and ensure no forbidden pattern appear in it each time a forbidden pattern is produced, MF checks it does not appear: Responsability zone of MF z }| a0 a1 f0 f1 f0 a2 f2 f1 f0 ... { ... ... ... aN ... f2 f1 ... f2 ... MF asks MSearch for ak (gives the adress k and waits for the answer) N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 23 / 26 Responsibility zone of a machine MF Required: responsability zones ⇒ the entire conguration is scanned Responsibility zones must overlap: . . . x−2 x−1 x0 ∈ L(Σ) and x0 x1 x2 · · · ∈ L(Σ) does not imply . . . x−2 x−1 x0 x1 x2 · · · ∈ L(Σ) N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 24 / 26 Level 4: Scan of the entire responsibility zone MF calls for MSearch to acceed its responsibility zone MSearch of level n needs the help of MSearch of level n − 1 N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 25 / 26 Level 4: Scan of the entire responsibility zone MF calls for MSearch to acceed its responsibility zone MSearch of level n needs the help of MSearch of level n − 1 MSearch shares its calculation time: I answer to I help the higher level MF N. Aubrun and M. Sablik () (with the help of MSearch of lower levels) MSearch How to obtain a RE subshift ? October 22, 2009 25 / 26 Outline 1 Subshifts and tilings Denitions Four classes of operations on subshifts 2 The main result A simulation result Sketch of the proof 3 Computation zones for Turing machines Adding Turing machine calculations in computation zones 4 Turing machines calculations The machines MF and MSearch 5 The nal construction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 25 / 26 The nal construction condition Request : MF asks MSearch for a letter in its responsibility zone and waits for the answer condition Communication : internal communication between the MSearch machines of dierent levels Tnal = φFT Request, Communication, φP TMF ,zones, TM zones Search , To obtain Σ : F operation to only keep letters from AΣ SA operation to project on the horizontal direction N. Aubrun and M. Sablik () How to obtain a RE subshift ? October 22, 2009 26 / 26

© Copyright 2018