# pouët.net

## universal cellular automata or

category: code [glöplog]
added on the 2012-03-12 11:05:55 by rudi
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.
added on the 2012-03-14 16:15:41 by rudi
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.
added on the 2012-03-14 17:11:41 by rudi
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?
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.
added on the 2012-03-14 21:11:39 by rudi
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.
added on the 2012-03-14 23:27:19 by rudi
I believe the center column means... the center column:
Code:``` | .|. ..|.. ...|... ....|.... .....|..... ......|......```
added on the 2012-06-08 03:06:27 by texel
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.
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.