Hacker News new | past | comments | ask | show | jobs | submit login

Is it Turing complete?



I'd bet it is, but I imagine it would be really hard to prove. The original turing-completeness proof [1] for discreet cellular automata worked by setting up some predictable repeating patterns and then using these to encode a representation of some other simple machine that was known to be turing-complete. Getting anything repeatable out of this would obviously be much harder, as any slight perturbation would cause unpredictable effects (see: chaos theory). However, I haven't read the paper so maybe they have some way of setting up the system that enables repeatability.

1. http://www.complex-systems.com/pdf/15-1-1.pdf




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: