The Proof of Universality
Matthew Cook presented his proof of the universality of Rule 110 at a Santa Fe Institute conference, held before the publication of NKS. Wolfram Research claimed that this presentation violated Cook's nondisclosure agreement with his employer, and obtained a court order excluding Cook's paper from the published conference proceedings. The existence of Cook's proof nevertheless became known. Interest in his proof stemmed not so much from its result as from its methods, specifically from the technical details of its construction. The character of Cook's proof differs considerably from the discussion of Rule 110 in NKS. Cook has since written a paper setting out his complete proof.
Cook proved that Rule 110 was universal (or Turing complete) by showing it was possible to use the rule to emulate another computational model, the cyclic tag system, which is known to be universal. He first isolated a number of spaceships, self-perpetuating localized patterns, that could be constructed on an infinitely repeating pattern in a Rule 110 universe. He then devised a way for combinations of these structures to interact in a manner that could be exploited for computation.
Read more about this topic: Rule 110
Famous quotes containing the word proof:
“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a proof that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”
—Herman Melville (1819–1891)