Computers, Programs, and Wrestling with Infinity

by Clarissa Littler

If you’re a programmer, you’re used to programming in a particular language. What is a programming language, though? What on a fundamental level are programs? Are some programming languages more powerful in what they can express than others? Even without a machine to run the code on, a program is a formal description of how to perform a computation. By the end of this article, we’ll hopefully have imparted a sense for what “a computation” is and will have some answers to the questions above.

The basic outline of this piece is that we’re going to cover:

• Rules of thumb for what counts as a computation and what infinity means
• How specifications of problems are separate from computations
• What Turing machines are and how they help us understand the limits of computation
• General limitations on what problems can be solved computably
• How Turing machines are related to every day programming languages

To start with, we’re going to draw up a rough sketch of “finite”, “infinite”, and “infinity” is since these are terms that are going to come up repeatedly.

Most of us are familiar with infinity as the distant unreachable end of the number line, or as the thing you get when you divide by zero in grade school. Going back even further, it’s the “number” that we pull out as children to win arguments. After all, infinity is bigger than any other number!

What is it though? Infinite things and “infinity” always represents a limitation of some kind, something you can’t do with limits on your time and resources. There’s many kinds of infinity, but the one that’s important to us is the kind you can’t reach by counting, no matter how much time you have. This is the infinity that we mean if we say something like “if you had an infinite amount of money, what would you do first?” or “I wish for infinite wishes”. We’re talking about quantities that we can usually count, such as “I have $50 dollars”. If I had $50 dollars in front of me I could verify that it is, indeed, $50 dollars by counting up all coins and bills. Since we can count it, we call it finite. If we can’t count it, then we call it infinite.

What of the act of counting itself? Clearly, counting is a kind of procedure, the beginnings of an algorithm. Coming from this notion of counting-as-proof-of-finiteness, we can generalize counting something finite to describing a general process for doing something as finite when you can count the number of steps it takes and you can count any of the resources you use up. For example, the process “slice the tofu into six pieces, then fry for ten minutes on each side” is finite. The process “sort an infinite number of CDs in alphabetical order” isn’t finite because you can’t count the number of CDs. The process “wait for an infinite number of seconds, then start breakfast” is not only obviously a terrible way to feed yourself but isn’t a finite process for cooking breakfast because waiting for a second, then ticking off that you’ve waited for a second, can be considered a single step. That means this process takes an infinite number of steps to accomplish it’s goal.

Now we can take our first stab at what we mean by computation. The essential notion is that a computation is a “finite process”, where by finite process we mean any sequence of steps that:

1. finishes its task in finite time or responds to input in finite time
2. uses only a finite amount of resources
3. can be described in a reproducible way in a finite amount of text

You’ll note this definition doesn’t really mention computers, and that’s very intentional. We’re going to consider anything that fits these three criterion as a finite process. This includes:

• balancing your checkbook
• transcribing a conversation
• keeping score in cribbage
• following a set of walking directions
• cooking from a recipe you found online
• following wordless diagrams to build Swedish furniture

but also more interesting things your computer does such as:

• running an operating system
• serving HTTP requests
• compiling your program

The question we need to answer is why we’ve settled on these criterion. Essentially, it’s for entirely pragmatic purposes. These are the bare minimum criterion for some process to actually do something useful. We consider in turn what happens if these criterion are violated.

First, if the process doesn’t accomplish something in finite time or, in the case of something like an operating system or a server, respond to input in finite time then we can’t possibly get any use from it. It makes no observable changes in the universe beyond consuming resources, which is entirely useless.

Second, if the process uses an infinite amount of any resource while executing then we can’t possibly finish executing it! We likely only have a finite amount of resources in the universe itself! We also can’t use an infinite amount of anything in finite time without breaking the laws of physics: hard drive space, memory, or garlic scapes. The act of consuming these resources takes time.

Finally, our process needs to be able to be written down in a finite amount of text. This is because we need to be able to transmit the knowledge of how to perform the process to each other. We need to be able to store it in books, hard drives, or napkins.

There’s an important complication though: do we know whether a process only takes a finite number of steps? Can we just look at the description and know? Let’s consider the following directions:

1. Take one step forward
2. Turn around
3. Take one step forward
4. Go back to step 1

In this case we can pretty easily see what’s happening here. There’s only a finite number of steps in the description, each step is well-defined, and we don’t appear to be using an infinite number of resources at any point. Yet, this will always take an infinite number of steps/infinite amount of time because there’s no way it can end. Step 4 always takes us back to step 1 no matter what. Having a finite description doesn’t necessarily guarantee that you’ll finish in finite time. Because it’s a concept that will come up repeatedly, we’ll point out that “finishing in finite time” is generally called “halting” or “terminating” in computer science.

Being able to tell whether a process halts isn’t always so simple, though. Consider the following directions, where we operate on a given number n,

1. If n equals 1, then we finish
2. If n is even we start the process over with our new n equal to n/2
3. If n is odd we start the process over with n equal to 3*n+1

Does this process always take a finite number of steps for all possible inputs n? We don’t actually know the answer to this, because what we’ve described is actually the Collatz conjecture! (Van Bendegem 2005; Lagarias 1985) We have experimental evidence indicating that for very large numbers this algorithm still terminates, but we have no proof of it. We honestly don’t know the answer.

These “finite processes” capture the informal essence of what an algorithm is in computer science. There was, however, a bit of sleight of hand: we defined a finite process as one that can “accomplish its task” in finite time. What is “its task”? To answer this, we need to talk a bit about problems and specifications.

We’ve seen that a computation is a process for doing something. A specification is then a description of what it’s doing. Although sometimes we sit down and start coding without really knowing what we’re trying to do, in general we’re always trying to solve a problem. The formal description of that problem is its specification. For example, the web server you write is a computation, but the design for the site and how it should respond to different HTTP requests is a specification.

We need to make this distinction between computation and specification because:

• a specification may have many distinct computations that solve the problem
• a specification may have no solution

Another example of the distinction between computation and specification comes from our schooling. We all may know that the expression 3+5 evaluates to 8, but that doesn’t tell us how we perform that calculation. You could evaluate it this way:

3 + 5 = 2 + 6
2 + 6 = 1 + 7
1 + 7 = 0 + 8
0 + 8 = 8

or you could do something more like:

3 + 5 = 4 + 4
4 + 4 = ...

and proceed by repeatedly adding one to the left-hand number in the addition. Also think of how we perform large sums: do you do the grade-school method of writing out the numbers as rows and columns and add them up a digit at a time? Do you break it apart in your head some other way?

Even just the act of recalling what the result of a sum is from memory is a different way of computing, essentially looking up the value in a database of math problems. The value of the addition and all of these different “programs” are all correct implementations of the specification for addition.

Before we move on, though, we still need to square our definitions of computation and specification with one horrid program we’ve all written at some point: the infinite loop. I think we’ve all done it at some point, we’ve written code that—when run—outputs nothing, takes in no input, and yet never stops running. It’s easy to do by accident, more easy in some languages than others. Isn’t this a computation since we can run it on the computer? The detail in which the devil has hidden is “finite time to accomplish its task”. A computation doesn’t have to finish in a finite number of steps if its specification doesn’t specify what to do in that particular case. For example, if we consider the specification:

For any positive whole number `n`, the program should count down from `n` and print out every number greater than `0`

and the following Python program that meets the specification:

def f(n):
    while n != 0:
        print(n)
        n = n-1

Inspecting this program we can see that it will enter an infinite loop if n is smaller than 0, but it still meets the specification since the specification said nothing about numbers smaller than zero. This freedom-to-be-infinite on unspecified inputs will come up again when we reach the halting problem.

To this point, we still haven’t explained how to actually define computations even though we have some general intuition for what is a computation. So far we’ve just been giving our descriptions of computations as intuitive algorithms that we can understand. The problem is that a computer isn’t as smart as we are. Even the easy to follow description of the Collatz problem that we gave above has many components that have to be carefully spelled out for the algorithm to be able to be followed by a machine. For example, how do we know two numbers are equal? What does it mean to start an algorithm over again? How do we know a number is even or odd? How do we even move from one step to the next in the instructions?

In order to define an algorithm rigorously, we need a mathematical formulism that allows us to describe all of the steps precisely. Such a mathematical formulism is called a universal model of computation. There are a number of universal models of computation, but the main one we’ll be talking about here is the Turing machine. Alan Turing introduced, in his 1936 paper (Turing 1936), a kind of simple mechanical machine meant to encompass all possible computations.

The original context of his work may seem remote from our perspective, because he was attempting to deal with something called the “decision problem” which was about whether there existed an algorithm that could construct rigorous proofs of true statements in logic, but in order to actually answer this question one way or another someone had to actually figure out what exactly an algorithm could be.

Today we have the advantage of having computers that inspire us to understand computation and programming languages that tell us that there must exist some rigid system for writing down the description of any computation. In Turing’s day, there were computers of a different sort for inspiration: human computers (Grier 2013). In Turing’s day, “computer” was a job title. Computers were people, mostly women, who’d had training in mathematics and performed complex calculations professionally. Computers would work on problems such as simulations in physics or on calculating firing tables for artillery. Some of these women went on to be the first programmers for the ENIAC.

Turing designed his abstract machine from watching computers work, noting that any computer solving a problem could:

• only use a finite amount of scratch paper
• only have a finite number of “mental states” that she went through when working on the problem
• only be working on one part of her scratch paper at a time

To this end, Turing’s “automatic machines”, which we now call Turing machines, had a long strip of scratch paper divided into segments, called the tape, and a piece of machinery that can read from and write to the segments, called the head. A Turing machine also has a finite number of “states” it can be in, which govern what it will do in the next step of computation. In each step of computation, a Turing machine will do these things:

1. read from the segment of tape that the head is on
2. write into the segment of tape that the head is on
3. move the head one segment to the left or the right
4. enter a new state

A Turing machine runs by giving it a tape with an initial input written on it and the data on the tape when it finishes running is the output.

This might sound very limited, but what’s rather surprising is that every computation corresponds to the behavior of some Turing machine.¹ This is a claim that we need to discuss briefly, though. We can see that a Turing machine, by its restrictions on finite and states and finite scratch paper, fits the criterion of a finite process. What’s less clear is that Turing machines correspond to all possible computations. On some level, we don’t know for certain but we’re somewhat confident that there is no computation that can’t be defined by a Turing machine. This comes down to the Church-Turing thesis (Kleene et al. 1952), which comes from the observation that every other attempt to define a universal model of computation ends up being exactly as powerful as Turing machines. Essentially the Church-Turing thesis is that there will never be a model of computation more powerful than all the models we currently have. We don’t know if the Church-Turing thesis is actually true, but I’d argue that most, though not all, computer scientists work under the assumption that it is correct.

Now, Turing machines were not the very first model of computation, that distinction barely goes to Church’s lambda calculus (Church 1936), but Turing’s automatic machines were the first that really captured the intuitive notions of computation and prefigured the modern computer. The lambda calculus, while elegant, isn’t obviously finite in the same satisfying way that Turing machines are. It’s in Turing’s honor, then, that we often speak of programming languages being Turing complete, which means that they are equivalent in descriptive power to a Turing machine.

We still need to show what a model of computation buys us, which brings us to the “halting problem”. The halting problem has the following specification:

Our program should read in the source code of a program and a value intended to be passed
into the program we read in. If the read-in program will terminate when fed that input,
then return 1, if it will not terminate then return 0.

In other words, an implementation of this specification should be able to read in:

• the source code of another program
• a value that would be fed that program

and tell us whether the program will finish or go into an infinite loop. This is basically asking whether we can write a program that will analyze other programs and always detect infinite loops. It turns out, though, that you can’t. The halting problem, much like the “decision problem” Turing originally proved had no solution, has no program that matches its specification. We say then that the halting problem and the decision problem are not decidable.

This is proven by a variant of the “liar’s paradox”, which is the old joke that “this statement is false”. Am I lying or am I telling the truth? There’s no possible resolution to the paradox.

A fairly rough sketch of the proof that the halting problem isn’t solvable goes as follows:

• assume that we have a program that can solve the halting problem, we’ll call it H
• we then construct a new program, called C for contradiction compiler, that
  1. reads in a program
  2. uses H to test to see if the program would halt when given its own source code as an input
     1. If H returns 1, then go into an infinite loop
     2. If H returns 0, halt

What happens if we run C on itself? There’s no resolution to the paradox, which can only mean that H cannot exist.

The much more modest problem,

Our program should read in the source code of a program and a value intended to be passed
into the program we read in. If the read-in program will terminate when fed that input,
then return 1

actually is solvable by simply running the program in an interpreter. If the program terminates, then simulating it in our interpreter will certainly terminate as well. If the program doesn’t terminate, then our interpreter won’t either. This is where the details of the specification are very important.

There are many other examples of specifications that are not decidable. Many of the more interesting ones correspond to programs that analyze other programs and there’s a general result we can use in this regard: Rice’s Theorem (Rice 1953). Rice’s theorem essentially tells us that if a specification would tell us something interesting about programs, then it will be undecidable.

What do we mean by “something interesting”? We mean properties like:

• whether a program halts on a given input (the halting problem)
• whether a program satisfies a specification
• whether a program is bug free
• whether a program contains a self-replicating virus

So unfortunately, Rice’s theorem tells us that programming will always be a difficult enterprise. There’s never going to be a magic solution that can tell us, with absolute certainty, that our programs are correct.

Finally, we tie all of this to every day programming and we can finally say exactly what a programming language is. A programming language is a model of computation, a system for defining computations, and programs are the representation of those computations in the model. This means that a programming language needs to have both a syntax and a semantics. The semantics is how syntax is actually translated into computations. Every language has at least one semantics: its interpreter or compiler. Many languages don’t, on the other hand, have a mathematically defined semantics useful for proving things like the undecidability of the halting problem. On a more personal level, the fundamental limits on computation and the nature of programs as precise descriptions of computations are the reason for programming being a fundamentally difficult activity, particularly when you are attempting to do it well.

In summary, we’ve covered a few concepts that will be worth remembering as a programmer. First, that computation itself is a subject worthy of mathematical study that is independent of any given programming language and that there are models of computation, such as Turing machines, that are universal in their ability to describe all computations. Second, that there are limits to what can be described as a computation. There are some things that you may want to solve with a program that just can’t be solved. In particular, these undecidable problems tend to involve things like program analyzers or virus scanners, because by Rice’s theorem it turns out that no particularly interesting properties of programs can be calculated decidably. Finally, that a programming language is fundamentally a way to specify computations precisely.

References

Church, Alonzo. 1936. “An Unsolvable Problem of Elementary Number Theory.” American Journal of Mathematics. JSTOR, 345–63.
Grier, David Alan. 2013. When Computers Were Human. Princeton University Press.
Kleene, Stephen Cole, NG de Bruijn, J de Groot, and Adriaan Cornelis Zaanen. 1952. “Introduction to Metamathematics.” van Nostrand New York.
Lagarias, Jeffrey C. 1985. “The 3x+ 1 Problem and Its Generalizations.” American Mathematical Monthly. JSTOR, 3–23.
Rice, Henry Gordon. 1953. “Classes of Recursively Enumerable Sets and Their Decision Problems.” Transactions of the American Mathematical Society. JSTOR, 358–66.
Turing, Alan Mathison. 1936. “On Computable Numbers, with an Application to the Entscheidungsproblem.” J. of Math 58 (345-363): 5.
Van Bendegem, Jean Paul. 2005. “The Collatz Conjecture. a Case Study in Mathematical Problem Solving.” Logic and Logical Philosophy 14 (1): 7–23.

Clarissa is a PhD student in computer science who spends her time worrying about computation, type theory, the foundations of logic, and just where this whole free will thing fits into science anyway.