Wikipedia 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]<p>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).<p>[1] <a href="https://en.wikipedia.org/wiki/Turing_completeness" rel="nofollow">https://en.wikipedia.org/wiki/Turing_completeness</a>