A New Kind of Science: The NKS Forum > Pure NKS > Revised T5 = ({0, +1, x, y, -1}; +, -; 0, +1, -1) Part 1: Foundations
Author
 Thread
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Revised T5 = ({0, +1, x, y, -1}; +, -; 0, +1, -1) Part 1: Foundations

Rather than a lengthy series of posts, this presentation offers most of the information in a revised version of an earlier notebook. The notebook and several figures are attached in posts immediately following this one.

The notebook corrects errors and includes material presenting reasons that explain why the members of T5 in x and y properly belong to the set. Although the members of T5 in x and y are generated by a necessary and sufficient process, it is still helpful to consider reasons why the members logically belong together and how they are related among one another. In fact it contributes to the appreciation of the workings of the necessary and sufficient process.

This notebook, then, has to do with the foundations of T5 in x and y. Subsequently, there will be three more notebooks that each take up a third of the rules, exploring what happens when sets of cellular automata are allowed to run their course. We refer to the members of these sets as phases, purposefully using vocabulary reserved for quantum applications. However, it is not that this discussion is intended to explain quantum behavior so much as it is to point out mechanisms common to both quantum applications and the subject under consideration.

So, to begin, here is a repetition of the general description of T5 in x and y presented previously.

Figure 1, also in the Subsubsection Print Tables in the notebook, lists a set of 27 three color rules that correspond to algebraic expressions for a ternary logic in two variables:

T5 = ({0, +1, x, y, -1}; +, -; 0, +1, -1)

where the operations, + and -, are modulo 3 sum and difference and
where the three identities are,

0: additive identity
+1: positive multiplicative identity and
-1: negative multiplicative identity.

T5 is a closed set. It is an example of a nondegenerate, complemented, distributive lattice.

We use the map function to carry out the operations in T5.
Of course, the map function results in rule numbers, not algebraic expressions.

However, there is a correspondence. It is found between the rule number result and the position it holds in the list of algebraic expressions.

This set of 27 rules is auto-generated using a seed and iterating the map function on that seed until the result no longer changes.

We establish that each member of T5 can be expressed using Mathematica functions for modulo 3 sum and difference, and set up algebraic expressions for each of the rules dictated by the modulo 3 sum and difference functions. (See Figure 1.)

After that, we group the 27 rules according to the principles of complementation and identity, describing the appropriateness of the symbolic names given to each rule. This is presented in great detail in the notebook.

Once this grouping has been done, we derive the rules using the map function. This involves showing how each rule is related to its algebraic expression using the map function. The motivation for this is to show how the map function results agree with results obtained earlier using Mathematica's modulo 3 sum and difference functions.

Next we take up rotations by multiples of 90 degrees. Although this is not directly related to cellular automata, it is included to show how the rules can be grouped into families of four members, where each member is the same, but seen from a different orientation.

For this subject we have designated colors to represent the 27 rule numbers. The color legend includes color, rule position in the list of 27 rules, rule number, and algebraic expression. This is an improvement over the former way the color legend was presented, in that it gives complete information about each rule. (See Figure 2.)

“Rotations” is a departure from how the rules were presented in the posts that this notebook corrects. From the figures it can be seen how the 12 rules representing forms of the variables naturally group themselves into three families, each having four members. (See Figure 3.)

Similarly, the operations form a set with twelve rules grouped into three families of four members. The figures for the operations are striking in that their diagonal structures contribute to the formation of three diamond-shaped objects. (See Figure 4.)

This presentation is accomplished by means of cross product projection graphs And, again, it employs the map function. The versatility of the map function really shows itself in these rotations. Close attention to the patterns of rules that fill the operands helps one appreciate one more aspect of the scope of the map function.

Moreover, the distinction between cross product projection action on cells from that of cellular automata is brought out.

It is emphasized that the different mechanisms of cross product projections and cellular automata have two things in common: both are rooted in the map function and both involve a rule.

Surprisingly, a set of just three rules controls rotations of all cross product projections, whether variables or operators, and these three rules are related through the principle of complementation.

The rotation rules are:
(4) 146064945221: (-1 + y)
(21) 387410647: (1 + y)
(17) 3943753520967: (y)

The principle of complementation manifest in each is:
(17) Uncomplemented version.
(21) Complement of (–y) with respect to positive identity.
(4) Complement of (–y) with respect to negative identity.

This raises the question as to what purpose, if any, other sets of three rules involving complementation serve. For instance, the same set as above but for (x).

In addition, the three phases of cellular automata (19) 7348211845533: (x + y) are executed in the traditional manner, and then in a way that operates on rule numbers rather than digits. Comparable output for these two methods is presented in figure 5. It should be noted that some features are visible in both types of output. For instance, in both there are three phases that cycle, and the rows of zeros is in the same coordinate locations phase for phase.

Finally, we introduce a strange use of the map function that acts on each cell of the output of a cellular automaton to change its value. For want of a better name we call these actions on the individual cells "flips". The purpose of introducing flips is not just to demonstrate some kind of trickery. It is to serve as a tool for full, as well as partial, translation of cellular automata output.

As an example the rule for (19) 7348211845533: (x + y) in its three phases is presented along with the three types of flips: alpha, beta, and gamma. (See Figure 6.)

The discussion on flips is expanded upon compared to earlier posts. The discussion introduces three sets of three rules, each occurring in the neighborhood of one of the identities. These nine rules flip in 27 distinct ways. (See Figure 7.)

One third of them travel flip paths that include only the identities. Two-thirds of them travel paths involving three forms of OR and three forms of NOR. The two sets of paths are disparate. Their graphs are found in figures 8a and 8b.

A final word is said regarding incoherent versus coherent flips. When all cells of the cellular automaton are given the same type of flip, the flip is said to be coherent. When each cell is given a randomly chosen flip type, the flip is said to be incoherent. It is noted that coherent flips preserve polar opposites, where opposites are defined in terms of complementation. In contrast, random or incoherent flips do not preserve polarity.

This completes the agenda for this notebook. As stated above, there will be three more notebooks, each covering a third of the rules in T5. These notebooks will focus on phase sets of cellular automata and some of their properties.

Map Function in Plain English

Understanding the code of the map function may be confusing to some.
So here is an explanation of it in non-programming terms.

There are four inputs to the map function. All are rule numbers.
The first input is called the operator. Think of this rule as a function.
The other three inputs are called operands. Think of these rules as inputs to the function.

Each of these four inputs undergoes digit expansion, which means the rule numbers are changed from base 10 to base 3. And these base 3 numbers are expressed as lists of base 3 digits. Additionally, the operator digit list is reversed so that it is in an order ready for indexing according to place value. This indexing happens later in the process.

Next, the lists representing the three operands are arranged in a matrix with row 1 having the third operand, row 2 the second, and row 3 the first. In other words, they are in reverse order, consistent with place value conventions, which have the lowest digit on the right.

Now to indicate their place values each digit of each column of the matrix is multiplied by a power of 3.

The digits in the first row are multiplied by 3^0.
The digits in the second row are multiplied by 3^1.
The digits in the third row are multiplied by 3^2.

Then each column of digits is added base 10. The result is a list of integers that is used to index the reverse ordered digit expansion of the first input, the operator. But because Mathematica begins indexing with 1 instead of 0, the integers in the list are each short by 1, so that 1 is added to each digit.

Next a new digit expansion of the operator is generated by indexing the reverse ordered digit expansion of the operator. This is the heart of the map function. Everything up to this point has been by way of preparation. What indexing does, is take the first digit of the index list and find the position of its value in the reverse ordered digit expansion list of the operator. That position in the digit expansion list of the operator holds the first digit of the digit expansion list for the result.

This procedure is repeated for each digit in the index list until all the digits in the expansion list for the result have been filled. (Some call this process coefficient indexing.)

Finally, the resulting digit list is converted to a base 10 rule number. This is the integer that is returned as the solution to the map function.

Let's take an example.

As operator we have the rule that finds modulo 3 sum of x and y.
As operand1 we have x.
As operand2 we have y.
As operand3 we have the equivalent of a Null.

operatorEx = 3681670999617; (* rule number for modulo 3 sum of first two operands *)

An observant reader may have recognized that this is the rule for modulo 3 sum (-x – y).

FromDigits[Mod[IntegerDigits[minusx, 3, 27] + IntegerDigits[minusy, 3, 27], 3], 3] = 3681670999617

True

This not an error. Strange though it is, the operator modulo 3 sum is defined in this system of logic in terms that are negative.

The way we handle this in the notebook is to define two types of modulo 3 sum.
One with positive operands and one with negative operands. Then we select the one defined with negative operands for use as the operator for (x + y).

Continuing with the example, here are the entries for the operands.

operand1Ex = 3812992433055; (* rule number for (x) *)
operand2Ex = 3943753520967; (* rule number for (y) *)
operand3Ex = 0 (* rule number for the “don’t care”. This acts as a Null entry. *)

So there are only two operands that the operator “looks” at. It renders the result of the third operand as though it did not exist. Or more exactly, it renders the results as zero. And this is not slight of hand. It is actually the way three valued logic works for this rule number.

These four inputs need to be converted to base 3 digit lists. And the operator needs to have its digits reversed.

operatorExDigitList = Reverse[IntegerDigits[operatorEx, 3, 27]]

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

operand1ExDigitList = IntegerDigits[3812992433055, 3, 27]

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

operand2ExDigitList = IntegerDigits[3943753520967, 3, 27]

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

operand3ExDigitList = IntegerDigits[0, 3, 27]

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

Now, following place value conventions, each digit list for the operands needs to be multiplied by a particular power of 3 depending on its position in the list of operands.

operand3ExDigitList = IntegerDigits[3681670999617, 3, 27] 3^0

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

operand2ExDigitList = IntegerDigits[3943753520967, 3, 27] 3^1

{3,3,3,6,6,6,0,0,0,3,3,3,6,6,6,0,0,0,3,3,3,6,6,6,0,0,0}

operand1ExDigitList = IntegerDigits[3812992433055, 3, 27] 3^2

{9,9,9,9,9,9,9,9,9,18,18,18,18,18,18,18,18,18,0,0,0,0,0,0,0,0,0}

Add up the columns of the three operands base 10.

indexList = operand1ExDigitList + operand2ExDigitList + operand3ExDigitList

{13,13,13,15,15,15,11,11,11,21,21,21,26,26,26,19,19,19,5,5,5,7,7,7,0,0,0}

Increment by 1 to accommodate indexing which does not begin with 0, but with 1. (The head of an expression occupies position 0.)

This gives us a list to index the reversed digits of the operator.

indexList = indexList + 1

{14,14,14,16,16,16,12,12,12,22,22,22,27,27,27,20,20,20,6,6,6,8,8,8,1,1,1}

For convenience, the digits of the operator are listed again here:

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

Here is the operator digit list indexed to form a new list.

operatorExDigitList[[indexList]]

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

You can see how the indexing works. The 14th position in operator is a 2. So since the first three index values are 14, the result starts off with three twos. Then there are three 16s, so the result continues with three zeros, since zero is the value at position 16 of the operator. And so on until all of the digits of the operator have been called out in their order.

But this new list needs to be converted to a rule number.

FromDigits[operatorExDigitList[[indexList]], 3]

7348211845533

This same rule number is returned from the map function.

map[3681670999617, x, y, dontcare]

7348211845533

The third operand was the equivalent of a Null in this example. In other cases it may be have a meaningful value. For example, when adding modulo 3 sum of x, y, and z.

The map function can be modified to take additional variables beyond x, y, and z.

Just push down the stack (matrix of operand digit expansions) with each additional variable and adjust the number of digits required to express them. The number of digits is base^number_of_variables.

It can also be modified to take on additional states other than the three used in this example: {0, 1, 2}. When addition states are introduced, expand the digits and multiply the digit lists for the operands by a base that reflects the number of states.

Concluding Remarks

As mentioned in the above comments, most of the information concerning this post is in the notebook. In the notebook I have tried to incorporate some of the new features from version 6.0.3.0 such as Grid, Manipulate, GraphPlot, and SlideView so as to make the presentation more appealing and flexible.

Also, including an explanation of the map function code that resembles a high-level engineering specification is meant to help those non-programmers who read the Forum posts but do not download the notebooks. It is hoped that this specification will be used by electrical engineers and students to build circuits that do multiple valued logic.

I am fascinated by the way flips work. The GraphPlot of the two divisions of flips on (x + y) are examined in great detail in the notebook. These are presented for your study with SlideView, so you can easily backup to a previous slide and make comparisons.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 08-23-2008 at 03:03 AM

Report this post to a moderator | IP: Logged

08-23-2008 02:32 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 2 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:55 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 3 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:56 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 4 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:57 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 5 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:57 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 6 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:58 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 7 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 02:59 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Figure 8 is attached.

Lawrence J. Thaden has attached this image:

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 03:00 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Notebook is attached.

Attachment: revised t5 in x and y (part1 foundations).nb
This has been downloaded 1272 time(s).

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-23-2008 03:01 AM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Comments on Figures 8a and 8b

More needs to be said about these figures, especially 8b.

Comments in the notebook indicate that the graph of figure 8a needs to be circumnavigated just once to form a cycle, for traversing the last self-loop sends you back to the cellular automaton’s original phase output.

In contrast, one circumnavigation of 8b leaves you upside down and in reverse order with respect to the complete set of rules. That is, instead of being at the output of the original phase with its cell content {0, 1, 2}, you are at the bottom of the list of rules, and in reverse order, with corresponding cell content: {7625597484984, 7625597484985, 7625597484986}.

Then, after a second circumnavigation, you are in the middle of the list with corresponding cell content: {3812798742492, 3812798742493, 3812798742494}, which is neither up nor down.

It is not until the third circumnavigation is completed that you find yourself back to corresponding cell content {0, 1, 2}, which is identical to the original phase output.

So while the identities complete a cycle in a single circumnavigation, it takes three to complete the cycle for the OR and NOR flip paths.

__________________
L. J. Thaden

Report this post to a moderator | IP: Logged

08-25-2008 03:41 PM
Lawrence J. Thaden

Registered: Jan 2004
Posts: 357

Comments on Figure 7

The flip list in figure 7 is organized first by algebraic expression of cell content from the output of the CA’s original phase, {0, NOR, -NOR}; then by type of flip, {alpha, beta, gamma}.

However, since the flips are all either self-loops or bi-directional, this makes for duplication in the list. For example, (2) NOR alpha flips to OR and (20) OR alpha flips to NOR are actually the same flip, just in a different direction. The commutative property holds for flips.

Actually, if such duplicates were removed, the flip list would consist of these members, where duplicates are shown on the right.

ALPHA FLIPS:

(1) 0 alpha flips to –1 ..................(21) –1 alpha flips to 0
(2) NOR alpha flips to OR .............(20) OR alpha flips to NOR
(3) –NOR alpha flips to 1 – OR .....(19) 1 – OR alpha flips to –NOR

(10) 1 – NOR alpha flips to –OR ....(12) –OR alpha flips to 1 – NOR
(11) 1 alpha flips to 1

BETA FLIPS:

(4) 0 beta flips to 1 .......................(14) 1 beta flips to 0
(5) NOR beta flips to 1 – NOR ........(13) 1 – NOR beta flips to NOR
(6) –NOR beta flips to –OR ............(15) –OR beta flips to –NOR

(22) 1 – OR beta flips to OR ...........(23) OR beta flips to 1 – OR
(24) –1 beta flips to –1

GAMMA FLIPS:

(7) 0 gamma flips to 0
(8) NOR gamma flips to –NOR ..........(9) –NOR gamma flips to NOR

(16) 1 – NOR gamma flips to 1 – OR (25) 1 – OR gamma flips to 1 – NOR
(17) 1 gamma flips to –1 .................(27) –1 gamma flips to 1
(18) –OR gamma flips to OR ............(26) OR gamma flips to –OR

By this arrangement there are only five flips per flip type, 15 flips in all.

We can arrange these 15 flips in another way, by their characteristics.

IDENTITIES:

(7) 0 gamma flips to 0
(11) 1 alpha flips to 1
(24) –1 beta flips to –1

CHANGE IN SIGN:

(9) NOR gamma flips to –NOR
(17) 1 gamma flips to –1
(26) OR gamma flips to –OR

POSITIVE MULTIPLICATIVE COMPLEMENTS

(4) 0 beta flips to 1 (The right side is formally: 1 – 0 = 1.)
(5) NOR beta flips to 1 – NOR
(23) OR beta flips to 1 – OR

CHANGES IN TYPE OF OPERATION OR IDENTITY:

(3) –NOR alpha flips to 1 – OR
(12) –OR alpha flips to 1 – NOR
(15) –OR beta flips to –NOR
(20) OR alpha flips to NOR
(21) –1 alpha flips to 0
(25) 1 – OR gamma flips to 1 – NOR

With this information it should be possible to develop a more detailed scheme for representing what is happening during flips than just color and shade changes, as I have done thus far.

__________________
L. J. Thaden

Last edited by Lawrence J. Thaden on 08-29-2008 at 01:20 AM

Report this post to a moderator | IP: Logged

08-28-2008 05:20 PM

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-15 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives