Writing a paper about Cellular Automata

For the discussion of math. Duh.

Moderators: gmalivuk, Prelates, Moderators General

Writing a paper about Cellular Automata

Postby rudi » Sun Mar 18, 2012 7:26 pm UTC

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 bachelor-studies 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Au

Postby tomtom2357 » Mon Mar 19, 2012 2:23 pm UTC

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.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Writing a paper about Cellular Au

Postby Yakk » Mon Mar 19, 2012 7:21 pm UTC

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 over-estimation and the Dunning–Kruger effect:
Spoiler:
Most people who are not academically inclined seriously over estimate their abilities at the subject area in question. One of the things that happens as you advance up the academic slope is that there are serious amounts of culling, and at each stage (mostly) the people who where really good at the previous stage are the ones left standing. By the time you even get your first tenure track job, you have the high-school cull, the early university cull, the finish university cull, starting grad school cull, the finishing your PhD culls, the getting a good post-doc cull, then the getting a tenure track job cull. Many of these culls are not solely based on intelligence or aptitude at the subject (self motivation ends up being rather important), but the output tends to be pretty expert cookies, who have spent sometimes north of 10,000 hours thinking (with help!) about an increasingly specialized part of science.

Ie: the odds are that what you are thinking isn't all that extraordinary. If you have an inclination to keep it secret, that inclination is almost certainly wrong. The world is full of people who have a "great idea" that they thought about and worked on really hard and, due to the effort in figuring it out, they don't want to share it: in my experience, such people very rarely actually have a particularly "great idea". Academia gets around this problem (of hording ideas) by rating people by what they share, rather than what they keep secret.

My advice to you is to accept that your idea almost certainly isn't all that revolutionary, and instead of going about it in a secret backwards way, try sharing it openly and seeing if people can help you understand what it means. Ie, instead of asking "what is a proof", you could ask for help proving your particular algorithm does what you think it does. The alternative approach is pretty much to start reading introductory textbooks on proving things in your domain of interest (like an undergrad would), and start with spending a few 100 hours learning how to prove easy things and how to read proofs, then move on up to intermediate texts, or even easy to read journal articles. You aren't going to become an expert at "writing a proof" from much less effort than this.

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 high-worth 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.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10372
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Writing a paper about Cellular Au

Postby rudi » Mon Mar 19, 2012 8:38 pm UTC

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? :D 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 public-key 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 :P).
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Au

Postby Meem1029 » Tue Mar 20, 2012 4:23 am UTC

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.
cjmcjmcjmcjm wrote:If it can't be done in an 80x24 terminal, it's not worth doing
Meem1029
 
Posts: 378
Joined: Wed Jul 21, 2010 1:11 am UTC

Re: Writing a paper about Cellular Au

Postby ++$_ » Tue Mar 20, 2012 4:53 am UTC

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.
++$_
Mo' Money
 
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Writing a paper about Cellular Au

Postby snowyowl » Wed Mar 21, 2012 8:02 pm UTC

Meem is right. If you have code that does something previously thought impossible - or even pseudocode, that is human-readable but not actually written in a programming language - then post it so we can give it the once-over. 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.
User avatar
snowyowl
 
Posts: 452
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Writing a paper about Cellular Au

Postby lightvector » Thu Mar 22, 2012 2:15 am UTC

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.
lightvector
 
Posts: 196
Joined: Tue Jun 17, 2008 11:04 pm UTC

Re: Writing a paper about Cellular Au

Postby ahammel » Thu Mar 22, 2012 2:27 am UTC

If you're interested in learning what goes in to a math or CS paper, why not read some? Since you've got some post-secondary 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.
I also answer to 'Alex'

YES, IT'S SPACEY-WACEY!
User avatar
ahammel
My Little Cabbage
 
Posts: 1434
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC

Re: Writing a paper about Cellular Au

Postby rudi » Thu Mar 22, 2012 9:01 am UTC

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, error-corrections and the like. i will try and find some info on how mathematicians write pseudo-code 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Au

Postby Meem1029 » Thu Mar 22, 2012 12:21 pm UTC

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
Meem1029
 
Posts: 378
Joined: Wed Jul 21, 2010 1:11 am UTC

Re: Writing a paper about Cellular Au

Postby ahammel » Thu Mar 22, 2012 3:01 pm UTC

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, error-corrections 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.
I also answer to 'Alex'

YES, IT'S SPACEY-WACEY!
User avatar
ahammel
My Little Cabbage
 
Posts: 1434
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC

Re: Writing a paper about Cellular Au

Postby rudi » Thu Mar 22, 2012 3:56 pm UTC

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.
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Au

Postby ahammel » Thu Mar 22, 2012 4:27 pm UTC

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 also answer to 'Alex'

YES, IT'S SPACEY-WACEY!
User avatar
ahammel
My Little Cabbage
 
Posts: 1434
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC

Re: Writing a paper about Cellular Au

Postby rudi » Thu Mar 22, 2012 5:14 pm UTC

ahammel: thanks
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Mon May 28, 2012 1:05 am UTC

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 spelling-errors 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 3-cells to determine the left one (a(i-1)).

now i want feedback, questions, bugs, error-corrections and the like. i really want to hear what you say about this.

Rudi
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby tomtom2357 » Mon May 28, 2012 7:53 am UTC

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.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Mon May 28, 2012 12:55 pm UTC

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]
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby OverBored » Mon May 28, 2012 1:39 pm UTC

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.
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.
User avatar
OverBored
 
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Mon May 28, 2012 4:28 pm UTC

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 non-cyclic 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(i-1)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.

Image
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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby OverBored » Mon May 28, 2012 5:56 pm UTC

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.
User avatar
OverBored
 
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Mon May 28, 2012 6:55 pm UTC

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.
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Mon May 28, 2012 6:56 pm UTC

thanks for the replies anyhow :)
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby Qlexander » Mon May 28, 2012 7:04 pm UTC

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(i-1). 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?
Qlexander
 
Posts: 2
Joined: Mon May 28, 2012 6:51 pm UTC

Re: Writing a paper about Cellular Automata

Postby Shadowfish » Mon May 28, 2012 7:24 pm UTC

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 well-known, or weaker than a well-known 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.
Shadowfish
 
Posts: 309
Joined: Tue Feb 27, 2007 2:27 am UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Tue May 29, 2012 10:01 pm UTC

Qlexander:

Sorry about not have written to much background-information, 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 space-steps as when i decreases by one (i=i-1) which has nothing to do with time-steps (t=t-1).
We will calculate the new cell at t-1, a(i-1).

At the first decrypting sequence a'(i) the configuration lies (the one you got) are on time t=0. a(i-1), a(i) and a(i+1) are all 0 before the first space-step. on the next space-step (that is i-1) the a(i) might be black or white depending on the a'(i-1) state after the first space-step. 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(i-1), a(i) and a(i+1) with the previous configuration a'(i) one determines the output a(i-1). so yes, its one extra dimension a'(i). when the configuration-length 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 i-direction rather than time-direction t and the formula used is not wolfram's typical Rule 30 formula: p xor (p|q) but the reversible-formula 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Tue May 29, 2012 10:03 pm UTC

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 well-known, or weaker than a well-known 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Wed May 30, 2012 12:39 am UTC

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(i-1) is calculated like this:

a(i-1) = (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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby gmalivuk » Wed May 30, 2012 3:56 pm UTC

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.
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 22000
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: Writing a paper about Cellular Automata

Postby Sizik » Wed May 30, 2012 4:00 pm UTC

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:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.
User avatar
Sizik
 
Posts: 774
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Writing a paper about Cellular Automata

Postby gmalivuk » Wed May 30, 2012 4:28 pm UTC

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.
Rule 86 is a left-right mirror of Rule 30. This is not the same thing as a time-reversal.
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 22000
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: Writing a paper about Cellular Automata

Postby rudi » Wed May 30, 2012 4:49 pm UTC

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(i-1) to a(i) and a(i+1) at each space-step. when a(i-1) is determined to be for example 1, then at next space-step 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(i-1) = (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 time-reversal 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby gmalivuk » Wed May 30, 2012 5:16 pm UTC

rudi wrote:you cannot prove that it is not a time-reversal algorithm.
If you apply 86 to the following, you definitely don't get the same thing I started with and applied rule 30 to:

..., 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 left-to-right. Try it with just a single central 1, and this is obvious.
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 22000
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: Writing a paper about Cellular Automata

Postby rudi » Wed May 30, 2012 7:10 pm UTC

gmalivuk:

im not sure if you're doing it wrong.
this is what i get:

Image

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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby Sizik » Wed May 30, 2012 7:51 pm UTC

I'm going to guess gmalivuk started with ...0,0,1,1,1,1,1,1,1,1,0,0...

Also,
rudi wrote:Image


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:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.
User avatar
Sizik
 
Posts: 774
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Writing a paper about Cellular Automata

Postby rudi » Wed May 30, 2012 7:57 pm UTC

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.
Rudi
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby gmalivuk » Wed May 30, 2012 9:21 pm UTC

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.
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 non-background cells (i.e. ones that aren't bordered by zeroes on both sides).

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?
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 22000
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: Writing a paper about Cellular Automata

Postby rudi » Thu May 31, 2012 12:56 am UTC

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 non-background cells (i.e. ones that aren't bordered by zeroes on both sides).


you can reverse infinite non-background cells. here is for example a history of a infinite cyclic system:

Image

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(i-1) the determined cell, and a(i) and a(i+1) are t-1. but t-1 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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Re: Writing a paper about Cellular Automata

Postby gmalivuk » Thu May 31, 2012 1:55 am UTC

rudi wrote:a(i) and a(i+1) are t-1. but t-1 are initially background
Like I said: you assume those must be zero. Which means you're not actually able to uniquely reverse all possible configurations.

rudi wrote:you can reverse infinite non-background cells. here is for example a history of a infinite cyclic system:
Sorry, I meant infinite in both directions, since you have to pick a rightmost position to start with.
Treatid basically wrote:widdout elephants deh be no starting points. deh be no ZFC.


(If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome)
User avatar
gmalivuk
A debonaire peeing style
 
Posts: 22000
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There

Re: Writing a paper about Cellular Automata

Postby rudi » Thu May 31, 2012 3:51 pm UTC

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
rudi
 
Posts: 23
Joined: Sun Mar 18, 2012 7:06 pm UTC

Next

Return to Mathematics

Who is online

Users browsing this forum: Izawwlgood and 14 guests