[I need a demonstration for the universal computation of cellular automata] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


I need a demonstration for the universal computation of cellular automata

(Click here to view the original thread with full colors/images)


Posted by: bulgariu_emilian

I’m writing my license in computer science on the subject of Cellular Automata and I need a demonstration for the power of computation of Cellular Automata. I know that A.C. are equivalent with Turing Machine ("a one-dimensional cellular automata with k=18 and r=1 is equivalent to the simplest known universal Turing machines") but I need a demonstration. If you can help me with some links or some demonstrations, I thank you.


Posted by: Jason Cawley

See 658. That shows a general scheme for emulating any TM with a CA, using some colors to represent the tape and others to represent the position and state of the head. Apply the same scheme to any TM known to be universal, and you have a CA (in general, with many colors) that must be universal as well, since it directly emulates the behavior of a known universal system.




Forum Sponsored by Wolfram Research

© 2004-2008 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings