What Can Computers Solve? The Question That Started It All

The Year “Computer” Meant a Person

Picture a large, quiet room in 1936. Rows of desks fill the floor. At each desk sits a person — many of them women — bent over sheets of paper covered in numbers. They hold pencils. They consult instruction booklets. They erase, rewrite, and move on to the next step. Their job title? Computer.

Before electronic machines took over the word, a “computer” was a human being. These human computers worked in banks, government offices, and research labs. Their task was to carry out long, tedious calculations — the kind you do when you multiply large numbers or work through a formula one operation at a time. They did not need to understand the deeper mathematics behind their work. They just needed to follow the rules.

That same year, a young British mathematician named Alan Turing (1912–1954) looked at what these human computers were doing and asked a question that would change the world: What, exactly, is going on when a person computes? Can we describe it so precisely that a machine could do it?

Turing’s answer led to the invention of the modern digital computer. But it also led somewhere more surprising — to a proof that some mathematical problems can never be solved by any mechanical method, no matter how powerful the machine.

What Makes a Method Truly “Mechanical”?

Turing was not the first person to wonder about this. For centuries, mathematicians had relied on what they called effective methods (or mechanical methods). The idea is simple. A method is “effective” if it meets these conditions:

First, the method must be written down as a finite number of exact instructions — you cannot need an infinite rulebook. Second, if you follow the instructions without making mistakes, you will get the answer in a finite number of steps — no endless wandering. Third, a human being should be able to carry it out using nothing but pencil and paper — no special machinery. And fourth, the method must require zero insight, intuition, or cleverness. You just follow the steps.

A classic example is the truth-table test for deciding whether a sentence in basic logic is always true. You list every possible combination of true and false for the sentence’s parts, then check the result for each combination. It is mindless, repetitive work — but it always works. Given enough paper and patience, a person who understands nothing about logic can do it perfectly.

Here is the catch. The definition above uses words like “insight” and “intuition” — fuzzy, human words. What counts as “no insight”? The definition is informal. Turing’s great achievement was to replace this informal idea with something mathematically precise.

Turing’s Gamble: The Human Mind as a Machine

Turing’s strategy was bold. He looked at a human computer — a person calculating at a desk — and asked: what are the essential features of this activity? Strip away everything irrelevant (the computer eats lunch, gets tired, daydreams) and what is left?

He listed the features that matter. The computer writes symbols on paper, which you can think of as divided into squares, one symbol per square. There are only finitely many types of symbol the computer can recognize or write. The computer can look at only a limited number of squares at once. To see more squares, the computer must make a fresh observation — and those new squares are never more than a fixed distance from the ones just observed. The computer’s behavior at any moment is determined by two things: the symbols currently being observed, and the computer’s “state of mind” at that moment. Crucially, the number of possible states of mind that matter is finite.

From this, Turing built a mathematical model: the Turing machine. Imagine an endless paper tape divided into squares. A scanner moves along the tape, reading one square at a time. The scanner can erase the symbol it sees, write a new one, and then move one square left or right. Inside the scanner is a control mechanism that can be in one of a finite number of internal states — Turing called them m-configurations. What the machine does next depends entirely on its current m-configuration and the symbol it is reading.

Turing then argued — in what he called a “direct appeal to intuition” — that any computation a human being can perform using an effective method can also be performed by a Turing machine. His argument, known as argument I, walks through each essential feature of human computation and shows that a Turing machine can duplicate or simulate it. States of mind become m-configurations. The two-dimensional sheet of paper becomes a one-dimensional tape (Turing said the two-dimensional character of paper is “no essential of computation”). The job of the human computer becomes, in principle, the job of a machine.

This is the core of what came to be called the Church-Turing thesis. The American logician Alonzo Church (1903–1995) arrived at a similar idea independently, using a different formal approach involving something called recursive functions. Both proposals turned out to be equivalent — they pick out exactly the same class of mathematical functions. The thesis, in its simplest form, says: if there is an effective method for solving a problem, then a Turing machine can solve it. And conversely, anything a Turing machine can do counts as an effective method.

The Problem That Was Supposed to Be Easy

Why did Turing care so much about this? He was trying to solve a famous problem — the Entscheidungsproblem, which is German for decision problem.

Here is the question. Imagine you have a logical system — a set of axioms and rules for proving things. Can you find an effective method that will decide, for any formula you feed in, whether that formula is provable using the system’s rules? You want a yes-or-no answer, every time, in a finite number of steps. Such a method is called a decision procedure.

The great mathematician David Hilbert (1862–1943) had called this “the main problem of mathematical logic.” He was confident such a procedure existed for the most important logical system of all — first-order predicate logic, which includes ordinary propositional logic plus quantifiers (“all,” “some”). Hilbert expected someone would find it.

In 1936, Church and Turing both proved him wrong — independently. Using the Church-Turing thesis, they showed that no decision procedure for first-order predicate logic can exist. There is no effective method, and there never will be. No Turing machine can do it. No human computer can do it. The Entscheidungsproblem is unsolvable.

This was a shock. Hilbert had famously said that every mathematical problem must have a solution — either an answer, or a proof that no answer is possible. The Entscheidungsproblem fell into the second category. It was a limit, not a temporary obstacle.

One Machine to Do Everything

Amid this negative result, Turing also discovered something astonishingly positive. He described what he called the universal computing machine — now known as the universal Turing machine.

An ordinary Turing machine is built to do one specific job. One machine might add numbers. Another might check whether a formula is a tautology. But the universal machine is different. It can imitate any Turing machine whatsoever. You simply write a description of the other machine — its instructions, its m-configurations, its rules — onto the universal machine’s tape. Then the universal machine reads those instructions and behaves exactly like the machine you described.

Think about what this means. Instead of building a new machine for every new problem, you build one machine and feed it different programs. The universal machine has two essential parts: a memory for storing instructions and data, and a control mechanism that reads and executes those instructions. This is the logical skeleton of every electronic computer you have ever used. Your phone, your laptop, your game console — all of them are universal machines in Turing’s sense.

Church himself, reviewing Turing’s work, said that Turing’s approach had an advantage over his own: Turing’s identification of effective methods with what a machine can do was “evident immediately.” The great logician Kurt Gödel (1906–1978) was initially unconvinced by Church’s version of the thesis — but he accepted it fully once he saw Turing’s formulation, calling it “correct beyond any doubt.”

The Limits Nobody Expected — and Why They Matter

So the Church-Turing thesis tells us that effective methods and Turing-machine programs are, for all practical purposes, the same thing. But here is something crucial: the thesis is about human computation — what a person can do with pencil and paper, following clear rules. It is not the same as the claim that no physical machine could ever compute more than a Turing machine.

This is a common confusion, and philosophers have worked hard to untangle it. The logician Robin Gandy (1919–1995), Turing’s only PhD student, gave the separate claim its own name: Thesis M — the idea that whatever any machine can calculate, a Turing machine can calculate. Thesis M is not the Church-Turing thesis. And in its strongest form, Thesis M is false.

Here is a thought experiment to show why. Imagine an accelerating Turing machine. It works like an ordinary Turing machine, except it speeds up as it goes. The first step takes one moment. The second step takes half a moment. The third takes a quarter of a moment. After two moments of operating time, this notional machine has completed infinitely many steps. That lets it solve problems that no ordinary Turing machine can ever solve — for instance, the famous halting problem, which asks whether a given Turing machine will eventually stop or run forever. An accelerating Turing machine can answer that question in finite time. An ordinary Turing machine cannot.

Does an accelerating machine violate the actual laws of physics? Probably — but the point is that the strong claim about all possible machines is false. The weaker claim — about machines that can actually exist in our universe — is still an open question. Some researchers believe quantum effects, or exotic physics involving time dilation, might allow physical machines to compute things that Turing machines cannot. Others disagree. The debate is live and fascinating.

Why does this matter to you? Because the Church-Turing thesis is not just history. It tells you something permanent: some questions have no mechanical answer. No app, no algorithm, no future artificial intelligence can solve them. And yet, the universal machine idea also tells you that a single, simple design can run every algorithm we do know. Every time you use a device that seems to do a thousand different things, you are watching Turing’s insight at work. The limits and the power came from the same idea.

Think about it

1. When you follow a recipe exactly, or solve a math problem using a memorized method, are you “thinking” or are you “computing”? Does the difference matter?
2. If a problem can never be solved by any machine, could a human being still solve it? What would your answer say about what the human mind is?
3. Your phone runs on the universal machine idea — one device, infinite apps. But there are problems no phone, no supercomputer, and no future technology can ever solve. Does knowing that change how you feel about technology?