One of the most amazing features of human languages is their capacity for self-reference. The consequences of this feature were explored by Eubulides, a 4th-century BCE Greek philosopher, who formulated the Liar's Paradox, "What I am saying now is a lie." Is this a lie or not? For over 2,000 years, the Liar's Paradox was a philosophical oddity. In 1902, in a letter to the mathematician Friedrich Frege, the philosopher Bertrand Russell reformulated the Liar's Paradox as a paradox in set theory, arguing that "the collection of all sets that do not include themselves as members" both cannot be a set and cannot fail to be a set. By identifying a contradiction in set theory, Russell launched a "foundational crisis" in mathematics.
The foundational crisis proved to be enormously fertile. It inspired David Hilbert to launch in the early 1920s what has become known as "Hilbert's Program," the goal of which was to demonstrate that mathematics was consistent (free of paradoxes), complete (can answer all mathematical questions), and decidable (amenable to computation). Within 15 years, Hilbert's Program was demolished first by Kurt Gödel, who proved that arithmetic is incomplete and cannot prove its own consistency, and then by Church and Turing, who showed that First-Order Logic is undecidable. The crucial technique used by Gödel, Church, and Turing is that of diagonalization, which is a technical term for self-reference. Turing invented Turing Machines as a model for computability in order to prove his undecidability result, so theoretical computer science rose out of the ashes of Hilbert's Program. Diagonalization went on to play a key role in computational complexity theory, where it was used to prove separation results, for example, that there are problems that can be solved in exponential time, but not in polynomial time.
Yet mathematicians, in general, took the demise of Hilbert's Program in stride. Mathematics is incomplete, undecidable, and cannot prove its own consistency; so what? Mathematics has just gone on. Perhaps computer scientists should develop a similar nonchalant attitude about negative results. The undecidability of program termination means there is no algorithm that can correctly decide termination of all programs. So what? As I argued in "Solving the Unsolvable,"a program termination may be practically decidable, even though it is theoretically undecidable. Just as mathematicians gave up on the quest to find a proof system that can prove all true mathematical statements, we may need to give up on the quest for algorithms that solve all problem instances. In other words, the quest for universality is self-destructive.
Self-reference was taken in a different direction by the philosopher Karl Popper, who formulated the paradox of freedom in 1945: "The so-called paradox of freedom is the argument that freedom in the sense of absence of any constraining control must lead to very great restraint, since it makes the bully free to enslave the meek." Closely related is the paradox of tolerance: "Unlimited tolerance must lead to the disappearance of tolerance." Popper's conclusion was that we must give up on the universality of freedom and tolerance, as complete freedom and tolerance are self-destructive. Even a free society must have some limits on freedom, and a tolerant society must be intolerant of intolerance.
These philosophical musings from more than 70 years ago seem these days to be quite prescient and relevant. Section 230 of the Communications Decency Act of 1996 is a fundamental item of Internet legislation in the U.S. Section 230 provides immunity from liability for providers and users of an "interactive computer service" who publish information provided by third-party users, asserting: "No provider or user of an interactive computer service shall be treated as the publisher or speaker of any information provided by another information content provider." Section 230 enables Internet companies such as Google and Facebook to be considered as platforms rather than as publishers, free from liability for the content they publish. The explosive growth of social-media platforms would have not been possible without Section 230.
Yet this explosive growth has led to the proliferation of "bad" speech on social-media platforms, which has become politically untenable. All social media platforms are now actively fighting "fake news"false news stories typically spread with the intent to influence political views. Recently, social-media platforms have banned the conspiracy theorist Alex Jones for violating their "abusive behavior" policy. In spite of Section 230, social-media platforms seem to be accepting responsibility for the content they publish. In other words, they are starting to behave with some restraint, like publishers, rather than platforms. Popper would be pleased with this development!
The Digital Library is published by the Association for Computing Machinery. Copyright © 2018 ACM, Inc.