BBM: Turing Complete?

For discussion of other cellular automata.
Post Reply
Ivan
Posts: 8
Joined: August 13th, 2011, 2:22 pm

BBM: Turing Complete?

Post by Ivan » August 21st, 2011, 12:16 pm

Wiki: http://en.wikipedia.org/wiki/Billiard-Ball_Computer

A Billiard Ball Computer is is a computer based in the Billiard ball model, that can
be simulated with the Margolus neighborhood. I have built the AND gate shown
in the page: ( It is rotated 45 degrees )

Code: Select all

x = 98, y = 69, rule = BBM-Margolus-emulated
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABAB$98B$ABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB$98B$A
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABAB$98B$ABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB$38B2D
10B2D46B$ABABABABABABABABABABABABABABABABABABABCDCBABABABADCDABABABAB
ABABABABABABABABABABABABABABABABABABAB$39B3D6B3D47B$ABABABABABABABABA
BABABABABABABABABADCBCBCDCBABADCDABADCBABABABABABABABABABABABABABABAB
ABABABABABAB$35B3D3B3D2B3D3B3D43B$ABABABABABABABABABABABABABABABABABA
BCDCBCBCDCDCDABADCDABABABABABABABABABABABABABABABABABABABABABAB$37B3D
3B4D3B3D45B$ABABABABABABABABABABABABABABABABABABABCDCBABABABADCDABABA
DCBABABABABABABABABABABABABABABABABABABAB$39B3D6B3D5B3D39B$ABABABABAB
ABABABABABABABABABABABABABABABCDABABABCDCBABADCDABABABABABABABABABABA
BABABABABABABABABAB$40B2D7B3D2B3D3B2D36B$ABABABABABABABABABABABABABAB
ABABABABABADCDABABABABCDCDCDABADCDABABABABABABABABABABABABABABABABABA
B$38B3D10B4D3B3D37B$ABABABABABABABABABABABABABABABABABABADCDABADCBABA
BABCDABADCDABABABABABABABABABABABABABABABABABABAB$36B3DBDB4D10B3D39B$
ABABABABABABABABABABABABABABABABABADCDABADCDCDCBABABABADCDABABABABABA
BABABABABABABABABABABABABABAB$35B2DBDB3D2B3D7B2D41B$ABABABABABABABABA
BABABABABABABABABABABADCDABABCDCBABABADCBABABABABABABABABABABABABABAB
ABABABABABAB$38B3D6B3D5B3D40B$ABABABABABABABABABABABABABABABABABABABC
DABABABABCDCBABABCDCBABABABABABABABABABABABABABABABABABABAB$49B5D3B3D
38B$ABABABABABABABABABABABABABABABABABABABABABABABABABCDCDCBABCDCBABA
BABABABABABABABABABABABABABABABAB$53B3D3B3D36B$ABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABCDCBABCDABABABABABABABABABABABABABABA
BABABAB$55B3D40B$ABABABABABABABABABABABABABABABABABABABABABABABABABAB
ABABCDCBABABABABABABABABABABABABABABABABABABAB$57B2D39B$ABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABAB$98B$ABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABABABABABABABABABABABABABABABABABAB$98B$ABABABABABABAB
ABABABABADCBABABABABADCBABABABABABABABABABABADCBABABABABADCBABABABABA
BABABABABABABAB$23B3D8B3D22B3D8B3D25B$ABABABABABABABABABABABCBCDCBABA
BADCDABABABABABABABABABABABABCDCBABABADCDABABABABABABABABABABABABAB$
20B2D3B3D4B3D3B2D16B2D3B3D4B3D3B2D22B$ABABABABABABABABABABCDCBCBCDCBA
DCDABADCDABABABABABABABABCDCBABCDCBADCDABADCDABABABABABABABABABABAB$
21B3D3B6D3B3D18B3D3B6D3B3D23B$ABABABABABABABABABABABCDCBABCDCDABADCDA
BABABABABABABABABABCDCBABCDCDABADCDABABABABABABABABABABABAB$23B3D8B3D
5B2D15B3D8B3D5B2D18B$ABABABABABABABABABABABABCDCBABABADCDABABADCDABAB
ABABABABABABCDCBABABADCDABABADCDABABABABABABABABAB$25B2D6B3D4B3D18B2D
6B3D4B3D19B$ABABABABABABABABABABABABADCBABABABCDCBADCDABADCBABABABABA
BABADCBABABABCDCBADCDABADCBABABABABABABAB$24B3D8B6D3B3D13B3D8B6D3B3D
15B$ABABABABABABABABABABABADCDABABABABABCDCDABADCDABABABABABABADCDABA
BABABABCDCDABADCDABABABABABABABAB$22B3D3B2D7B2D3B3D13B3D3B2D7B2D3B3D
17B$ABABABABABABABABABABADCDABADCDCBABABABABADCDABABABABABABADCDABADC
DCBABABABABADCDABABABABABABABABAB$20B3D3B6D8B3D13B3DBDB6D8B3D19B$ABAB
ABABABABABABABABCDABADCDABCDCBABABABCDABABABABABABABCDABADCDABCDCBABA
BABCDABABABABABABABABABAB$24B3D4B3D6B2D16BDB3D4B3D6B2D20B$ABABABABABA
BABABABABABADCDABABABCDCBABABCDCBABABABABABABABADCDABABABCDCBABABCDCB
ABABABABABABABABAB$23B2D8B3D5B3D15B2D8B3D5B3D18B$ABABABABABABABABABAB
ABABABABABABABCDCDCBABCDCBABABABABABABABABABABABABCDCDCBABCDCBABABABA
BABABABAB$35B5D3B3D25B5D3B3D16B$ABABABABABABABABABABABABABABABABABABA
BCDCBABCDCBABABABABABABABABABABABABABCDCBABCDCBABABABABABABAB$39B3D3B
2D28B3D3B2D15B$ABABABABABABABABABABABABABABABABABABABABCDCBABABABABAB
ABABABABABABABABABABABCDCBABABABABABABABABAB$41B3D33B3D18B$ABABABABAB
ABABABABABABABABABABABABABABABABCDABABABABABABABABABABABABABABABABABC
DABABABABABABABABAB$98B$ABABABABABABABABABABABABABABABABABABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABABABAB$98B$ABABABABABA
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB
ABABABABABABABABAB!
Unfortunately, a NOT gate should be impossible, because BBM is conservative (the number of white dots never change), and that would require something like a billiard ball gun. Not really! We can use another notation for representing numbers, where a single signal can represent a continuos stream of bits. Example:

Code: Select all

x = 63, y = 51, rule = BBM-Margolus-emulated
63B$ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABA$
10B2D51B$ABABABABABCDCBABABABABABABABABABABABABABABABABABABABABABABAB
ABA$11B3D49B$ABABABADCBABCDCBABABABABABABABABABABABABABABABABABABABAB
ABABABA$7B3D3B3D47B$ABABABABCDCBABCDCBABABABABABABABABABABABABABABABA
BABABABABABABA$4B2D3B3D3B3D45B$ABABCDCBCBCDCBABCDCBABABABABABABABABAB
ABABABABABABABABABABABABA$5B3D3B3D3B3D43B$ABABABCDCBCBCDCBABCDCBABABA
BABABABABABABABABABABABABABABABABABA$7B3D3B3D3B3D41B$ABABABABCDCBABCD
CBABCDCBABABABABABABABABABABABABABABABABABABABA$9B3D3B3D3B3D39B$ABABA
BABABCDCBABCDCBABCDCBABABABABABABABABABABABABABABABABABABA$11B3D3B3D
3B3D37B$ABABABABABABCDCBABCDCBABCDCBABABABABABABABABABABABABABABABABA
BA$13B3D3B3D3B3D35B$ABABABABABABABCDCBABCDCBCBCDCBABABABABABABABABABA
BABABABABABABA$15B3D3B3D3B3D33B$ABABABABABABABABCDCBABCDCBCBCDCBABABA
BABABABABABABABABABABABABA$17B3D3B3D3B3D31B$ABABABABABABABABABCDCBABC
DCBABCDCBABABABABABABABABABABABABABABA$19B3D3B3D3B3D29B$ABABABABABABA
BABABABCDCBABCDCBABCDCBABABABABABABABABABABABABABA$21B3D3B3D3B3D27B$A
BABABABABABABABABABABCDCBABCDCBABCDCBABABABABABABABABABABABABA$23B3D
3B3D3B3D25B$ABABABABABABABABABABABABCDCBABCDCBABCDCBABABABABABABABABA
BABABA$25B3D3B3D3B3D23B$ABABABABABABABABABABABABABCDCBABCDCBABCDCBABA
BABABABABABABABABA$27B3D3B3D3B3D21B$ABABABABABABABABABABABABABABCDCBC
BCDCBABCDCBABABABABABABABABABA$29B3D3B3D3B3D19B$ABABABABABABABABABABA
BABABABABCDCBCBCDCBABCDCBABABABABABABABABA$31B3D3B3D3B3D17B$ABABABABA
BABABABABABABABABABABABCDCBABCDCBABCDCBABABABABABABABA$33B3D3B3D3B3D
15B$ABABABABABABABABABABABABABABABABABCDCBABCDCBCBCDCBABABABABABABA$
35B3D3B3D3B3D13B$ABABABABABABABABABABABABABABABABABABCDCBABCDCBCBCDCB
ABABABABABA$37B3D3B3D3B3D11B$ABABABABABABABABABABABABABABABABABABABCD
CBABCDCBABCDABABABABABA$39B3D3B3D15B$ABABABABABABABABABABABABABABABAB
ABABABABCDCBCBCDCBABABABABABABA$41B3D3B2D14B$ABABABABABABABABABABABAB
ABABABABABABABABABCDCBCBABABABABABABABA$43B3D17B$ABABABABABABABABABAB
ABABABABABABABABABABABABCDABABABABABABABABA$63B!
Means 011100011110...

Now we can make a NOT gate!
Just swap streams of 1s with streams of 0s.

Code: Select all

x = 36, y = 35, rule = BBM-Margolus-emulated
36B$ABABABABADCBABABABABABABABABABABABAB$9B3D24B$ABABABABCBCDCBABABAB
ABABABABABABABAB$6B2D3B3D22B$ABABADCDCBCBCDCBABADCDCBABABABABABAB$5B
5D3B3D2B6D12B$ABABCBCDCDCBABCDADCDABCDCBABABABABAB$2B2D3B4D3B5D4B3D
10B$ABCDCBCBCDABADCDCDABABABCDCBABABABAB$3B3D6B5D3B2D3B3D8B$ABABCDCBA
BADCDCDABADCDCBABCDCBABABAB$4B3D4B4D3B6D3B2D7B$ABADCDABABABCDABADCDCD
CDABADCBABABAB$2B3D3B2D6B7D3B3D7B$ABCDABADCDCBABADCDCDCDABADCDABABABA
B$2B2D3B5D2B7D3B3D9B$ABCDCBABCDCDCDCDCDCDCBABCDCBABABABAB$3B3D3B13D3B
3D8B$ABABCDCBABCDCDCDABCDCDCBABCDCBABABAB$5B3D3B4D4B5D3B2D7B$ABABABCD
CBABCDABABABCDCDCBABABABABAB$7B3D6B2D3B5D10B$ABABABABCDCBABADCDCBABCD
CDABABABABAB$9B3D2B6D3B2D11B$ABABABABABCDCDCDABCDCBABABABABABABAB$11B
4D4B2D15B$ABABABABABABABABABABABABABABABABABAB$36B$ABABABABABABABABAB
ABABABABABABABABAB$36B$ABABABABABABABABABABABABABABABABABAB$36B$ABABA
BABABABABABABABABABABABABABABAB$36B!
That's good but... this new notation will require much more complex AND gates!

...

OK, I have not implemented the AND gate yet, but I will post when it's ready. But if you discover anything interesting or useful about this rule please post here.

PS: I'm new on this community so if I did something wrong please don't say things like "you idiot" etc.

PSS: Sorry for bad English, not my first language.

EDIT: The NOT gate works only at low frequencies!

APerson241
Posts: 4
Joined: August 27th, 2011, 5:34 pm
Location: Somewhere in the western or eastern United States

Re: BBM: Turing Complete?

Post by APerson241 » August 29th, 2011, 11:30 am

Hmmm...

Is it possible to emulate a non-Turing machine computer using the Margolus family?

Johnicholas
Posts: 10
Joined: August 23rd, 2011, 4:28 pm

Re: BBM: Turing Complete?

Post by Johnicholas » August 29th, 2011, 8:31 pm

You might enjoy: "Predicting Lattice Gases is P-complete" by Moore and Nordahl

http://tuvalu.santafe.edu/~moore/pubs/lgas.html

Ivan
Posts: 8
Joined: August 13th, 2011, 2:22 pm

Re: BBM: Turing Complete?

Post by Ivan » August 31st, 2011, 12:58 pm

Tofolli investigated the billiard ball model. Here is what I've found: http://www.cs.unb.ca/profs/gdueck/cours ... rs/BBM.pdf.

Post Reply