Registered: Jul 2012
Posts: 1

Hello there, I'm new to the forum, but I was wondering if someone could help me with some research I have been conducting.

In a paper I am reviewing, the authors present a 'skewed' version of CA rule 30.

Defining rule 30 as : X _i (t+1) = X_i-1(t) XOR ( X_i(t) OR X_i+1(t) )

Then the 'skewed' rule 30 is defined as follows:

X _i (t+1) = X_i(t) XOR ( X_i+1(t) OR X_i+2(t) )

Now the problem is that the authors claim that this automaton is reversible under the same operation.
e.g to reverse:

X _i (t) = X_i(t+1) XOR ( X_i+1(t+1) OR X_i+2(t+1) )

I have checked this under a few examples, and I have found that this is simply not true.
For example using skewed rule 30 on {0,1,1,0,0} -> {1,0,1,0,1}
But using the reverse on {1,0,1,0,1} -> {0,1,0,1,0,1}.

I was wondering if anyone had seen this kind of 'skewed' rule before, and whether this is a method for constructing reversible automata and that the paper contains a typing error? Or perhaps I have missed something glaringly obvious (but I have spent the best part of the day checking and rechecking).

I am pretty sure that just by shifting the neighbourhood to the right will not convert an automata into a reversible automata, but I am no expert on this, and I just looking for confirmation and any other general advice.

Thanks
Richard

Report this post to a moderator | IP: Logged

Registered: May 2012
Posts: 2

Hi Richard.

It sounds a little similar to the layman's paper that i started on some months ago. But with skewed rule I dont quite understand. I worked on a paper that i did not finish, it was and still is in the process of being written to be fully understood by others. But what you say sounds quite similar to the solution I found. It should actually work if you use another cellular automaton rule, then you can intrinsincly reverse it. But you need atleast one black or white cell on the background you are using. A configuration if you need to find the initials. Eric wrote a paper that shows this is true i believe. But the solution I found I am not sure if those are accepted as a viable solution to reverse the rule 30 in the mathematics community. But it works in practical so for me, i dont know how to do analysis or prove it yet, but the simulation worked and i was quite happy about that. If this is the same trick that i am using, then it works under an operation that uses another CA-rule. two cells are read in the future time-frame or dimension if you like. and the last one cell is reading from the current time. so actually you can intrinsicly generate the reverse states of cells or a future cell based on a reversible logical pathway.

i found that they are the same but they use different positions.

this is the standard algebraic definition of wolframs Rule 30:

A+B+C+(B*C) (mod2)

now, the reversible one i found is this:

A+B+C+(A*B) (mod2)

you see A and C are both different. but the actuall mathematical operations are the same!

if you subtract A+B+C on both sides
you'll get the equation of a straight line or plane or something.

B(C-A)=0

I dont know if this is enough proof to show that it is reversible.
But in my future revisions of my own paper i will try prove that with truth tables or the like.
I want to actually show that it works, but have some time-constraints to do other things meanwhile.

[Edit:]
I dont know if you use the same algorithm that I have but if you do, try using Rule 86 or 106 to intrinsincly reverse it. Dont use rule 30 for that. Atleast that is what I am doing. The reason why I dont know to use 86 or 106 is because you can actually use both because it depends on the ordering of the cells you are reading. I think to actually prove it and show that it works is pretty hard. Since I don't have a degree in math I find it hard to explain and prove such things. A computer simulation is not enough to show, even if it is an exact reversible solution. But to show it works one doesnt really need to have many cells, because it is a local solution. And with that local algorithm you must iterate backwards. Its what i call right-finite reversibility. Also I call it a hidden information-neighbourhood, because there lies "hidden" information between the cells that Rule 30 produces. I dont know if this helped or answered your questions, if not then sorry, but if it could shine some light then I am glad I didnt waste your time. :p

Last edited by Rudi B. Stranden on 08-11-2012 at 03:39 PM

Report this post to a moderator | IP: Logged