Writing a paper about Cellular Automata
Moderators: gmalivuk, Moderators General, Prelates
Writing a paper about Cellular Automata
Hello!
This is my first post in this forum. It seems to have alot of activity and some interesting topics!
First Okay, tell a little about my story:
I kinda droped out of college, I liked math a bit, but i hated school.
I still i have alot of computational experience and I experiment with cellular automata and the like,
i started programming at early age.
I have fragmented knowledge about math, but sometimes i look at a problem and solve it very easily.
but I am really sucky at writing anything down into readable form (for others to understand).
I what i want to ask you about is what does a paper contain?
Does it have mathematical proofs, solutions to problems etc. but what does a proof actually mean?
does someone have a specifical definition of a proof? let's say i have found a solution to a problem that I think
can be usefull for researchers, professors, mathematicians and physicists and the like..
how do i prove that it is correct? by coding a computer program i see that it is correct, but i dont necessary
have the mathematical knowledge (formal) to write a proof down.
I want to learn it, but i dont have access to school. my bachelorstudies in Computer Science was boring and so my
grades reflected that. i dont study any mastering either.
im studying stuff at home, not at an academy. and have many ideas and solutions to problems.
studying the cellular automaton rules i found a way to reverse rule 30, that is to go backwards without much to know about the history.
only last configuration.
i heard it was impossible to do, i read on the web, and looked at seminar by Stephen Wolfram about his book.
but either i have misunderstood or i have the solution on how to go backwards (atleast for this specific rule).
I dont know if it has been done before.
I wanna write a paper about it, but i dont know how. or where to start.
Thanks
Rudi
This is my first post in this forum. It seems to have alot of activity and some interesting topics!
First Okay, tell a little about my story:
I kinda droped out of college, I liked math a bit, but i hated school.
I still i have alot of computational experience and I experiment with cellular automata and the like,
i started programming at early age.
I have fragmented knowledge about math, but sometimes i look at a problem and solve it very easily.
but I am really sucky at writing anything down into readable form (for others to understand).
I what i want to ask you about is what does a paper contain?
Does it have mathematical proofs, solutions to problems etc. but what does a proof actually mean?
does someone have a specifical definition of a proof? let's say i have found a solution to a problem that I think
can be usefull for researchers, professors, mathematicians and physicists and the like..
how do i prove that it is correct? by coding a computer program i see that it is correct, but i dont necessary
have the mathematical knowledge (formal) to write a proof down.
I want to learn it, but i dont have access to school. my bachelorstudies in Computer Science was boring and so my
grades reflected that. i dont study any mastering either.
im studying stuff at home, not at an academy. and have many ideas and solutions to problems.
studying the cellular automaton rules i found a way to reverse rule 30, that is to go backwards without much to know about the history.
only last configuration.
i heard it was impossible to do, i read on the web, and looked at seminar by Stephen Wolfram about his book.
but either i have misunderstood or i have the solution on how to go backwards (atleast for this specific rule).
I dont know if it has been done before.
I wanna write a paper about it, but i dont know how. or where to start.
Thanks
Rudi

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Writing a paper about Cellular Au
It is impossible to do, every configuration has four possibilities of what could lead to it, so it is impossible.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
 Yakk
 Poster with most posts but no title.
 Posts: 11065
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Writing a paper about Cellular Au
What is a proof?
A proof is a justification for an answer to a question.
The proof is typically written out in a sequence of steps such that checking each step is (much) easier than finding the answer to the original proof, and that if the steps are valid then the reader will agree the answer is correct.
Now, that checking is highly context dependent. What kind of steps are acceptable and which are not depends on what is well known about the subject area, and the skill of the reader.
In an academic sense, this means understanding enough about the subject area to understand what kind of steps are easy to verify and are known, and which are not. Creating an invalid proof is really, really easy, where at some point you miss some random edge case. You also have to really specifically describe the question in such a way that there is very little ambiguity, and the same with the answer: doing so is a hard problem, and is one of the things you learn when you study a subject area academically.
For specific examples of proofs, you could pick up any textbook on computer science and automata theory. Or you could search online paper repositories.
"Seeing that a computer program is correct" is not, generally, a reliable form of proof.
On overestimation and the Dunning–Kruger effect:
In short, don't try to keep your technique secret. Tell people, and ask for help with the flaws. There will almost certainly be flaws. The worth of your idea is not a function of how hard it was to come up with, and you aren't an expert at coming up with highworth ideas.
A proof is a justification for an answer to a question.
The proof is typically written out in a sequence of steps such that checking each step is (much) easier than finding the answer to the original proof, and that if the steps are valid then the reader will agree the answer is correct.
Now, that checking is highly context dependent. What kind of steps are acceptable and which are not depends on what is well known about the subject area, and the skill of the reader.
In an academic sense, this means understanding enough about the subject area to understand what kind of steps are easy to verify and are known, and which are not. Creating an invalid proof is really, really easy, where at some point you miss some random edge case. You also have to really specifically describe the question in such a way that there is very little ambiguity, and the same with the answer: doing so is a hard problem, and is one of the things you learn when you study a subject area academically.
For specific examples of proofs, you could pick up any textbook on computer science and automata theory. Or you could search online paper repositories.
"Seeing that a computer program is correct" is not, generally, a reliable form of proof.
On overestimation and the Dunning–Kruger effect:
Spoiler:
In short, don't try to keep your technique secret. Tell people, and ask for help with the flaws. There will almost certainly be flaws. The worth of your idea is not a function of how hard it was to come up with, and you aren't an expert at coming up with highworth ideas.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Writing a paper about Cellular Au
Yakk:
thank you for an interesting and educable answer. i will have to read it a couple of times more to really grasp it all and let it in. I ordered a book last year, its called "Theory And Applications of Cellular Automata" by Martinez and le others, that contains papers with different solutions to problems and papers that introduces applications on some topics in CA. I just recently started looking into it and I find it difficult to understand, but I get some clues by reading the Abstract sections etc.
What I do is much simpler than all these things. Because I like simple solutions! and my solution to this specific problem was a very logical thinking, like injecting something into the automaton and just giving it the right directions.
I know that seeing a computer program that is correct, is not a reliable form of proof. thats why I am looking into actually writing a proof by dividing the different program codes into small sections, and getting it down as some form on a paper or something, hopefully. Ill ask here for help if i need it, if thats okay. i find this forum the best one considering the issues and problems I have, atleast it seems like a forum where one can learn, get hints about things, and talk about interresting subjects etc. But I would have to write down some stuff first, so that it doesnt look like gibberish. I talked with someone who work with patents here in my country  Just to hear if something like this would be worth to patent if it really was a solution to something. Really I dont want to do it, if it happens to be a solution! But I need a meeting with him before actually revealing anything about this, even if it might not be anything. I cant afford to patent it, but i would like some info from someone about it anyway. The only reason why I actually think this way is because "Rule 30" is allready patented. And, what would be a cooler idea to actually patent a reversible solution to that rule? I dont think its extraordinary solution to all worlds problems what i have here, hehe. It took me one day to solve the problem i was facing. And when I looked on the web etc: I found out that no others had done this before. And some people say it's plain impossible. Even Stephen Wolfram himself. I dont understand what he and they mean by that, but anyway. How can something be impossible when I think I have the solution right here. Not that I care. What I care about is my work, and what i did that day was a very concentration to do things right. If I can prove that what I have is actually right, then I would be glad. I dont say those people are wrong, but I want to show how to solve a problem, by using a / some method(s), rather than wasting time on thinking that what I have here is not right, when I can't see it yet, because my program is showing the proof. I dont know how many iterations I would have to do and check to find that it is not correct, a million? or infinite many times? i think thats why i want it down on paper. im sure if i look closer I can find wrong things about it. But if I follow the logical methods I use, it doesnt seem like that. There you have some thoughts about what kind of problems i am in right now. hehe.
I tried to share my idea first at some site, but I didnt find any great answers back. I just got: "No, its impossible to do" etc.. but.. so i am trying to find an environment where knowledge is freely accepted and where people: mathematicians, physicists dont look at things that are impossible, but look on how things can be possible. if you know what i mean.
anyway, i could have written so much more here, i just have so much to say, but it would be too much to read hehe, so ill just wait and see what people say. i will look more into proofs etc. also its almost like i am not at the time being in the mood of putting my notes into something bigger and better. I think i need a break from that, so I will take it out later and look at it then. It's been a very strange past few days, thinking around this kind of thing. I will not have my technique secret after a few talks and when ive gotten a few answers to some questions that i have. i hope that it is okay! i will get back to this, when i have gotten the answers! I want information to be free! But sometimes I wonder, whats the reason why Rule 30 is already patented? Because its a good random generator or is used in publickey cryptography? and used in processes in nature (not only rule 30). but anyway. if one can reverse engineer things, nothing would be impossible! not even finding the cellular automaton for our universe! (although that requires alot of work ).
thank you for an interesting and educable answer. i will have to read it a couple of times more to really grasp it all and let it in. I ordered a book last year, its called "Theory And Applications of Cellular Automata" by Martinez and le others, that contains papers with different solutions to problems and papers that introduces applications on some topics in CA. I just recently started looking into it and I find it difficult to understand, but I get some clues by reading the Abstract sections etc.
What I do is much simpler than all these things. Because I like simple solutions! and my solution to this specific problem was a very logical thinking, like injecting something into the automaton and just giving it the right directions.
I know that seeing a computer program that is correct, is not a reliable form of proof. thats why I am looking into actually writing a proof by dividing the different program codes into small sections, and getting it down as some form on a paper or something, hopefully. Ill ask here for help if i need it, if thats okay. i find this forum the best one considering the issues and problems I have, atleast it seems like a forum where one can learn, get hints about things, and talk about interresting subjects etc. But I would have to write down some stuff first, so that it doesnt look like gibberish. I talked with someone who work with patents here in my country  Just to hear if something like this would be worth to patent if it really was a solution to something. Really I dont want to do it, if it happens to be a solution! But I need a meeting with him before actually revealing anything about this, even if it might not be anything. I cant afford to patent it, but i would like some info from someone about it anyway. The only reason why I actually think this way is because "Rule 30" is allready patented. And, what would be a cooler idea to actually patent a reversible solution to that rule? I dont think its extraordinary solution to all worlds problems what i have here, hehe. It took me one day to solve the problem i was facing. And when I looked on the web etc: I found out that no others had done this before. And some people say it's plain impossible. Even Stephen Wolfram himself. I dont understand what he and they mean by that, but anyway. How can something be impossible when I think I have the solution right here. Not that I care. What I care about is my work, and what i did that day was a very concentration to do things right. If I can prove that what I have is actually right, then I would be glad. I dont say those people are wrong, but I want to show how to solve a problem, by using a / some method(s), rather than wasting time on thinking that what I have here is not right, when I can't see it yet, because my program is showing the proof. I dont know how many iterations I would have to do and check to find that it is not correct, a million? or infinite many times? i think thats why i want it down on paper. im sure if i look closer I can find wrong things about it. But if I follow the logical methods I use, it doesnt seem like that. There you have some thoughts about what kind of problems i am in right now. hehe.
I tried to share my idea first at some site, but I didnt find any great answers back. I just got: "No, its impossible to do" etc.. but.. so i am trying to find an environment where knowledge is freely accepted and where people: mathematicians, physicists dont look at things that are impossible, but look on how things can be possible. if you know what i mean.
anyway, i could have written so much more here, i just have so much to say, but it would be too much to read hehe, so ill just wait and see what people say. i will look more into proofs etc. also its almost like i am not at the time being in the mood of putting my notes into something bigger and better. I think i need a break from that, so I will take it out later and look at it then. It's been a very strange past few days, thinking around this kind of thing. I will not have my technique secret after a few talks and when ive gotten a few answers to some questions that i have. i hope that it is okay! i will get back to this, when i have gotten the answers! I want information to be free! But sometimes I wonder, whats the reason why Rule 30 is already patented? Because its a good random generator or is used in publickey cryptography? and used in processes in nature (not only rule 30). but anyway. if one can reverse engineer things, nothing would be impossible! not even finding the cellular automaton for our universe! (although that requires alot of work ).
Re: Writing a paper about Cellular Au
First of all, tomtom already told you that it's impossible to do and why. Do you have a reason that the point he brought up is invalid?
Second of all, remember that code speaks louder than words. If you have code that does something people say is impossible, post it somewhere (ex github) and make it known so people can tell you what's wrong with it. And approach it in a way that does not seem arrogant and "I'm smarter than the people who spend their lives studying this stuff and proved it impossible but I did it anyway." All that will accomplish is annoying people and making them tear your code apart. The type of people who look at it will generally provide constructive feedback as to what was wrong about it or else be very impressed if your code is right.
Second of all, remember that code speaks louder than words. If you have code that does something people say is impossible, post it somewhere (ex github) and make it known so people can tell you what's wrong with it. And approach it in a way that does not seem arrogant and "I'm smarter than the people who spend their lives studying this stuff and proved it impossible but I did it anyway." All that will accomplish is annoying people and making them tear your code apart. The type of people who look at it will generally provide constructive feedback as to what was wrong about it or else be very impressed if your code is right.
cjmcjmcjmcjm wrote:If it can't be done in an 80x24 terminal, it's not worth doing
Re: Writing a paper about Cellular Au
Do not ever keep your ideas secret. Out of all the ideas you come up with in your life, almost none will be worth keeping secret. But many will be worth sharing.
Re: Writing a paper about Cellular Au
Meem is right. If you have code that does something previously thought impossible  or even pseudocode, that is humanreadable but not actually written in a programming language  then post it so we can give it the onceover. Probably there'll be some flaw in it, since some very clever people have already looked into this and found conclusive 100% proof that it's impossible, but you never know.
The preceding comment is an automated response.

 Posts: 224
 Joined: Tue Jun 17, 2008 11:04 pm UTC
Re: Writing a paper about Cellular Au
Definition: A cellular automaton is reversible if every configuration has a unique predecessor, that is, a unique configuration that transitions to it. Where "configuration" refers to the global state  the state of every cell in the automaton.
Theorem: Rule 30 is not reversible.
Proof: The configuration where every cell is 0 has two predecessors. Itself and the configuration where every cell is 1. QED.
On the other hand, there is an interesting paper that shows (among other things) that rule 30 is reversible if you impose the additional constraint that the right half of any configuration must eventually be all zero. Given this paper together with the above disproof, it's unlikely what you've discovered is new. But it is still good to experiment and learn about such things.
Theorem: Rule 30 is not reversible.
Proof: The configuration where every cell is 0 has two predecessors. Itself and the configuration where every cell is 1. QED.
On the other hand, there is an interesting paper that shows (among other things) that rule 30 is reversible if you impose the additional constraint that the right half of any configuration must eventually be all zero. Given this paper together with the above disproof, it's unlikely what you've discovered is new. But it is still good to experiment and learn about such things.
 ahammel
 My Little Cabbage
 Posts: 2135
 Joined: Mon Jan 30, 2012 12:46 am UTC
 Location: Vancouver BC
 Contact:
Re: Writing a paper about Cellular Au
If you're interested in learning what goes in to a math or CS paper, why not read some? Since you've got some postsecondary education in the topic, you should be able to find some that you can get through without too much difficulty. If I understand you correctly, you don't have access to a university library anymore, but there are plenty of journals that make at least some of their material available for free on the interenet. This is probably a good start. A good public library will have a few scholarly journals available as well.
Edit: P.S. The title of your thread is cut off. I was very confused to learn that you're not writing a paper about cellular gold.
Edit: P.S. The title of your thread is cut off. I was very confused to learn that you're not writing a paper about cellular gold.
He/Him/His/Alex
God damn these electric sex pants!
Re: Writing a paper about Cellular Au
ahammel: thanks for the links! sorry about that topic, i dunno what happened with it during my first post. It should of course have said Cellular Automata. so its an error from my side or something. that paper, i allready have but thanks for telling me anyway, i didnt read and understand it all the way through yet, but i will do it again! I was actually going to send a email to Eric Rowland, but i choosed not too since i just have these messy notes.
okay, thanks, and too all of you: I will try and write some human readable paper about this (because now it's just very chaotic, probably most wouldnt understand it since it is in c++ code) and then I will come back and post it so you can read it and come with suggestions, errorcorrections and the like. i will try and find some info on how mathematicians write pseudocode so i can include it in the paper/article for you to see or whatever.
[Edit]: another thing (which i forgot) that i formally was going to ask this time, was if someone knows about a good application for windows that can be used to write math symbols and text, draw things like grids, figures and so on to include in an article for example
okay, thanks, and too all of you: I will try and write some human readable paper about this (because now it's just very chaotic, probably most wouldnt understand it since it is in c++ code) and then I will come back and post it so you can read it and come with suggestions, errorcorrections and the like. i will try and find some info on how mathematicians write pseudocode so i can include it in the paper/article for you to see or whatever.
[Edit]: another thing (which i forgot) that i formally was going to ask this time, was if someone knows about a good application for windows that can be used to write math symbols and text, draw things like grids, figures and so on to include in an article for example
Rudi
Re: Writing a paper about Cellular Au
If you're going to write a paper on it at all, you need to learn LaTeX. There are many tutorials on the internet for learning it. A good one for the basics is at Art of Problem Solving (http://www.artofproblemsolving.com/Wiki ... aTeX:About).
cjmcjmcjmcjm wrote:If it can't be done in an 80x24 terminal, it's not worth doing
 ahammel
 My Little Cabbage
 Posts: 2135
 Joined: Mon Jan 30, 2012 12:46 am UTC
 Location: Vancouver BC
 Contact:
Re: Writing a paper about Cellular Au
rudi wrote:okay, thanks, and too all of you: I will try and write some human readable paper about this (because now it's just very chaotic, probably most wouldnt understand it since it is in c++ code) and then I will come back and post it so you can read it and come with suggestions, errorcorrections and the like.
Trust me, anybody who is in a position to make corrections will understand c++ code.
rudi wrote:[Edit]: another thing (which i forgot) that i formally was going to ask this time, was if someone knows about a good application for windows that can be used to write math symbols and text, draw things like grids, figures and so on to include in an article for example
I strongly support using LaTeX. MiKTeX is the most popular Windows frontend, but emacs and vim make good environments with a few additional packages.
He/Him/His/Alex
God damn these electric sex pants!
Re: Writing a paper about Cellular Au
thanks.
im downloading protext, i dunno if it includes latex or miktex. i think i tried miktex without luck, or something else. cant remember.
also im in the middle of a inheritance. my dad passed away last year. and its so much else takes time to do than working on this.
hopefully ill get back when all this is inheritance is over. takes alot of energy.
im downloading protext, i dunno if it includes latex or miktex. i think i tried miktex without luck, or something else. cant remember.
also im in the middle of a inheritance. my dad passed away last year. and its so much else takes time to do than working on this.
hopefully ill get back when all this is inheritance is over. takes alot of energy.
Rudi
 ahammel
 My Little Cabbage
 Posts: 2135
 Joined: Mon Jan 30, 2012 12:46 am UTC
 Location: Vancouver BC
 Contact:
Re: Writing a paper about Cellular Au
Protext looks like it's based on MiKTeX, so it should be sufficient. I'm not a windows user, so I can't be of much direct help.
I'm sorry for your loss. Take your time.
I'm sorry for your loss. Take your time.
He/Him/His/Alex
God damn these electric sex pants!
Re: Writing a paper about Cellular Automata
Hey! Im back! im very very tired right now, but i decided to post my results. if anyone can check it, (i dont know if it has some spellingerrors right now), then please tell me how it turned out! also if there are any questions, please post them here, and i will answer. tell me why Rule 30 is not reversible after reading this:
http://www.home.no/rudibs/Rule 30 reversibility.pdf
i believe it is reversible, i just can't believe anything else, or i've missed something essential about the definition they use for reversibility.
i wrote the document fast because i decided to post it before i go to sleep.
i will write a more comprehensive document that might be easier to understand the things i wrote, but they should be easy after some studying.
its really simple. because rule 30 is simple to produce, it should be simple to reverse.
remember the current configurations is all one needs.
please understand that the states of Rule 86 is the key here after reading the 3cells to determine the left one (a(i1)).
now i want feedback, questions, bugs, errorcorrections and the like. i really want to hear what you say about this.
Rudi
http://www.home.no/rudibs/Rule 30 reversibility.pdf
i believe it is reversible, i just can't believe anything else, or i've missed something essential about the definition they use for reversibility.
i wrote the document fast because i decided to post it before i go to sleep.
i will write a more comprehensive document that might be easier to understand the things i wrote, but they should be easy after some studying.
its really simple. because rule 30 is simple to produce, it should be simple to reverse.
remember the current configurations is all one needs.
please understand that the states of Rule 86 is the key here after reading the 3cells to determine the left one (a(i1)).
now i want feedback, questions, bugs, errorcorrections and the like. i really want to hear what you say about this.
Rudi
Rudi

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Writing a paper about Cellular Automata
Okay, if your algorithm does what it is supposed to do, then it should do one of these three things with an infinite string:
1. It outputs all the strings which, when run through rule 30, produce the original string.
2. It outputs one of the strings which, when run through rule 30, produce the original string.
3. It outputs the only string which, when run through rule 30, produce the original string.
Option 1 is possible, and it would be interesting, but it is not reversibility. Reversibility is one to one.
Option 2 is possible, but it is less interesting than option 1, as it is less powerful. However it is not reversibility, because it is weaker than option 1, and just because it is one to one, doesn't mean rule 30 is reversible, as for some strings it will omit a different string which precedes the original string.
Option 3 is impossible because, as we have shown, some strings (if not all) have at least 2 strings which could precede it in the iteration, for example the string of all zeroes.
1. It outputs all the strings which, when run through rule 30, produce the original string.
2. It outputs one of the strings which, when run through rule 30, produce the original string.
3. It outputs the only string which, when run through rule 30, produce the original string.
Option 1 is possible, and it would be interesting, but it is not reversibility. Reversibility is one to one.
Option 2 is possible, but it is less interesting than option 1, as it is less powerful. However it is not reversibility, because it is weaker than option 1, and just because it is one to one, doesn't mean rule 30 is reversible, as for some strings it will omit a different string which precedes the original string.
Option 3 is impossible because, as we have shown, some strings (if not all) have at least 2 strings which could precede it in the iteration, for example the string of all zeroes.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
Re: Writing a paper about Cellular Automata
tomtom2357: please explain what you mean by this.
i believe that you talk about the definition of string the same as configuration, or?
commonly: the original rule 30 with black cell or with initial configurations (random states of cells) intrinsincly generates consecutive configurations with time steps on forward.
what my algorithm are capable of is to intrinsincly generate the consecutive reverse states of cells with reverse time steps of the current/last configuration. the length of the current configuration is the amount of time steps you need to go back to the original configuration (your random string).
[edit: computational irreducibility has nothing to do with reversibility]
i believe that you talk about the definition of string the same as configuration, or?
commonly: the original rule 30 with black cell or with initial configurations (random states of cells) intrinsincly generates consecutive configurations with time steps on forward.
what my algorithm are capable of is to intrinsincly generate the consecutive reverse states of cells with reverse time steps of the current/last configuration. the length of the current configuration is the amount of time steps you need to go back to the original configuration (your random string).
[edit: computational irreducibility has nothing to do with reversibility]
Rudi
Re: Writing a paper about Cellular Automata
Okay, how about this. I generated a random sequence of digits, and it turned out the at the next step my string looks like this:
.....0000000000000000.....
Or if you prefer,
....Black Black Black Black.......
What did I have previously? Note that this is precisely the question you claim to be answering, but I am confident that if you tell me just one answer, you will be wrong. If you give me more than one answer, you might be right, but this won't be new, as reversible claims there is a unique sequence leading to this.
.....0000000000000000.....
Or if you prefer,
....Black Black Black Black.......
What did I have previously? Note that this is precisely the question you claim to be answering, but I am confident that if you tell me just one answer, you will be wrong. If you give me more than one answer, you might be right, but this won't be new, as reversible claims there is a unique sequence leading to this.
G4!!
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Re: Writing a paper about Cellular Automata
OverBored:
your question is based on what you define being zero or one in your rule 30 pattern. black and white has two different solutions, you need to specify which one it is. a sequence of 1,1,1,1,1,1,1,1's had previously a sequence of ...0,0,1,0,0,1,0,0,1.... (because 1 would have generated infinite zeros), and a sequence of zeroes would have had previous sequence of ...0,0,0,0,0,0,.... you ask me which one of these there is without explicitly tell me if your sequences are inifinite or not  has borders or not. if you go backwards with one black cell you see that there are infinite history yes. but when you know that you can use another dimension to reverse lets say a defined discrete latitce of cells with some random initial configuration, it i dont see the reason why one cannot say that it is?
first of all, the algorithm was not in the first place designed for cyclic borders, but it would work there too if the width of the wrapping was equal to a modulus 8 digit in decimal and if you knew the amount of time steps. one can go backwards as much as one wants anyhow. my algorithm was designed for noncyclic borders. but, even that the lattice was infinite you would be able to go backwards at specific points of times.
since the rule 30 intrinsinctly generates numbers based on ONE rule, the rule to reverse it is exactly the same, only by opposite states of cells  Rule 86 is this solution. it intrinsincly generates the state of the past a(i1)discrete cell based on one extra dimension in time, the past  sort of the same dimension as when one generates a rule 30 pattern forward in time.
if rule 30 generates histories based on previous histories. i dont see any reason why generating the histories on past histories can be used as a reversible solution?
your question is based on what you define being zero or one in your rule 30 pattern. black and white has two different solutions, you need to specify which one it is. a sequence of 1,1,1,1,1,1,1,1's had previously a sequence of ...0,0,1,0,0,1,0,0,1.... (because 1 would have generated infinite zeros), and a sequence of zeroes would have had previous sequence of ...0,0,0,0,0,0,.... you ask me which one of these there is without explicitly tell me if your sequences are inifinite or not  has borders or not. if you go backwards with one black cell you see that there are infinite history yes. but when you know that you can use another dimension to reverse lets say a defined discrete latitce of cells with some random initial configuration, it i dont see the reason why one cannot say that it is?
first of all, the algorithm was not in the first place designed for cyclic borders, but it would work there too if the width of the wrapping was equal to a modulus 8 digit in decimal and if you knew the amount of time steps. one can go backwards as much as one wants anyhow. my algorithm was designed for noncyclic borders. but, even that the lattice was infinite you would be able to go backwards at specific points of times.
since the rule 30 intrinsinctly generates numbers based on ONE rule, the rule to reverse it is exactly the same, only by opposite states of cells  Rule 86 is this solution. it intrinsincly generates the state of the past a(i1)discrete cell based on one extra dimension in time, the past  sort of the same dimension as when one generates a rule 30 pattern forward in time.
if rule 30 generates histories based on previous histories. i dont see any reason why generating the histories on past histories can be used as a reversible solution?
Rudi
Re: Writing a paper about Cellular Automata
rudi wrote:OverBored:
your question is based on what you define being zero or one in your rule 30 pattern. black and white has two different solutions, you need to specify which one it is. a sequence of 1,1,1,1,1,1,1,1's had previously a sequence of ...0,0,1,0,0,1,0,0,1.... (because 1 would have generated infinite zeros), and a sequence of zeroes would have had previous sequence of ...0,0,0,0,0,0,.... you ask me which one of these there is without explicitly tell me if your sequences are inifinite or not  has borders or not. if you go backwards with one black cell you see that there are infinite history yes. but when you know that you can use another dimension to reverse lets say a defined discrete latitce of cells with some random initial configuration, it i dont see the reason why one cannot say that it is?
Sorry, I should have been clearer. I meant the latter. You correctly observe that
....0000000....
is a possible previous state. However, there is another possible previous state:
.....11111111.....
Just to clarify, my sequences are infinite in both directions. I am pretty sure this is a standard definition. Some definitions might require that the number of 1's be bounded, in which case it might be conceivable that the process is reversible, but this isn't what we normally mean.
G4!!
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Grob FTW,
Hello. Smithers. You're. Quite good. At. Turning. Me. On.
Re: Writing a paper about Cellular Automata
1) ...111111111111111111... and ...0000000000000... doesnt contain any
information at all.
2) they dont produce any complex patterns.
based on this, it doesnt even have to be generated by Rule 30. its unfortunately a contradiction.
information at all.
2) they dont produce any complex patterns.
based on this, it doesnt even have to be generated by Rule 30. its unfortunately a contradiction.
Rudi
Re: Writing a paper about Cellular Automata
Rudi, I have looked at your solution, and while I haven't checked if it "works", I have found a problem with it.
I understand that you're determining the previous cells gradually, from right to left. For this reason, you allow yourself to use a(i) and a(i+1) in your formula to determine a(i1). This would be okay, BUT... it means that your algorithm can never start! In order to compute a(0), you need a(1) and a(2). But before you can compute a(1) and a(2), your formula needs a(3) and a(4). And before that, you need a(5) and a(6)! And so on... Your algorithm has no place to start, because it requires at least some information about generation t before it can compute any of the cells in generation t.
Does that make sense?
I understand that you're determining the previous cells gradually, from right to left. For this reason, you allow yourself to use a(i) and a(i+1) in your formula to determine a(i1). This would be okay, BUT... it means that your algorithm can never start! In order to compute a(0), you need a(1) and a(2). But before you can compute a(1) and a(2), your formula needs a(3) and a(4). And before that, you need a(5) and a(6)! And so on... Your algorithm has no place to start, because it requires at least some information about generation t before it can compute any of the cells in generation t.
Does that make sense?

 Posts: 309
 Joined: Tue Feb 27, 2007 2:27 am UTC
Re: Writing a paper about Cellular Automata
It sounds like rudi has noticed that some subset of initial conditions yield reversible dynamics for some number of iterations, and that the evolution starting from these initial conditions can be reversed in a straightforward way. This leads to the questions:
1) Will the CA evolve from a reversible state to an irreversible one?
2) Can we specify what subset of initial conditions yields reversible dynamics?
3) Is this result wellknown, or weaker than a wellknown result?
As an outsider to the CA world, it seems like rudi's algorithm might be interesting if these questions can be answered.
1) Will the CA evolve from a reversible state to an irreversible one?
2) Can we specify what subset of initial conditions yields reversible dynamics?
3) Is this result wellknown, or weaker than a wellknown result?
As an outsider to the CA world, it seems like rudi's algorithm might be interesting if these questions can be answered.
I'm mostly a lurker. I lurk. Kind of like a fish, in the shadows.
Re: Writing a paper about Cellular Automata
Qlexander:
Sorry about not have written to much backgroundinformation, i will do that in a more comprehensive document like i said earlier, just havent gotten around making the document complete yet.
You have the information  let's say you have only one configuration, but the past are gone, there is just a white background except for your current configuration. Let's say that this lies on t=0.
I will refer to as spacesteps as when i decreases by one (i=i1) which has nothing to do with timesteps (t=t1).
We will calculate the new cell at t1, a(i1).
At the first decrypting sequence a'(i) the configuration lies (the one you got) are on time t=0. a(i1), a(i) and a(i+1) are all 0 before the first spacestep. on the next spacestep (that is i1) the a(i) might be black or white depending on the a'(i1) state after the first spacestep. we know that the first and last few cells are black because of the borders on rule 30, but in general when reading a'(i) where our configuration lies there might be 0 or 1 depending on the rule 86 truth table (or the formula used, which is kind of a mirror of the truth table). combining these values that gets fed into the a(i1), a(i) and a(i+1) with the previous configuration a'(i) one determines the output a(i1). so yes, its one extra dimension a'(i). when the configurationlength is complete time decreases by one. all this happens in discrete time anyway. almost like a mobile automaton or turring machine. so in some sense we are reading the current time as well as the past to create a new past.
does this makes sense?
thanks for the questions.
[edit: maybe its much simpler to understand if i say that it is almost similar a sideways evolution, like the (b) one on page 604 in Wolfram's NKS book. the difference that the evolution goes in the idirection rather than timedirection t and the formula used is not wolfram's typical Rule 30 formula: p xor (pq) but the reversibleformula in my document  i might have to test it a few times, because i am not sure if i got all the notation right in that doc. however it behaves similar to rule 89 because ive testet that in my simulation. and besides the one in page 604, it's of course just one string of information initially, no more.]
Sorry about not have written to much backgroundinformation, i will do that in a more comprehensive document like i said earlier, just havent gotten around making the document complete yet.
You have the information  let's say you have only one configuration, but the past are gone, there is just a white background except for your current configuration. Let's say that this lies on t=0.
I will refer to as spacesteps as when i decreases by one (i=i1) which has nothing to do with timesteps (t=t1).
We will calculate the new cell at t1, a(i1).
At the first decrypting sequence a'(i) the configuration lies (the one you got) are on time t=0. a(i1), a(i) and a(i+1) are all 0 before the first spacestep. on the next spacestep (that is i1) the a(i) might be black or white depending on the a'(i1) state after the first spacestep. we know that the first and last few cells are black because of the borders on rule 30, but in general when reading a'(i) where our configuration lies there might be 0 or 1 depending on the rule 86 truth table (or the formula used, which is kind of a mirror of the truth table). combining these values that gets fed into the a(i1), a(i) and a(i+1) with the previous configuration a'(i) one determines the output a(i1). so yes, its one extra dimension a'(i). when the configurationlength is complete time decreases by one. all this happens in discrete time anyway. almost like a mobile automaton or turring machine. so in some sense we are reading the current time as well as the past to create a new past.
does this makes sense?
thanks for the questions.
[edit: maybe its much simpler to understand if i say that it is almost similar a sideways evolution, like the (b) one on page 604 in Wolfram's NKS book. the difference that the evolution goes in the idirection rather than timedirection t and the formula used is not wolfram's typical Rule 30 formula: p xor (pq) but the reversibleformula in my document  i might have to test it a few times, because i am not sure if i got all the notation right in that doc. however it behaves similar to rule 89 because ive testet that in my simulation. and besides the one in page 604, it's of course just one string of information initially, no more.]
Last edited by rudi on Wed May 30, 2012 12:26 am UTC, edited 2 times in total.
Rudi
Re: Writing a paper about Cellular Automata
Shadowfish wrote:It sounds like rudi has noticed that some subset of initial conditions yield reversible dynamics for some number of iterations, and that the evolution starting from these initial conditions can be reversed in a straightforward way. This leads to the questions:
1) Will the CA evolve from a reversible state to an irreversible one?
2) Can we specify what subset of initial conditions yields reversible dynamics?
3) Is this result wellknown, or weaker than a wellknown result?
As an outsider to the CA world, it seems like rudi's algorithm might be interesting if these questions can be answered.
I hope someone could answer these quesions, because i dont want my algorithm to go to waste if they are usable in any way for other mathematicians and researchers.
Rudi
Re: Writing a paper about Cellular Automata
sorry people. i knew it, there's something missing in that doc. i forgot to say that i wrote this at night when i was very tired.
now i will correct the formulas in the doc.
a(i1) is calculated like this:
a(i1) = (a(i) AND (a(i+1)) xor a(i) xor a(i+1) xor a'(i)
if you look up that logic formula up in lets say wolfram alpha, then you will see that you get rule 86 as the rule to reverse the rule 30 pattern.
and if you look up the common rule 30 logic expression: "a xor (b or c)" you see that the algebraic normal form is exactly the same.
i've updated the doc: http://www.home.no/rudibs/Rule%2030%20reversibility.pdf
hope it's easier for you mathematicians to understand. also if its really bad to have use one extra dimension to produce past states, please tell me why.
hope that helps.
thanks for your patience.
now i will correct the formulas in the doc.
a(i1) is calculated like this:
a(i1) = (a(i) AND (a(i+1)) xor a(i) xor a(i+1) xor a'(i)
if you look up that logic formula up in lets say wolfram alpha, then you will see that you get rule 86 as the rule to reverse the rule 30 pattern.
and if you look up the common rule 30 logic expression: "a xor (b or c)" you see that the algebraic normal form is exactly the same.
i've updated the doc: http://www.home.no/rudibs/Rule%2030%20reversibility.pdf
hope it's easier for you mathematicians to understand. also if its really bad to have use one extra dimension to produce past states, please tell me why.
hope that helps.
thanks for your patience.
Rudi
 gmalivuk
 GNU Terry Pratchett
 Posts: 25975
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Writing a paper about Cellular Automata
Please don't post three times in a row. If you have something more to say, and your last post is still the latest in the thread, just edit it to include the new information.
Re: Writing a paper about Cellular Automata
One thing that should tell you that it's not reversible is the inverted triangles of 0s that rule 30 forms. They form when a section of the line is all 1s, which turns into all 0s on the next line. The sides then shrink over time (since both 100 and 001 map to 1), forming a triangle. In order to reverse that, since the triangles can be upwards of 20 cells wide at the top, your rule would have to map 001, 100, and 000 to 0, in order to have them stay at least the same width as time "decreases". Then, at some point, you'd have to have your line of 0s all turn into 1s, completing the triangle. This requires having 000 map to 111, but you can't do that since you need it to map to 0 in order to form the triangle in the first place.
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.
 gmalivuk
 GNU Terry Pratchett
 Posts: 25975
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Writing a paper about Cellular Automata
Rule 86 is a leftright mirror of Rule 30. This is not the same thing as a timereversal.rudi wrote:if you look up that logic formula up in lets say wolfram alpha, then you will see that you get rule 86 as the rule to reverse the rule 30 pattern.
Re: Writing a paper about Cellular Automata
sizik:
look at the information flow on fig 2 in the document. im not really a good explanator, but try and figure out how information flows from a(i1) to a(i) and a(i+1) at each spacestep. when a(i1) is determined to be for example 1, then at next spacestep a(i) is 1 and after the second space step a(i+1) is 1. based on the formula, they all produce 1's at at your particular problem. when they reach a border the formula behaves differently since a(i1) = (1 ^ 1) xor 1 xor 1 xor 1 = 0
dont know if that answered your question.
you could give me some last configuration of your Rule 30 pattern. I will try with my algorithm to reverse (produce the whole pyramid) and get back to your random/or defined initial configuration. I don't see any flaws at this time with my current formula. the pdf is updated once more. i found another small bug!
gmalivuk:
you cannot prove that it is not a timereversal algorithm. this formula intrinsincly generates the past reverse states of rule 30 states. rule 30 intrinsicly generates complex patterns forward in time, this formula does the opposite.
look at the information flow on fig 2 in the document. im not really a good explanator, but try and figure out how information flows from a(i1) to a(i) and a(i+1) at each spacestep. when a(i1) is determined to be for example 1, then at next spacestep a(i) is 1 and after the second space step a(i+1) is 1. based on the formula, they all produce 1's at at your particular problem. when they reach a border the formula behaves differently since a(i1) = (1 ^ 1) xor 1 xor 1 xor 1 = 0
dont know if that answered your question.
you could give me some last configuration of your Rule 30 pattern. I will try with my algorithm to reverse (produce the whole pyramid) and get back to your random/or defined initial configuration. I don't see any flaws at this time with my current formula. the pdf is updated once more. i found another small bug!
gmalivuk:
you cannot prove that it is not a timereversal algorithm. this formula intrinsincly generates the past reverse states of rule 30 states. rule 30 intrinsicly generates complex patterns forward in time, this formula does the opposite.
Rudi
 gmalivuk
 GNU Terry Pratchett
 Posts: 25975
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Writing a paper about Cellular Automata
If you apply 86 to the following, you definitely don't get the same thing I started with and applied rule 30 to:rudi wrote:you cannot prove that it is not a timereversal algorithm.
..., 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, ...
Like I said, 86 simply flips the result lefttoright. Try it with just a single central 1, and this is obvious.
Re: Writing a paper about Cellular Automata
gmalivuk:
im not sure if you're doing it wrong.
this is what i get:
so your initial configuration would be, afaik:
....0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,....
(zero in this case is always background).
pdf is updated. maybe its easier to understand what i do now.
im not sure if you're doing it wrong.
this is what i get:
so your initial configuration would be, afaik:
....0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,....
(zero in this case is always background).
pdf is updated. maybe its easier to understand what i do now.
Rudi
Re: Writing a paper about Cellular Automata
I'm going to guess gmalivuk started with ...0,0,1,1,1,1,1,1,1,1,0,0...
Also,
Is definitely NOT what you get if you apply rule 86 to ...0,1,1,0,1,1,1,0,1,0,1,1,0,1,1,1,1,0...
Also,
rudi wrote:
Is definitely NOT what you get if you apply rule 86 to ...0,1,1,0,1,1,1,0,1,0,1,1,0,1,1,1,1,0...
gmalivuk wrote:Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one metame to experience both body's sensory inputs.
Re: Writing a paper about Cellular Automata
Sizik:
You don't just apply rule 86 on the automaton like any other elementary ca. its a more dynamic algorithm than that.
But yea, i get your point. but sequences like ...0000000... or ...1111111... doesnt make any sense at all. for a rule 30 to produce these sequences, if they do at all.. the background would be the final result. the background is not possible to reverse, because it contains just one 1/2 bit state. but complex patterns are possible to reverse.
You don't just apply rule 86 on the automaton like any other elementary ca. its a more dynamic algorithm than that.
But yea, i get your point. but sequences like ...0000000... or ...1111111... doesnt make any sense at all. for a rule 30 to produce these sequences, if they do at all.. the background would be the final result. the background is not possible to reverse, because it contains just one 1/2 bit state. but complex patterns are possible to reverse.
Rudi
 gmalivuk
 GNU Terry Pratchett
 Posts: 25975
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Writing a paper about Cellular Automata
So it looks like you can't reverse the "background" (i.e. infinite strings of 0), nor can you reverse states with an infinite number of nonbackground cells (i.e. ones that aren't bordered by zeroes on both sides).rudi wrote:But yea, i get your point. but sequences like ...0000000... or ...1111111... doesnt make any sense at all. for a rule 30 to produce these sequences, if they do at all.. the background would be the final result. the background is not possible to reverse, because it contains just one 1/2 bit state. but complex patterns are possible to reverse.
It seems you can only reverse when you start with the assumptions that a'(j)=a(j)=0 for j>i, and a(i)=0. Otherwise how do you know where to start?
Re: Writing a paper about Cellular Automata
So it looks like you can't reverse the "background" (i.e. infinite strings of 0), nor can you reverse states with an infinite number of nonbackground cells (i.e. ones that aren't bordered by zeroes on both sides).
you can reverse infinite nonbackground cells. here is for example a history of a infinite cyclic system:
i drawn a yellow line because it seems that things happen and that there is some kind of hidden "border" between the background noise and the regular structures. it's tricky to know what this means at the moment, but those borders seem to increase/decrease by 3 because of the neighborhood length, r=1 perhaps. someone with more analytical knowledge than me should look into this area and see if there is something interesting to find.
It seems you can only reverse when you start with the assumptions that a'(j)=a(j)=0 for j>i, and a(i)=0. Otherwise how do you know where to start?
a'(i) can be anything. this is where the current configuration lies, for example t=0. a(i1) the determined cell, and a(i) and a(i+1) are t1. but t1 are initially background. after a space step, this background may either have 1 or 0 based on a'(i)'s state, but also a(i) and a(i+1)'s states of course, but since initially their states are all 0 a'(i)'s state are most important at first space step. [i use the word space step because i found it easy to use, what i mean is that i decreases].
[edit: you should know where to start, when a'(i) changes state. for example from 0 to 1].
I just first of all would like to thank everybody for their responses. and please make contact if you perhaps would like to contribute into a larger research project, if that even is something that can be done. ive allready thought about building a website where i should put this up. or even write a more comprehensive paper in the future, if that is necessary.
Rudi
 gmalivuk
 GNU Terry Pratchett
 Posts: 25975
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Writing a paper about Cellular Automata
Like I said: you assume those must be zero. Which means you're not actually able to uniquely reverse all possible configurations.rudi wrote:a(i) and a(i+1) are t1. but t1 are initially background
Sorry, I meant infinite in both directions, since you have to pick a rightmost position to start with.rudi wrote:you can reverse infinite nonbackground cells. here is for example a history of a infinite cyclic system:
Re: Writing a paper about Cellular Automata
Like I said: you assume those must be zero. Which means you're not actually able to uniquely reverse all possible configurations.
They are zero (background). Because there are no history until you actually compute that history based on a'(i).
Sorry, I meant infinite in both directions, since you have to pick a rightmost position to start with.
The question is do you really know where to start when something is infinite, can you pick somewhere on the infinite string, does it really matter?
Rudi
Who is online
Users browsing this forum: mashnut and 11 guests