4 ms·
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?
by dclowd9901 4y ago
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?
- davidrupp 4y agoNot sure how this translates to "rules" in a cellular automaton, but: https://en.wikipedia.org/wiki/One-instruction_set_computer https://en.wikipedia.org/wiki/One-instruction_set_computer
- dclowd9901 4y agoThis is exactly what I was asking about. Thank you!
- riffraff 4y agoThere's also a few "one instruction" CPUs https://en.m.wikipedia.org/wiki/One-instruction_set_computer https://en.m.wikipedia.org/wiki/One-instruction_set_computer
- dclowd9901 4y agoHere’s a white paper on how one was implemented https://www.sccs.swarthmore.edu/users/06/adem/engin/e25/finale/ https://www.sccs.swarthmore.edu/users/06/adem/engin/e25/fina...
- dnh44 4y agoYou can build anything with AND and NOT gates or OR and NOT gates. https://www.electronics-tutorials.ws/logic/universal-gates.html https://www.electronics-tutorials.ws/logic/universal-gates.h...
- deleted 4y ago[deleted]
- JohnFen 4y agoYou can build anything with just NAND gates.
- gdprrrr 4y agoWell, 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.