WOLFRAM NOTEBOOK

Multi-way Tiling Systems

Farhan Tanvir Chowdhury
The University of Sheffield
We aim to formulate a framework for exploring the multiway evolution of tiling systems. Tiling systems have a key relation to Turing Machines since any given Turing can be encoded as a Tiling problem. While deterministic evolution of such tilings have been widely studied, non-deterministic evolution has so far not been considered widely. But within the context of Multi-way systems in the framework of the Wolfram Fundamental Physics project, the non-deterministic evolution of tiling systems becomes a natural phenomena to consider , and that is what we aim to explore in this project.

Project Background

A Turing Machine is a fairly basic model, describing an abstract machine which manipulates symbols on a two way (conventionally right and left) infinite strip of tape according to a given table of rules. But essentially all of modern Computer Science boils down to this model of computation, as a Turing machine capable of simulating the logic of any given computer algorithm can be constructed in principle. In the 1960s logician Hao Wang showed that any given Turing Machine could be encoded into a tiling completion problem (Wang 1961). This means that a set of tiles and a seed configuration could be constructed, such that the infinite Euclidean plane could be tiled completely (with no overlaps) if and only if the run of the encoded Turing Machine never halts. ​​
​We show above a schematic (Goodman-Strauss 2016) of Wang’s encoding. Simple cases of deterministic Turing Machines, and tiling patterns generated from simple rules, were extensively visualised and studied in Stephen Wolfram’s A New Kind of Science. Recently non-deterministic Turing Machines have also gained particular attention, appearing as Multi-way Turing Machines within the Multi-way systems framework of the Wolfram Fundamental Physics project. This leads naturally to considering the nature of possible Multi-way “Tiling” Systems within the Wolfram Language.

Generating Multiway Tiling Systems

We start with defining tiling constraints for square tilings of two colours (black and white), with light-gray representing “blank” cells or empty tiles. For examples, a sample of five tilings generated from a given constraint is shown below:
In[]:=
rules=RandomSample[generateConstraints[{{0,2,0},{3,1,5},{0,4,0}}],5]
Out[]=
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
In[]:=
ArrayPlot[#,Mesh->True]&/@rules
Out[]=
,
,
,
,
We require an indexArray function to index the tiling space so that we can use a backtracking algorithm to determine whether the constraint or the given set of constraints match the given rules. The initial size of the tiling has to be compatible with the number of computational steps. The ordering produced by indexArray means that the tiling will grow from the center in an anti-clockwise spiral, with already “filled” cells being skipped over.
​
We generate two possible initial conditions:
In[]:=
init=AssociationThread[indexArray[5],Join[{Black},Table[LightGray,Length[indexArray[5]]-1]]]
Out[]=
{3,3}
,{2,3}
,{2,2}
,{3,2}
,{4,2}
,{4,3}
,{4,4}
,{3,4}
,{2,4}
,{1,4}
,{1,3}
,{1,2}
,{1,1}
,{2,1}
,{3,1}
,{4,1}
,{5,1}
,{5,2}
,{5,3}
,{5,4}
,{5,5}
,{4,5}
,{3,5}
,{2,5}
,{1,5}
The initial condition above is a 5×5 initial tile with a black tile in the centre, while below we have an 7×7 initial tile with a random combination of filled-in black and white tiles.
In[]:=
init2=AssociationThread[indexArray[7],RandomChoice[{0.4,0.3,0.3}->{LightGray,Black,White},Length[indexArray[7]]]]
Out[]=
{4,4}
,{3,4}
,{3,3}
,{4,3}
,{5,3}
,{5,4}
,{5,5}
,{4,5}
,{3,5}
,{2,5}
,{2,4}
,{2,3}
,{2,2}
,{3,2}
,{4,2}
,{5,2}
,{6,2}
,{6,3}
,{6,4}
,{6,5}
,{6,6}
,{5,6}
,{4,6}
,{3,6}
,{2,6}
,{1,6}
,{1,5}
,{1,4}
,{1,3}
,{1,2}
,{1,1}
,{2,1}
,{3,1}
,{4,1}
,{5,1}
,{6,1}
,{7,1}
,{7,2}
,{7,3}
,{7,4}
,{7,5}
,{7,6}
,{7,7}
,{6,7}
,{5,7}
,{4,7}
,{3,7}
,{2,7}
,{1,7}
The ingredients we need to generate non-deterministic evolution are a state evolution function, a state event function, and an event application function. The first gives a list of all possible successors to a state. The second takes the list of events applicable to a state; generate the states, backtracks by checking against constraints, and returns a list of possible color changes. The third applies an event to a given state. Unlike other multiway systems, an event decomposition function is not necessary since subsequent tilings do not involve “destroyer” events, only creation ones. With these, we can now generate multi-way evolution of the above initial conditions with the given rules to get:
In[]:=
generateMultiwayTiling[rules,init,6]
Out[]=
The above evolves the first initial condition for six time steps, while below evolves the second initial condition for four time steps.
In[]:=
generateMultiwayTiling[rules,init2,4]
Out[]=
To see how the tilings evolve in detail, we can use a state rendering function to generate graphics showing the tilings evolve:
In[]:=
Graph[generateMultiwayTiling[rules,init,6],VertexShapeFunction->getStateRenderingFunction[],PerformanceGoal"Quality",VertexSize->1.5,GraphLayout"LayeredDigraphEmbedding"]
Out[]=

Concluding Remarks and Future Directions

The multi-way system shows possible transitions between states. Starting with a set of rules, we traverse the space of all possible attainable states (i.e of abstract rewrites), as the rules evolve for a greater number of steps. In our set up, the vertices of the multi-way graph represents possible tilings and a path through the graphs represents tiling sequences. The system terminating represents tilings that get stuck (i.e tilings which cannot continue to further tile the plane without gaps and/or overlaps).
​
It wasn’t readily clear to us in our investigation how we could translate between simple Turing Machine rules and simple tiling constraints. So our preliminary analysis leaves room for many extensions. One could make the connection to Turing Machines with an explicit Turing machine encoding. Once that is achieved, there could be the scope of re-interpreting the multiway evolution as that of a “quantum” Turing Machine, where the “nondeterministic states” are identified as quantum states, assigned quantum amplitudes, and collections of multiple states viewed as being in a quantum superpositions are considered.
​
Another key extension is to study which tilings eventually get stuck, which would require a finiteness tracking function. Then, we would evolve different combinations of initial conditions/rule sets via the multi-way system, in order to try to find branches of the multiway graph that do not halt. One could also consider reformulating the system to consider a possible connection to the non-deterministic evolution of 2D Turing Machines instead, where the Turing Machine can move around on a two dimensional grid instead of a 1D tape.

Keywords

◼
  • Tilings
    • ◼
  • Turing Machines
    • ◼
  • The Halting Problem

    • Acknowledgment

    Thank you firstly to Mano Namuduri, without whose help and expertise with the Wolfram language I couldn’t have gone very far in exploring the ideas in this project. Thank you to WSS 2021 for this opportunity, and to Stephen Wolfram for his invaluable input in helping define the project within the “Fundamental Physics” track. Lastly, but not the least, I would like to give a special thanks to my personal tutor Sam Dolan at the University of Sheffield, whose enthusiasm and encouragement with further exploring Mathematica as a research tool was a key driver for me to participate in this school.

    References

    ◼
  • Hao Wang. Proving theorems by pattern recognition — ii. Bell System Technical Journal, 40(1):1–41, Jan 1961.
    • ◼
  • Chaim Goodman-Strauss. Tessellations. arXiv e-prints, page arXiv:1606.04459, June 2016.

    • Code

    Wolfram Cloud

    You are using a browser not supported by the Wolfram Cloud

    Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


    I understand and wish to continue anyway »

    You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.