Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I'm constantly blown away by the fact that such a simple rules can lead to complex systems such as this. Changed my perspective on a lot of things after that


I read Code by Charles Petzold earlier this year and I feel like I had a similar realization. A simple switch can lead to such complex systems.


Right. A transistor (as used in most digital logic, anyway) is just a switch, and is what our most complex computers are made of.


Do we have an understanding yet of the minimum number of unique rules a system must have in order to be able to be Turing complete?


Not sure how this translates to "rules" in a cellular automaton, but: https://en.wikipedia.org/wiki/One-instruction_set_computer


This is exactly what I was asking about. Thank you!


There's also a few "one instruction" CPUs

https://en.m.wikipedia.org/wiki/One-instruction_set_computer


Here’s a white paper on how one was implemented https://www.sccs.swarthmore.edu/users/06/adem/engin/e25/fina...


You can build anything with AND and NOT gates or OR and NOT gates.

https://www.electronics-tutorials.ws/logic/universal-gates.h...


You can build anything with just NAND gates.


Well, we know that rule 110, which is like a 2d versions of Conway's game of life, is also Turing complete. So at least that simple.


Growing Artificial Societies is an interesting book that extrapolates on this.




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

Search: