The Paradox that Led to the Founding of Computer Science as a Discipline
Ray Toal
2021-04-30
Abstract. Many in the general public think of Computer Science as a field in which logic is binary, where answers are right or wrong, and thought and computation can somehow be studied independent of the humans doing the thinking and computing. This perception is far from the truth: paraconsistent, adaptive, fuzzy, and many-valued logics play a role in many activities within the discipline. In fact, computer science became a discipline because of a paradox invented by Alan Turing that demonstrated the limits of formal, universal computation. This little paper tells the story of Turing's construction and the birth of a new field.
1 What is Computer Science?
Many know “Computer Science” as something you can study at a university, but what is it? Roughly, it’s the theory and practice of computation, algorithms, software systems, data organization, knowledge representation, language, intelligence, learning, and consciousness.
It’s roots are in Philosophy (working out the best ways to reason and search for truth), Mathematics (reasoning symbolically), Linguistics (applying syntax and semantics), Electrical Engineering (building and using really fast computation engines), Psychology (as reasoning and information processing is done by humans for humans), and Neuroscience (for additional models of computation).
The field is unique in three ways: (1) It is not concerned with solutions to specific problems but rather in teaching agents how to solve general classes of problems. (2) It focuses on computers’ ability to amplify human thought by speeding up time, and (3) it is non-reductive:
Scientists who work in material domains - physics, chemistry, astronomy, biology, geology, meteorology - study the cosmos and all that is in it, reflect on the patterns they observe, then try to reduce their understandings to the simplest principles. I am a computer scientist; I approach the cosmos through a very different path: I take the simplest of principles - information theory, logic, design - and from them create new worlds that are bound only by my imagination. —Grady Booch.
2 The Big Questions of Computer Science
Computer science can get pretty deep and even pretty meta, as its big concerns are:
In the 1930s, quite a few people attacked the “What is computation?” question and came up with various “models” for the idea. Alan Turing created perhaps the most famous of these models, but he carried his ideas much farther, so much so that he is credited with, and revered for, founding a new discipline. What did he do?
3 Turing
Turing did some big things with his computational model (now named the Turing Machine in his honor). Two stand out:
Then he attacked the what-can-we-not-know question, something akin to “Are there any problems that could not be computed by any machine, no matter how powerful?” And he found that the answer was yes.
4 A Paradox Shows Computation Has Limits
Turing asked whether it was possible to write a program, called “Halts”, which, when given the text of another program P and some data X, reported whether program P would finish processing X or whether it would run forever. He began by imagining that this program existed:
Program: Halts(P, X)
Purpose: determine whether or not P halts on input X or whether it runs forever
If it did exist, he noted, you’d be able to write this program:
Program: Fox(P)
Steps:
Now Turing would ask you, what does Fox(Fox) say?
Work it out! If our assumed Halts program is true to its word, then whenever Halts(Fox,Fox) says YES, Fox(Fox) would run forever. But if Halts(Fox,Fox) says NO, then Fox(Fox) halts. WHAT?! Paradox!
Can a program both halt and not halt? Does the Catuṣkoṭi apply here? Probably not, as self-contradiction in this case doesn’t have the desired predictive properties we want for our day-to-day tasks. So we resolve the paradox by saying our assumption that Halts can be written was wrong. Therefore, Halts is not a computable function. There is no algorithm that can answer this question (for arbitrary P and X).
Now we have as part of our knowledge of computation a sense of its boundaries. We have a real discipline.
5 So What?
So there are problems we cannot compute. Big deal. Does your intuition tell you everything should be computable? That every true statement should have a proof? That computers, or formal reasoning, could ever tell us everything that could be known? It probably shouldn’t. Why should formal, discrete, quantized, linear, boring, step-by-step reasoning define all that we can know? Mathematicians know, thanks to Gödel, that there are true statements, even about arithmetic, that cannot be proven, and Gödel’s proof followed the same model as Turing’s. Surely knowledge and truth must transcend formal reasoning?
None of this is really surprising. Paradoxes arise in everyday discourse when encountering absolutistics statements surrounding nothingness and everythingness. To say I can know everything, I can prove everything, or I can compute everything naturally opens one up to paradoxes of self-reference when the things you imagine knowing, proving, or computing are statements about knowledge, proof, or computation.
What is interesting is that, using Turing’s approach, we have identified many interesting un-programmable and uncomputable questions over the years. So not everything we can know is reachable through mechanical computation. Maybe the very idea of computing, or reasoning, via steps-in-time, or inference, or logic, is what is limiting us. What are, or where are, the better models of reasoning and knowing? Who will invent or discover them?