Message Boards

GROUPS:

Staff Picks Wolfram Science Computer Science Computational Systems Graphics and Visualization Wolfram Language Wolfram Summer School

Alejandro Puga

[WSS21] The 2-state cellular automaton with non-adjacent parent cells

Alejandro Puga, Universidad Autónoma de Zacatecas

Posted 3 months ago

906 Views

2 Replies

3 Total Likes

Follow this post

The 2-state cellular automaton with non-adjacent parent cells
by Alejandro Puga-Candelas

Introduction

In 1901 the brilliant mathematician David Hilbert at Sorbonne posed the following question: can we construct an automated procedure to find/prove all the theorems of a mathematical theory? e. g. Arithmetic, Calculus, Set Theory, etc. Hilbert believed that such a procedure could be found. To Hilbert’s surprise, Kurt Gödel and Alan Turing proved that it was not possible. The amazing way in which Alan Turing found the proof that such a procedure was not possible brought the new era of digital computing and the birth of computer science.
Alan Turing created a machine, which now bears his name, to prove the impossibility of what Hilbert was proposing. The Turing Machine, (TM), is an automaton with 5-tuples (5 distinguishable elements) of which a Tape (memory), a Head that can read/write and a set of States (operations) stand out. The Turing Machine is deterministic automaton and its power rested with the Tape.
However, one might think that using the Turing Machine we can know when a problem is computable, that is, if the TM that can solve this problem. The reality is that we cannot know it since we cannot know for sure if a TM will reach the Halt state and stop. This is known as the Halting problem.
The Halting Problem is the Principle of indeterminacy of computer science; you can’t tell when an automated procedure is going to halt. The Busy Beaver, (BB), problem uses the TM as an automated procedure and is said to be an uncomputable problem for the aforementioned reason. The BB consists of finding the TM of a given size that takes the longest computational time to halt.
In this project we will use an unconventional Cellular Automaton (CA) as an automated procedure. That is, a 2-state CA with non-adjacent parent cells and estimate the Computational Universe by finding both the rules and the effects of initial conditions that lead to the Busy Beaver for these CAs. The CA model is equivalent to the TM model. The results of this project can be of great help since there is a conjecture that proposes that BB as candidates to be Turing Universality.

What is novel about it?

◼

The Busy Beaver for a CAs is not define.

◼

It’s clear for a TM.

◼

For a CA

A particular Initial Condition

A particular Code Rule

The Halt State is the x-space with all cells white (0´s)

The Busy Beaver is the CA Rule Code that takes the longest t-step to find the Halt State.

◼

Unconventional CAs

◼

A CAs with non-adjacent parent cells

What?

The figures shown below were taken from the page 69 of the book A New Kind of Science by Stephen Wolfram. The figure shows a totalistic three colors cellular automaton. A totalistic cellular automata, (TCA), in which the rules depend on the average of the values of the cells in a neighborhood. The left TCA reach the halt state, while the others never do or so it seems. What determines this behavior? Does it depend on the code rule? The initial condition? about what?

In[]:=

Grid[{{ArrayPlot[CellularAutomaton[{357,{3,1}},{{1},0},250]],ArrayPlot[CellularAutomaton[{600,{3,1}},{{1},0},250]],ArrayPlot[CellularAutomaton[{1599,{3,1}},{{1},0},250]],ArrayPlot[CellularAutomaton[{2058,{3,1}},{{1},0},250]]}}]

General and Particular Goals

To answer the questions in the previous paragraph, the project will have the following goals .

◼

General

◼

To identify the Busy Beaver for an specific CA

◼

To measure algorithmic information content and complexity

◼

Particular

◼

To Determine the appropriate range r for the CAs

◼

The range r goes form 1,2,3, up to 4

◼

To determine the appropriate gaps for those Unconventional CAs

◼

Gaps = To skip first, second, third, etc. neighbour

◼

The Gaps will increase the multiplicity

◼

To determine a specific initial condition pattern

◼

To determine a particular neighbor patterns (range plus gaps) to study

Particular

For the regular TCA, without gaps, we have the following states and rules :

The appropriate range r

Out[]=

Neighbors	1	2	3	4	5	6	7
Number of States	2	3	4	5	6	7	8
Number of TCAs	4	8	16	32	64	128	256

What is an Unconventional TCA and the Preliminary Tests

The Code Rules that govern the regular TCAs are affected by gapping between neighboring cells . In the next part we will take an example to clarify the concept of TCA.

TCA Code Rule 20, k-2 , r-1 ,

In[]:=

GraphicsGrid[{{RulePlot[CellularAutomaton[{20,2,1}]],Grid[{{"Gap One",rulePlot[CellularAutomaton[{20,2,{{-1},{0},{2}}}]]},{"Gap Two",rulePlot[CellularAutomaton[{20,2,{{-1},{0},{3}}}]]}},AlignmentLeft]}},ImageSizeFull]

Out[]=

Is that all?

The skipping can be to the left of the center cell too

In[]:=

GraphicsGrid[{{RulePlot[CellularAutomaton[{20,2,1}]],Grid[{{"Gap One Left",rulePlot[CellularAutomaton[{20,2,{{-2},{0},{1}}}]]},{"Gap Two Left",rulePlot[CellularAutomaton[{20,2,{{-3},{0},{1}}}]]}},AlignmentLeft]}},ImageSizeFull]

Out[]=

Is it really all?

No! The skipping can be to the left and to the right of the center cell

In[]:=

Grid[{{"Gap One Left One Right",rulePlot[CellularAutomaton[{20,2,{{-2},{0},{2}}}]]},{"Gap Two Left One Right",rulePlot[CellularAutomaton[{20,2,{{-3},{0},{2}}}]]},{"Gap One Left Two Right",rulePlot[CellularAutomaton[{20,2,{{-2},{0},{3}}}]]}},AlignmentLeft]

The Zero Test

Computational Universe of a TCA of 2-k, r-2

For this case there are 64 rules, so I' m able to map all of them . It' s important to mention that de Busy Beaver will depend on both, the code rule and the initial condition . Thai is, a different code rule or a different initial condition will give different Busy Beaver .

In[]:=

GraphicsGrid[Partition[Table[RulePlot[CellularAutomaton[{i,{2,1},2}],PlotLegends"Text"],{i,0,63}],8],ImageSize{785,469},AspectRatioFull]

The Code Rule 20

In[]:=

RulePlot[CellularAutomaton[{20,{2,1},2}],PlotLegends"Text"]

Initial Condition

Out[]=

In[]:=

tca20=CellularAutomaton[{20,{2,1},2},{{1,0,1},0},{10,{-15,15}}];ArrayPlot@tca20

Out[]=

The following image shows the evolution of the TCAs according to the width considered. That is, we vary the width to see the dynamics of the BBs that appear with it and compared with the All the option at the end.

The following image shows the history of each of the TCA rule that reached the Halt state a

Out[]=

2	2	2	2	2
15	31	63	511	∞
5	5	5	5	5
18	80	144	1040	∞
2	2	2	2	2
13	∞	∞	∞	∞
18	66	130	1026	∞
9	33	65	513	∞
2	2	2	2	2
148	∞	∞	∞	∞
5	5	5	5	5
178	∞	∞	∞	∞
2	2	2	2	2
729	∞	∞	∞	∞
105	∞	∞	∞	∞
9	33	65	513	∞
2	2	2	2	2
5	5	5	5	5
2	2	2	2	2
379	∞	∞	∞	∞
2	2	2	2	2
184	∞	∞	∞	∞
5	5	5	5	5
2	2	2	2	2

The Complexity Measure

The measurement of complexity has always been a real challenge in the world of science . Knowing how random an object is, being the object a way of abstracting a part of the universe - a system -, has given rise to great revolutions . For example, the revolution of matter that allowed human beings to be sedentary and form societies, develop agriculture and livestock . The industrial revolution with the avenue of Thermodynamics and the informatics revolution that we are experiencing until now.
There are several ways to measure complexity. What interests us is to be able to measure the complexity of both the initial conditions, the code rules and especially the BB obtained from the simulations.
In what follows, the calculation of the complexity of a regular TCAs (without gaps) that shows a behavior like a BB is presented.

The example of the code 20

In[]:=

ArrayPlot@tca20

Out[]=

In[]:=

shape=SequenceCases[#,{1,Longest[___],1}|{1}]&/@tca20

Out[]=

{{{1,0,1}},{{1,1,1}},{{1,0,0,0,1}},{{1}},{},{},{},{},{},{},{}}

In[]:=

MatrixForm@%

Out[]//MatrixForm=

{}

Ratio

In[]:=

info=shape//Flatten//Tally

Out[]=

{{1,8},{0,4}}

In[]:=

Divide@@Last/@ReverseSort[info]//N

Out[]=

Algorithmic Information vs Shannon Entropy

In[]:=

string=shape//Flatten//FromDigits//ToString

Out[]=

101111100011

In[]:=

StringLength[%]

Out[]=

In order to get the estimation of the Algorithmic Complexity

Algorithmic Calculator

Out[]=

	algorithmic complexity estimation	Shannon Entropy
string	32.3093113009744002 bits	0.9183 bit(s)

In[]:=

Entropy[2,string]//N

Out[]=

0.918296

Other types of measurements?

◼

Compress?

Compress/*ByteCount

Testing for Different Numbers of Neighbors

First Test: Two Neighbours

In this section we analyze the case of two neighbors and all their possible configurations

2-k, 16 Code Rules (0, ..., 15), 1 Neighbours, 8 Initial Conditions,

In[]:=

ini=Tuples[{{{1},{1,1},{1,1,1},{1,0,1},{1,1,1,1},{1,0,1,1},{1,1,0,1},{1,0,0,1}},{0}}];neighbours={{{-1},{1}}};tca2=CellularAutomaton[{#1,2,neighbours[[#2]]},ini[[#3]],{1000,All}]&;haltLength2[history:{__List}]:=Position[history,{(0)..},{1}]//Map[First]//SequenceCases[#,{i_,j_}/;i==j-1]&//Replace[#,{{}->0,l:{{_,_}..}:>l〚1,1〛}]&;iniPlot[{bits:{(0|1)..},0}]:=ArrayPlot[{bits},ImageSize12Length[bits],MeshTrue];

In[]:=

ini

Out[]=

{{{1},0},{{1,1},0},{{1,1,1},0},{{1,0,1},0},{{1,1,1,1},0},{{1,0,1,1},0},{{1,1,0,1},0},{{1,0,0,1},0}}

Only one Code Rule

In[]:=

ArrayPlot[tca2[12,1,6]]

Out[]=

Each Code Rule with all Initial Conditions

In[]:=

rulePlot[CellularAutomaton[{3,2,neighbours[[1]]}]]

Out[]=

In[]:=

Manipulate[Column[{rulePlot[CellularAutomaton[{code,2,neighbours[[1]]}]],Grid@Partition[Table[Column[{iniPlot[ini[[i]]],ArrayPlot[tca2[code,1,i]]},Center],{i,Length[ini]}],4]},Center],{code,Range[0,15]}]

Out[]=

In[]:=

iniPlot/@ini

Out[]=

{

}

Computational Universe

Neighbours 1, Initial Condition 1,

In[]:=

t=ParallelMap[haltLength2,Table[tca2[i,1,1],{i,0,15}]]

Out[]=

{2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0}

In[]:=

uno=Labeled[ArrayPlot[Partition[t,4],ColorRules{Max[t]->Red},PlotLegendsPlaced[Automatic,Below]],iniPlot[ini[[1]]],Top]

Out[]=

Neighbours 2, Initial Condition 1

In[]:=

t21=ParallelMap[haltLength2,Table[tca2[i,1,2],{i,0,15}]]

Out[]=

{2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0}

In[]:=

dos=Labeled[ArrayPlot[Partition[t21,4],ColorRules{Max[t21]->Red},PlotLegendsPlaced[Automatic,Below]],iniPlot[ini[[2]]],Top]

Out[]=

In[]:=

alltca2=Labeled[ArrayPlot[Partition[todastca2[[#]],4],ColorRules{Max[todastca2[[#]]]->Red},PlotLegendsPlaced[Automatic,Below]],iniPlot[ini[[#]]],Top]&;

In[]:=

todas[[1]]

Out[]=

{2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0}

Grid[Partition[Table[alltca2[i],{i,Length[ini]}],4],FrameTrue]

Second Test: Three Neighbours

In[]:=

Clear[ini,neighbours]

2-k, 256 Code Rules (0, ..., 255), 5 Neighbours, 8 Initial Conditions, 1000 t-Steps

In[]:=

ini=Tuples[{{{1},{1,1},{1,1,1},{1,0,1},{1,1,1,1},{1,0,1,1},{1,1,0,1},{1,0,0,1}},{0}}];neighbours={{{-1},{0},{1}},{{-2},{1},{2}},{{-2},{0},{2}},{{-2},{-1},{2}},{{-3},{0},{3}}};tca3=CellularAutomaton[{#1,2,neighbours[[#2]]},ini[[#3]],{1000,All}]&;haltLength2[history:{__List}]:=Position[history,{(0)..},{1}]//Map[First]//SequenceCases[#,{i_,j_}/;i==j-1]&//Replace[#,{{}->0,l:{{_,_}..}:>l〚1,1〛}]&;iniPlot[{bits:{(0|1)..},0}]:=ArrayPlot[{bits},ImageSize12Length[bits],MeshTrue];

Only one Code Rule

In[]:=

Manipulate[ArrayPlot[tca3[20,ne,ic]],{{ne,1,"Neighbours"},Range[Length[neighbours]]},{{ic,2,"Initial Condition"},Range[Length[ini]]},FrameLabelStyle["Three Neighbours",Small],LabelStyleBlack]

Out[]=

In[]:=

Manipulate[Column[{rulePlot[CellularAutomaton[{code,2,neighbours[[ne]]}]],Grid@Partition[Table[Column[{iniPlot[ini[[i]]],ArrayPlot[tca3[code,1,i]]},Center],{i,Length[ini]}],4]},Center],{code,Range[0,255]},{{ne,1,"Neighbours"},Range[Length[neighbours]]},FrameLabelStyle["Three Neighbours",Small],LabelStyleBlack]

Out[]=

Computational Universe

In[]:=

generateData3[n_]:=Module[{data},data=ParallelMap[haltLength2,Table[tca3[i,n,#],{i,0,255}]]&/@Range[8];Export[FileNameJoin[{NotebookDirectory[],StringJoin["data3-",ToString[n],".mx"]}],data];data]

The following cell takes a long time to evaluate, but it’s shown here to indicate how the data were generated. The cell after the next one has the iconized version of the data.

Table[generateData3[n],{n,Length[neighbours]}];t3=Table[Import[StringJoin["data3-",ToString[n],".mx"]],{n,Length[neighbours]}];

In[]:=

t3=

data3-1

data3-2

data3-3

data3-4

data3-5

;

In[]:=

alltca3s=Labeled[ArrayPlot[Partition[#1[[#2]],16],ColorRules{Max[#1[[#2]]]->Red},PlotLegendsPlaced[Automatic,Below]],iniPlot[ini[[#2]]],Top]&;

In[]:=

comuniv3=Table[Grid[Partition[Table[alltca3s[t3[[j]],i],{i,Length[ini]}],4],FrameTrue],{j,Length[neighbours]}];

In[]:=

Manipulate[Column[{neighbours[[i]]//ToString,comuniv3[[i]]},Center],{{i,1,"Neighbours number"},Range[Length[neighbours]]},FrameLabelStyle["Three Neighbours Computational Universe ",Small],LabelStyleBlack]

Out[]=

Third Test : Four Neighbours

In[]:=

Clear[ini,neighbours]

2-k, 1024 Code Rules (0, ..., 1023), 13 Neighbours, 8 Initial Conditions, 1000 t-Steps

In[]:=

ini=Tuples[{{{1},{1,1},{1,1,1},{1,0,1},{1,1,1,1},{1,0,1,1},{1,1,0,1},{1,0,0,1}},{0}}];neighbours={{{-2},{0},{1},{2}},{{-2},{-1},{1},{2}},{{-2},{-1},{0},{2}},{{-3},{0},{2},{3}},{{-3},{0},{1},{3}},{{-3},{-1},{2},{3}},{{-3},{-1},{1},{3}},{{-3},{-1},{0},{3}},{{-3},{-2},{1},{3}},{{-3},{-2},{0},{3}},{{-4},{-1},{2},{4}},{{-4},{-1},{1},{4}},{{-4},{-2},{1},{4}}};tca4=CellularAutomaton[{#1,2,neighbours[[#2]]},ini[[#3]],{1000,All}]&;haltLength2[history:{__List}]:=Position[history,{(0)..},{1}]//Map[First]//SequenceCases[#,{i_,j_}/;i==j-1]&//Replace[#,{{}->0,l:{{_,_}..}:>l〚1,1〛}]&;iniPlot[{bits:{(0|1)..},0}]:=ArrayPlot[{bits},ImageSize12Length[bits],MeshTrue];

In[]:=

Length[neighbours]

Out[]=

Only one Code Rule

In[]:=

Manipulate[ArrayPlot[tca4[150,ne,ic]],{{ne,1,"Neighbours"},Range[Length[neighbours]]},{{ic,2,"Initial Condition"},Range[Length[ini]]},FrameLabelStyle["Four Neighbours",Small],LabelStyleBlack]

Out[]=

In[]:=

Manipulate[Column[{rulePlot[CellularAutomaton[{code,2,neighbours[[ne]]}]],Grid@Partition[Table[Column[{iniPlot[ini[[i]]],ArrayPlot[tca4[code,1,i]]},Center],{i,Length[ini]}],4]},Center],{code,Range[0,1023]},{{ne,1,"Neighbours"},Range[Length[neighbours]]},FrameLabelStyle["Four Neighbours",Small],LabelStyleBlack]

Out[]=

Computational Universe

In[]:=

generateData[n_]:=Module[{data},data=ParallelMap[haltLength2,Table[tca4[i,n,#],{i,0,1023}]]&/@Range[8];Export[FileNameJoin[{NotebookDirectory[],StringJoin["data-",ToString[n],".mx"]}],data];data]

The following cell takes a long time to evaluate, but it’s shown here to indicate how the data were generated. The cell after the next one has the iconized version of the data.

Table[generateData[n],{n,1,Length[neighbours]}];t4=Table[Import[StringJoin["data-",ToString[n],".mx"]],{n,Length[neighbours]}];

Table[Iconize[Import[StringJoin["data-",ToString[n],".mx"]],StringJoin["data-",ToString[n]]],{n,Length[neighbours]}]

In[]:=

t4=

data-1

data-2

data-3

data-4

data-5

data-6

data-7

data-8

data-9

data-10

data-11

data-12

data-13

;

In[]:=

alltca4s=Labeled[ArrayPlot[Partition[#1[[#2]],32],ColorRules{Max[#1[[#2]]]->Red},PlotLegendsPlaced[Automatic,Below]],iniPlot[ini[[#2]]],Top]&;

In[]:=

comuniv4=Table[Grid[Partition[Table[alltca4s[t4[[j]],i],{i,Length[ini]}],4],FrameTrue],{j,Length[neighbours]}];

In[]:=

Manipulate[Column[{neighbours[[i]]//ToString,comuniv4[[i]]},Center],{{i,1,"Neighbours number"},Range[Length[neighbours]]},FrameLabelStyle["Four Neighbours Computational Universe",Small],LabelStyleBlack]

Out[]=

Conclusions

The results obtained for the case of three, four and five neighbors with a small number of gaps have shown a very similar trend . That is, the effect of including gaps between cells sometimes leads to very short BBs; maximum of 5 steps in the t - step . Although it should be noted that the shape that certain unconventional TCAs acquire is qualitatively very different from regular TCAs, but without affecting their length in the t - step . To investigate the quantitative effect we would have to associate an unconventional TCA to a particular phenomenon, but that is outside the objective of the project . To investigate whether or not BBs of greater length are possible, a wider range of initial conditions should be examined as well as more gaps in the rule . it is also necessary to establish a computationally viable procedure due to the large amount of data and computational time that this task would have .

The next steps

The importance of the Zero Test section lies not only in testing the structure of the codes but also in testing the hypothesis that the TMs that stop make it proto and those that do not show that tendency soon . That is what we observed in that section and in the other section tests with two, three, and four neighbors.
To be clearer and to further emphasize the importance of the Zero Test section, the tests that will come with more neighbors (five, six, and more) will be the most representatives. That is, we expect behaviors with larger BBs and with greater measures of complexity as well. This challenge is not easy because there are too many cases to investigate and the combination among the initial conditions, the code rules, and the different arrangements of the number of neighbors increases the multiplicity enormously. So, if one could discriminate cases where trends indicate that they are not candidates for BBs among all the enormous number of possibilities would facilitate the calculations enormously.

Initialization

A function called rulePlot was designed by my mentor Bob Nachbar to be used with the bulit-In function CellularAutomaton

Code


POSTED BY: Alejandro Puga

Answer

2 Replies

Sort By:

Moderation Team

Moderation Team, WOLFRAM

Posted 2 months ago

-- you have earned *Featured Contributor Badge* Your exceptional post has been selected for our editorial column *Staff Picks* http://wolfr.am/StaffPicks and Your Profile is now distinguished by a *Featured Contributor Badge* and is displayed on the Featured Contributor Board. Thank you!

POSTED BY: Moderation Team

Answer

[WSS21] The 2-state cellular automaton with non-adjacent parent cells

What is novel about it?

What?

General and Particular Goals

Particular

The appropriate range r

TCA Code Rule 20, k-2 , r-1 ,

Is that all?

Is it really all?

The Zero Test

Computational Universe of a TCA of 2-k, r-2

Initial Condition

The Complexity Measure

Ratio

Algorithmic Information vs Shannon Entropy

Other types of measurements?

First Test: Two Neighbours

2-k, 16 Code Rules (0, ..., 15), 1 Neighbours, 8 Initial Conditions,

Only one Code Rule

Each Code Rule with all Initial Conditions

Computational Universe

Neighbours 1, Initial Condition 1,

Neighbours 2, Initial Condition 1

Second Test: Three Neighbours

2-k, 256 Code Rules (0, ..., 255), 5 Neighbours, 8 Initial Conditions, 1000 t-Steps

Only one Code Rule

Computational Universe

Third Test : Four Neighbours

2-k, 1024 Code Rules (0, ..., 1023), 13 Neighbours, 8 Initial Conditions, 1000 t-Steps

Only one Code Rule

Computational Universe

Code

Code
