Foundations of Computation

Definition and Core Concepts What Is a Computation? A computation is any well-defined arithmetic or non-arithmetic calculation. The key word here is "well-defined"—this means the computation must be unambiguous and follow a clear set of instructions that leave no room for interpretation. Think of computation broadly: it's not just simple arithmetic like $2 + 2 = 4$. It also includes solving complex equations, running algorithms, sorting data, or any other process that can be precisely specified. The essential requirement is that someone (or something) could follow the instructions and always arrive at the same answer given the same starting inputs. Who Performs Computations? Any device or entity capable of performing computations is called a computer. Historically, this term has referred to: Mechanical devices (like Babbage's Analytical Engine) Electronic devices (like modern laptops and servers) People trained to follow strict computational procedures The important point is that "computer" originally described what something does (performs computations), not what it is made of. A computer doesn't have to be electronic—it's defined by its ability to execute well-defined procedures. What Makes a Statement Computable? Not all statements are computable. A computable statement is one that can be unambiguously expressed as a procedure—a step-by-step process that a computer could follow. When we say a statement is "well-defined," we mean it can be converted into exact instructions without any vagueness or ambiguity. For example: "Find the square root of 16" is well-defined and computable "Paul loves me twice as much as Joe" is not well-defined—how would you measure love? How would you encode this into clear computational steps? This distinction is central to understanding computation. A statement must be precise enough that a machine (or a person following strict rules) could execute it mechanically. The Relationship to Computer Science Computer science is the academic discipline that studies computation—how to formally define what is computable, how to design algorithms to solve problems, and what problems cannot be solved by computation at all. Understanding the foundations of what computation is forms the basis of the entire field. Formalizing Computability: When Can We Call Something Computable? Alan Turing's Breakthrough In the 1930s, mathematician Alan Turing created a formal definition of what it means for a statement to be "well-defined" and computable. Turing's approach was elegant: he asked, "Can this statement be expressed as instructions for a Turing machine?" A Turing machine is a theoretical device consisting of: An infinite tape divided into squares A read/write head that can move along the tape A finite set of states and rules for what to do in each state Turing's insight was that any statement that could be precisely expressed in terms of what a Turing machine could do—given appropriate starting inputs—is computable. This provided the first rigorous, mathematical definition of computability. Equivalent Definitions Show the Robustness of the Concept Around the same time, other mathematicians independently developed different formal definitions of computability: Alonzo Church developed lambda-definability Herbrand, Gödel, and Kleene developed general recursiveness Emil Post developed 1-definability What's remarkable is that all of these different approaches turned out to be equivalent—they all define exactly the same set of computable statements. This equivalence strongly suggests that these definitions capture something fundamental about what "computable" really means, independent of the particular formalism used. Computable vs. Non-Computable Statements Understanding What Makes a Statement Non-Computable Just because a problem is interesting or important doesn't mean it's computable. There are two categories of non-computable statements: Type 1: Ill-defined statements These statements cannot be unambiguously encoded into computational procedures. For example: "Create a beautiful piece of music" (what counts as beautiful?) "Paul loves me twice as much as Joe" (how do you measure and compare emotions?) "Find the most interesting number" (what makes a number interesting?) These aren't computable because they're fundamentally ambiguous—different people would interpret the instructions differently. Type 2: Well-defined but unsolvable statements These statements are clearly specified, but mathematicians have proven that no computational procedure—no matter how clever—could ever solve them. The most famous example is the halting problem. The halting problem asks: "Given any computer program and any input, can you determine whether that program will eventually finish running or run forever?" This problem is precisely defined, but Alan Turing proved that no algorithm can solve it in general. Some specific cases might be solvable, but there's no universal procedure that works for all programs. This is a profound result: it shows there are limits to what computation can do. Computability is not unlimited. Computation as a Physical Process An important perspective is that computation can be understood as a purely physical process happening inside a physical system called a computer. When you run a program on your laptop, you're setting up a particular physical configuration (voltage patterns, magnetic states, etc.) and then letting the laws of physics carry out a deterministic process. This viewpoint connects abstract mathematical ideas about computability to real, physical machines—a bridge between theory and practice. Physical Realisations of Computation Multiple Ways to Implement Computation Turing's 1937 work established a formal equivalence: the set of statements that are mathematically "computable" corresponds to the set of problems that particular physical systems (computers) can solve. In other words, the abstract mathematical concept of computability matches what physical devices can actually accomplish. This means computation can be physically realized in multiple ways: Turing machines (the theoretical foundation) Digital computers (using binary digits and electronic circuits) Mechanical computers (using gears and levers) Analog computers (using continuous physical phenomena like voltage or fluid flow) <extrainfo> What's fascinating is that despite their enormous differences in construction—a mechanical device using gears versus an electronic computer using transistors—they can all compute exactly the same set of problems. This universality is a fundamental insight in computer science. </extrainfo> The key takeaway is that being a "computer" (in the sense of performing computation) isn't about the physical substrate—it's about whether the device can implement the abstract procedures that define computable statements.