Cellular Automata: Rule 30 (Math & Logic)
category: code [glöplog]
first i would like to say that this thread is a continuance to this thread.
i found a paper, link: here, (that was written in 2006) and sent a few questions via mail to the author. still waiting for response. i wasnt aware that this paper existed until not long ago. i am not sure if he ever will respond to the mail i sent or if he ever sees the mail. nevertheless, about his paper, it is hard for me to comprehend all of it since im not like well educated in math, atleast not in a formal sense. but the more i read and understand some things about what he write the more i see that it has some resemblance to the work ive been doing for the past few months.
i will reveal my results later because its kind of a big mess right now, that is I wrote down 70-80 pages off stuff, and by the time being still trying to reduce it to a reasonable amount of pages. the resulting boolean equations i found are pretty simple ones that will be able to reverse the Rule 30 cellular automaton, with the current configuration. its a pretty simple formula that anyone can figure out for themselves just with a little bit of work. a very important finding is that the algebraic normal form is the same as the rule 30 one. which shouldn't be surprising, but in some sense it still is, atleast for me, because it gives a direct link between the rule 30 and the reversible rule - the formula to reverse it. what i can say is that its almost equivalent to rule 86 which the author of the paper (i mentioned above) also says, i believe (still some technical terms are hard to get, but it may be that i hadnt had the time to really put it into any context). before i found the results i was wondering if i would ever write a paper about it, i wanted to do it, but i had to find out if it was done before while i was working on it, or else it wouldnt be any reason for me to write a paper about it. one BIG question is: if my findings is in a sense a more practical way to reverse the rule, than what the author does in his paper. because then there is no reason not to point out - in some kind of additional approach and that there is a more practical way to reverse the process and get back to the initial conditions. if not, then i will reveal the results anyway and point to his paper that it is the same thing (which i still dont know yet), because its so simple and also it might be usable for some people who work with these kinds of problems in cellular automata theory anyway.
thank you
i found a paper, link: here, (that was written in 2006) and sent a few questions via mail to the author. still waiting for response. i wasnt aware that this paper existed until not long ago. i am not sure if he ever will respond to the mail i sent or if he ever sees the mail. nevertheless, about his paper, it is hard for me to comprehend all of it since im not like well educated in math, atleast not in a formal sense. but the more i read and understand some things about what he write the more i see that it has some resemblance to the work ive been doing for the past few months.
i will reveal my results later because its kind of a big mess right now, that is I wrote down 70-80 pages off stuff, and by the time being still trying to reduce it to a reasonable amount of pages. the resulting boolean equations i found are pretty simple ones that will be able to reverse the Rule 30 cellular automaton, with the current configuration. its a pretty simple formula that anyone can figure out for themselves just with a little bit of work. a very important finding is that the algebraic normal form is the same as the rule 30 one. which shouldn't be surprising, but in some sense it still is, atleast for me, because it gives a direct link between the rule 30 and the reversible rule - the formula to reverse it. what i can say is that its almost equivalent to rule 86 which the author of the paper (i mentioned above) also says, i believe (still some technical terms are hard to get, but it may be that i hadnt had the time to really put it into any context). before i found the results i was wondering if i would ever write a paper about it, i wanted to do it, but i had to find out if it was done before while i was working on it, or else it wouldnt be any reason for me to write a paper about it. one BIG question is: if my findings is in a sense a more practical way to reverse the rule, than what the author does in his paper. because then there is no reason not to point out - in some kind of additional approach and that there is a more practical way to reverse the process and get back to the initial conditions. if not, then i will reveal the results anyway and point to his paper that it is the same thing (which i still dont know yet), because its so simple and also it might be usable for some people who work with these kinds of problems in cellular automata theory anyway.
thank you
tl;dr: is there a question or call for comments in there somewhere?
ps: yes it is. sorry for not being too clear about that.
one of the first questions is if his paper says anything about the current configuration (or half current configuration) is enough to reverse it - and if he proves it in his paper.
Quote:
tl;dr
Yes, he does it is enough, no, he does not prove it (it's what a mathematician would call "trivial")
The paper uses a shifted form of the automaton. Your normal rule 30 is a [-1,1] rule, meaning, the color of the cell depends on the cell left to it (-1), the cell itself (0) and the cell right to it (+1).
He uses [-2,0], so each cell depends on itself as well as their 2 left neighbours. This makes no fundamental difference. Think of it as if you are pushing each new line you just created by "your" rule 30 one pixel to the left. You will get a normal rule 30, only that the first line is pushed one pixel to the left, the second two, the third three and so on.
Identically, you can get from his form to your form by pushing the first row one pixel to the right, the second row two pixels to the right and so on.
Page 5:
(d=2), since each cell depends on 3 (2+1) cells of the previous step.
So, if f (the function that maps the color of the two left neighbours and the cell itself to the new color for the cell) is right bijective, the function has an inverse, meaning you can reverse it to get the original color.
(A function is bijective if it is both surjective and injective. For example, negation is a bijective function: it maps integers to integers, and from knowing the result, you can detemine the input value, therefore it is reversible/an inverse function exists)
Page 10:
(Most of the paper seems to deal with periodicity of pattern of generalized automata - not limited to two colors, and not limited to the immediate neighbours - and the question what conditions must hold so that a particular pattern cannot be the result of a smaller(!) previous pattern. For example, in rule 30, the starting pattern, one black pixel at 0, has the predecessor "infinite black pixels from -1 (left of zero) )
The paper uses a shifted form of the automaton. Your normal rule 30 is a [-1,1] rule, meaning, the color of the cell depends on the cell left to it (-1), the cell itself (0) and the cell right to it (+1).
He uses [-2,0], so each cell depends on itself as well as their 2 left neighbours. This makes no fundamental difference. Think of it as if you are pushing each new line you just created by "your" rule 30 one pixel to the left. You will get a normal rule 30, only that the first line is pushed one pixel to the left, the second two, the third three and so on.
Identically, you can get from his form to your form by pushing the first row one pixel to the right, the second row two pixels to the right and so on.
Page 5:
Quote:
Right bijectivity allows one to uniquely determine c0 in
c = f (c−d , c−d+1 , . . . , c−1 , c0 ),
given the colors of all other cells appearing. That is, there is an inverse function
f^{−1} : f (c−d , c−d+1 , . . . , c−1 , x) → x
for every d-tuple (c−d , c−d+1 , . . . , c−1 ).
(d=2), since each cell depends on 3 (2+1) cells of the previous step.
So, if f (the function that maps the color of the two left neighbours and the cell itself to the new color for the cell) is right bijective, the function has an inverse, meaning you can reverse it to get the original color.
(A function is bijective if it is both surjective and injective. For example, negation is a bijective function: it maps integers to integers, and from knowing the result, you can detemine the input value, therefore it is reversible/an inverse function exists)
Page 10:
Quote:
So rule 30 is left bijective, and therefore, by knowing the pattern of one particular row, you know what the previous pattern looked like.The 2-color, range [0, 2] left bijective rules with histories from I are left–right
reflections of the range [−2, 0] right bijective rules; their rule numbers are
15, 30, 45, 60, 75, 90, 105, 120, 150, 180, 210, 240
(Most of the paper seems to deal with periodicity of pattern of generalized automata - not limited to two colors, and not limited to the immediate neighbours - and the question what conditions must hold so that a particular pattern cannot be the result of a smaller(!) previous pattern. For example, in rule 30, the starting pattern, one black pixel at 0, has the predecessor "infinite black pixels from -1 (left of zero) )
Quote:
... and therefore that pattern in irreducable(Most of the paper seems to deal with periodicity of pattern of generalized automata - not limited to two colors, and not limited to the immediate neighbours - and the question what conditions must hold so that a particular pattern cannot be the result of a smaller(!) previous pattern. For example, in rule 30, the starting pattern, one black pixel at 0, has the predecessor "infinite black pixels from -1 (left of zero) )
Joghurt: thanks for clearing out some things.
yes, you're right, it makes no difference how one indices the numbers.
i need to study the inverse function more after some time, because it bugs me that i cant comprehend it to the fullest. i thought it would be easy for a function. i usually look at functions as f(x), f(x,y) or f with subscript i j. but this one is kind of different.
i'll either make some document or make a site where i explain the boolean operators i used for my own approach etc for this. if not anyone else does it before me, that is, because i havent found one yet, i tried search alot before i found this paper.
yes, the irreducibility has been set by wolfram for quite some time. im going to look further into it when i am done with this part first.
Quote:
He uses [-2,0], so each cell depends on itself as well as their 2 left neighbours.
yes, you're right, it makes no difference how one indices the numbers.
i need to study the inverse function more after some time, because it bugs me that i cant comprehend it to the fullest. i thought it would be easy for a function. i usually look at functions as f(x), f(x,y) or f with subscript i j. but this one is kind of different.
i'll either make some document or make a site where i explain the boolean operators i used for my own approach etc for this. if not anyone else does it before me, that is, because i havent found one yet, i tried search alot before i found this paper.
yes, the irreducibility has been set by wolfram for quite some time. im going to look further into it when i am done with this part first.
Quote:
You're welcome.thanks for clearing out some things.
Quote:
I'm not sure if you mean this, but it actually makes a difference: the results looks differently, but the structure he is examining is the same.yes, you're right, it makes no difference how one indices the numbers.
a [-1,1] rule makes a cell dependent upon the left and right cell, a [-2,0] to the two left and no right. A [-42,23] rule would make it dependant on 42 left and 23 right.
But you probably meant that.
Quote:
He never specifies that function, he simply says that it exists.i need to study the inverse function more after some time, because it bugs me that i cant comprehend it to the fullest. i thought it would be easy for a function. i usually look at functions as f(x), f(x,y) or f with subscript i j. but this one is kind of different.
And do not think about functions like graphs like you learned in school, like f(x) and f(x,y). They are much more generic. Think of them like a function in a programming language.
A function is simply a black box that maps values to different (or same) values. Both the result as well as the input values can actually be a tuple.
For example, your school function f(x) = 42*x + 9 can be written as
f : R -> R
x |-> 42*x +9
"f is a function that takes a value from R (real numbers) and maps it to a real number. For each value x from R, x is mapped to 42*x+9"
instead of R, you can use sets, fields, whatever suits you.
f: R x R x R -> R
(x0,x1,x2) |-> x0*x1*x2
Would be a function that "takes 3 parameters" and multiplies them.
I think the wikipedia article is a good introduction.
Stop thinking about functions like graphs. They are useful to understand basic properties in linear algebra, but will confuse you once you get into the more serious stuff.
Oh, and BTW: the paper you referenced is IMO poorly written, it uses some confusing notation etc. I've studied physics and therefore saw a fair of mathematics, but it still took me some minutes to understand what he actually was saying.
Joghurt:
okay. seems like i would continue my work on this then.
do you have email of some sort or anywhere i can send some more questions to you. i might even ask you if you could help me building a paper out of this, if my simple findings are worthy. i do however have alot to sort out and rewrite first, since its a mess like i said. i dont want to spam pouet too much either. you seem to be having the answers i need, since you understand the paper as well.
Quote:
He never specifies that function, he simply says that it exists.
okay. seems like i would continue my work on this then.
do you have email of some sort or anywhere i can send some more questions to you. i might even ask you if you could help me building a paper out of this, if my simple findings are worthy. i do however have alot to sort out and rewrite first, since its a mess like i said. i dont want to spam pouet too much either. you seem to be having the answers i need, since you understand the paper as well.
http://www.mathpages.com/home/kmath439/kmath439.htm
Inopia: i allready posted that link in this thread.
ok. excuse me for posting this too soon. Im kind of tired, and after i got email from Eric (the author behind the paper), he said quote
isnt this contradictory? what does he mean? i am waiting reply now.
i decided to put my past findings online at this hour. so it might contain some errors, please if anyone have the time or motivation check out if its right. if im in the mood tomorrow i will work on a more comprehensive document. but this page i just wrote is the central point of the algorithm.
Rule 30 reversibility.pdf
Quote:
Yes, it's true that rule 30 is not reversible as a cellular automaton, but once you've fixed the right half of each row appropriately then you can go backwards in time uniquely.
isnt this contradictory? what does he mean? i am waiting reply now.
i decided to put my past findings online at this hour. so it might contain some errors, please if anyone have the time or motivation check out if its right. if im in the mood tomorrow i will work on a more comprehensive document. but this page i just wrote is the central point of the algorithm.
Rule 30 reversibility.pdf
i found an error. its fixed.
this is not based on r=2 neighborhood. rather its only 2 cells. and random rules on each row:
just got bored and had to experiment with some visual stuff
just got bored and had to experiment with some visual stuff
some experiments..
i could make a demo with that :)
beautiful images
ps: it actually runs in realtime so. yes. ps. demo with this would be cool.:)
elfh: thanks!
elfh: thanks!
Y u talk and not make demo?
Preacher: sorry, but time is limited. it requires much work to make good demo by one person. if ps wants extra-code to he can contact me. or anyone serious about designing a demo for this i would like to be part, but not main-coder.
:D
but not least, motivation :D
Quote:
i could make a demo with that :)
Like this one?
(Unlike a normal cellular automation, it's not deterministic)
