2 ms·
Ask HN: Is Google or Facebook turing complete?
Or perhaps a better question would be something along the lines of - is social graph or page rank turing complete?
- greenyoda 11y agoWikipedia defines Turing completeness like this: "A system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete ... if it can be used to simulate any single-taped Turing machine." [1] A social graph is just a list of pairs of people ("A knows B", "B knows C"), so I'm not sure how the concept of Turing completeness could apply to it. There is no computational model inherent in it. It doesn't manipulate data - it is just data (that can be manipulated by any number of algorithms that run on Turing complete computers). [1] https://en.wikipedia.org/wiki/Turing_completeness https://en.wikipedia.org/wiki/Turing_completeness