pouët.net

can the xor operator be used to make universal arithmetic operations?
it looks like rule 30 is doing xor operations. any math-wiz done any research on this or?
i just made those shitty CA-patterns, but it seems like they're not very good. especially visually, when looking at the rules that are odd-numbers those change state on each column, so they're not pretty to look at. and there are only two of the CA- that i can look at, that is rule 30 and rule 110. except for one of the rules that makes some kind of a pascal triangle, but anyway.

also i wonder what kind of structure the xor-operator in cpu's, what kind of operations they do. if they are the same as some of the simple CA's ive found here.

AFAIK not.
You need AND, OR, NOT to build all possible binary operations.
(NOR or NAND would be enough - one can build AND, OR, NOT from NOR or NAND only but not from XOR only iirc).

Straight from Wikipedia:




So, go with rule 110 and build a tuuring machine from it and do everything.

the strange thing is that by using a simple CA, with random initial conditions you can get a pattern that looks kinda like Rule 30. it produces same output by using a xor-operator, and a xor-operator is never used in the computations but it produces the results anyway.

here's a pic:

what las said, you need NOT and OR or NOT and AND

Now if you only have XOR
X XOR 1 = NOT X
(x^0xffffffff = ~x)
so we have the NOT part covered
But you can't reproduce a OR or AND with XOR gates no matter how hard you. You can only get NXOR.

In your CPU there are so called XOR gates made out of transistors. When the appropriate instruction is read the data from selected registers is routed to these gates and their output is loaded into another register. Something like this but I'm not sure on this one...

XOR is not a magic operator that cures cancer. What it does is that it compares if two bits are different.

But there are some neat properties such as
x^x == 0 // will be always true
x=x^y; y=x^y; x=x^y; //value swap without using 3rd varible
x=x^a; /* will change x to different value */ x=x^a; //when you do it the second time x gets his original value back.

this is rule 6 from a cellular automaton that only have 2^4 amount of rules. which only checks two neighbours instead of three.

mu6k: ok, ill try understanding more about what you just said.

anyway, the rule above was to be drawn in paint looks like this:
its very simple:

say val is the neighbours:


you set the cells below the two neighbours:


if rule = 6 then you get xor-operations,
because if you replace the above code-line with this



you get same result.

i wonder if they use this technique in their xor-gates. it should be a pretty good way of CA's to produce xor-operations atleast :P

bah. so, working on a xor-decryption algorithm. just have to do it because i just happens to be there right now :S

funny, by looking at my picture from yesterday it looks like a xor truth table. and that is really what it is. lol. so, the cellular automata is just really a backdrop for the computations that can be done with this operator. now i am trying to figure out the two first cells that are important for reverse-engineering the xor operator. it really seems that there are two possibilities. and that when using either one, the other one will be mirrored.
havent done any code yet, but i will in near future. just had plottet alot of stuff on some papers.

i think i can prove that the xor operator is universal. i just really wonder about it because ive written all this stuff down. and now, i have these strange things happening with that. but perhaps i should read about what universal means before i say anything like that.. hmm.

Sounds like homework

XOR isn't an universal gate, but you're welcome to try to prove otherwise.

some of my notes. some of it is just scribbled stuff that is wrong, and should be erased. but some of it is on its right track. its some ideas. some of it is sensible stuff. the whole point is that it should be simple. because it is. i have scribbled down some new stuff that is not in there though. some very interresting things in it too..

page 1


page 2


page 3

some i also get into direction of rule 77 or rule 89 to decode the xor pattern
that is 1001101 = 77 or 1011001 = 89, because its unknown which mirror it is.
for this rule one can decode it, but one thing that is also unknown is the state of the first cell.

If I recall correctly, a constant 1 or 0 + NAND or NOR is enough to be universal. 1 or 0 can be inverted to produce the other. Nand/nor is arbitrary. Pick your poison.

Xor as well as xor + a constant is not enough, because you can't create and/or/nand/nor from it. xor + nand/nor is enough to be universal, since you could create a constant from (x xor x) which would always be 0.

Of course, in reality, chip designers physically have nor/nand/not and 0/1 at their disposal, (those are the smallest gates you can consutruct with transistors) so xor is a complex gate built from 4 nands or 5 nors.

one will be able to get the result anyway. because even if it is mirrored the whole cellular automata. the patterns will look the same. the only difference in our senses is the voltages that are being used to represent zero and one. it could have been one and zero for that matter. so.

nitro2k01: well. with a cellular automata model like this, you dont need 4 nands or 5 nors or whatever to construct a xor-gate, like you say to get result of a xor operation. you only need shift by a two-bit value and check the first bit. you use two xor-gates for the two bit values, or do it with electrons / quantum computing or whatever. it may be too slow by the operations used in cpu's today, i dont know how slow shifts are, but it is not what concerns me with what im trying to achieve here. and no, i dont say that it is universal, because i have no proof. it might just be unprovable but that doesnt stop me from working more on this.

hm. excuse me. rule 77 or rule 89 was wrong. the bit values here where random. i need to see if i am able to get them into a structure and check them again.

i get rule 60.

rule 34 - no exceptions

What others say about NOR / NAND. The latter was called Scheffer stroke IIRC, also my father was working as a microelectronician and was constantly using NAND gates.

As for visual aspect of cellular automaton, i added randomness:

rndcell