universal cellular automata or
category: code [glöplog]
http://www.zimuel.it/talks/Nks2006.pdf
its really frustrating to read. altho, my algorithm is purely based on CA, i havent tested it on large number of cells. and another thing is that i dont have any ph.d in mathematics or something to actually write a paper about this. which sucks.
its really frustrating to read. altho, my algorithm is purely based on CA, i havent tested it on large number of cells. and another thing is that i dont have any ph.d in mathematics or something to actually write a paper about this. which sucks.
quote from: http://www.knowledgerush.com/kr/encyclopedia/Cellular_automaton/
Quote:
Rule 30 was originally suggested as a possible stream cipher for use in cryptography.
Cellular automata have been proposed for public key cryptography. The one way function is the evolution of a finite CA whose inverse is hard to find. Given the rule, anyone can easily calculate future states, but it is very difficult to calculate previous states. However, the designer of the rule can create it in such a way as to be able to easily invert it. Therefore, it is a trapdoor function, and can be used as a public-key cryptosystem. The security of such systems is not currently known.
This is a very interesting thread!
Note that in your example, the number of cells in a line increases with 2 each line. A lot of the generators I've seen have a maximum width, and just drop the new cells at the edge. That would make total decryption impossible. Is partial decryption still possible?
Some generators wrap around the borders when the line reaches maximum length. How does this affect the possibility to decrypt?
Note that in your example, the number of cells in a line increases with 2 each line. A lot of the generators I've seen have a maximum width, and just drop the new cells at the edge. That would make total decryption impossible. Is partial decryption still possible?
Some generators wrap around the borders when the line reaches maximum length. How does this affect the possibility to decrypt?
whynot2000: i havent tested it on edges, so i dont know yet. i would guess that the information gets lost in the way. but i would also guess that in a encryption scheme, if they hit the edges, it doesnt really matter nor if it is wrapped. the inversion technique should do exactly the opposite to the encryption, then doing exactly the opposite of the edges. i would need some more research to actually say that i have a solution to this thing. what i can say is that you dont need the whole last configuration. you only need half of it.
http://www.stephenwolfram.com/publications/recent/nksmain/
Quote:
Well, back in physics one place randomness has been discussed a lot is the Second Law of Thermodynamics--the law of entropy increase. A lot is known about it, but there's still a basic mystery about how the laws of physics can be reversible, yet in our everyday experience we see so much apparent irreversibility. And I think that intrinsic randomness generation finally gives one a way to explain that. It's a slightly long story, but it's basically that things like rule 30 can so encrypt the data associated with initial conditions that no realistic experiments or observations can ever decode it to see how to go backwards.
I believe the center column means... the center column:
Code:
|
.|.
..|..
...|...
....|....
.....|.....
......|......
I've searched the BBS for "Wolfram", and found this thread (as well as thread #8815). I am now also reading Stephen Wolfram's "A New Kind Of Science", which is probably what inspired rudi to starting this thread, and I was looking for a thread here dealing with it since, obviously, what Wolfram is going on about can also be used for demos.
I am roughly on page 150, so I am still far from having finished reading this book. We will see whether it will eventually serve as some sort of inspiration.
I am roughly on page 150, so I am still far from having finished reading this book. We will see whether it will eventually serve as some sort of inspiration.
Regarding the emulation of Boolean operators by means of NAND:
NAND(x,y) = 0 <=> x = y = 1
NAND(x,y) = 1 <=> x = 0 OR y = 0
Therefore:
NOT:
NAND(x,x) = 0 <=> x = 1
NAND(x,x) = 1 <=> x = 0
AND:
NAND(NAND(x,y),NAND(x,y)) = 0 <=> x = 0 OR y = 0
NAND(NAND(x,y),NAND(x,y)) = 1 <=> x = y = 1
OR:
NAND(NAND(x,x),NAND(y,y)) = 0 <=> x = y = 0
NAND(NAND(x,x),NAND(y,y)) = 1 <=> x = 1 OR y = 1
It is analogous with NOR.
NOR(x,y) = 0 <=> x = 1 OR y = 1
NOR(x,y) = 1 <=> x = y = 0
The crucial point about this is that the operations NAND and NOR require in one case both parameters to be the opposite of the result, and in the other case they require at least one of the two parameters to be the opposite of the result.
With AND and OR the parameters are in one case both the same as the result, in the other case at least one of them is the same as the result.
Apparently it is necessary to be able to "flip" values (i.e. get a result different from at least one of the two parameters) to be able to emulate all other Boolean operations; therefore it is possible to emulate all other Boolean operations using NAND or NOR, but not using AND or OR.
With XOR, XOR(0,0) = 0; so the value is not "flipped". That seems to be the reason why it is not possible to use XOR to emulate all other Boolean operations.
NAND(x,y) = 0 <=> x = y = 1
NAND(x,y) = 1 <=> x = 0 OR y = 0
Therefore:
NOT:
NAND(x,x) = 0 <=> x = 1
NAND(x,x) = 1 <=> x = 0
AND:
NAND(NAND(x,y),NAND(x,y)) = 0 <=> x = 0 OR y = 0
NAND(NAND(x,y),NAND(x,y)) = 1 <=> x = y = 1
OR:
NAND(NAND(x,x),NAND(y,y)) = 0 <=> x = y = 0
NAND(NAND(x,x),NAND(y,y)) = 1 <=> x = 1 OR y = 1
It is analogous with NOR.
NOR(x,y) = 0 <=> x = 1 OR y = 1
NOR(x,y) = 1 <=> x = y = 0
The crucial point about this is that the operations NAND and NOR require in one case both parameters to be the opposite of the result, and in the other case they require at least one of the two parameters to be the opposite of the result.
With AND and OR the parameters are in one case both the same as the result, in the other case at least one of them is the same as the result.
Apparently it is necessary to be able to "flip" values (i.e. get a result different from at least one of the two parameters) to be able to emulate all other Boolean operations; therefore it is possible to emulate all other Boolean operations using NAND or NOR, but not using AND or OR.
With XOR, XOR(0,0) = 0; so the value is not "flipped". That seems to be the reason why it is not possible to use XOR to emulate all other Boolean operations.
Quote:
I am now also reading Stephen Wolfram's "A New Kind Of Science", which is probably what inspired rudi to starting this thread, and I was looking for a thread here dealing with it since, obviously, what Wolfram is going on about can also be used for demos.
I was inspired in 2003 while taking computer science at college. Since the classes was so boring I did some experiments on my own. I looked at the simple rules on a 1-dimensional line just like Wolfram did back then. I asked some persons on IRC if they've seen rule 30 and 110 before. Yes! They told me that Wolfram had allready. Thanks to that, I buyed his book 7 years later.