Tale of two answer to same question

question still hang

End of last tale, Hilbert big plan in pieces. Goal one survive: mathematics can be formalised. Goal two gone: no system can prove its own consistency. Goal three gone: no system can prove every truth. Goal four still open. Just one. The Entscheidungsproblem. Is there a mechanical procedure that decide, for any statement of mathematics, whether the statement have a proof? But "mechanical procedure" still has no precise definition. To answer Hilbert last question, someone must first say what the question even mean.

In year 1936, two young big brain answer the question. They never speak before publishing. They prove the same thing in two formal language that look nothing alike. Then they prove the formal language are the same.

Tale of how this happen.

Newman speak the word "machine"

First, Cambridge. Spring of 1935.

Young big brain Alan Turing has seen twenty-two winter. Just made Fellow of King's College that March, on the strength of an undergraduate paper called On the Gaussian Error Function. The paper prove from scratch a result called the central limit theorem. Big brain Lindeberg already prove it in 1922. Turing not know. Fellowship committee not care. Paper too good. This is Turing pattern. Work from first principle on everything.

That spring, Turing start attending Part III lectures on the Foundations of Mathematics. Lecturer is Max Newman. Newman a topologist by trade. His course walk through the territory of the last tale and end where it ended. Entscheidungsproblem still open.

Newman, in lecture, want to be precise about what the question even ask. He say a process is constructive if a purely mechanical machine can do it. Years later Newman recall the moment himself: I may even have said, a machine can do it. Figure of speech. The mathematicians of 1935 hear machine as rhetorical convenience. Like saying "a child could see this". Nobody in the room actually expect a machine to do mathematics. Newman certainly not.

Turing hear it literally.

Question sit in his head all term. Turing want to know if such a machine could really exist. Not in the engineering sense. In the formal-definition sense. If a machine can do mathematics, then what is a machine? Mathematics had a theory of number, line, function, proof. No theory of machine. The word too low-status. Too close to grease and metal. Turing decide to build the theory. Alone. In one paper.

Idea come to him in the summer of 1935. Grantchester meadows outside Cambridge. Quiet field. Turing later tell his student Robin Gandy how the idea arrive: lying in the grass, asking one question.

What does a person actually do when they compute?

That question is the seed of everything.

Turing watch the computer

Reader recall from first tale: word computer not always mean machine. For two centuries it mean a person at a desk doing sum. The bug demon haunt the human computer. Wrong number get copied, ship hit rock, men go to ancient spirits.

Turing take this human computer and make it the centre of his answer. Forget complicated rule. Forget proof system. Forget axiom. Just watch a real human being doing a real computation. What do they do? They sit at a desk. They have paper, divided into squares. In each square they write a symbol. They look at one square at a time. They have rule in their head, or perhaps written on a separate sheet, that say: when computer see this symbol and is in this state of mind, write that symbol, then look at the square to the left or to the right, then change to a different state of mind. That is the whole thing. Tape with squares. One square at a time. Finite list of state. Finite list of rule. The human computer can have as much paper as they want, but at any instant they only look at one square and only have one state of mind.

A Turing machine.

Turing build paper machine

Turing machine is not a real machine. It is a definition. Here is what it have.

• A tape. One single tape. Infinitely long in both direction. Divided into cells. Each cell hold exactly one symbol from a small finite alphabet, often just {0, 1, blank}. One tape do everything: input start on it, scratch space happen on it, output left on it. No second tape for output.
• A head. Sit over one cell at a time. Each step the head do three thing: read the symbol in its cell, write a new symbol over the old one (the old symbol gone, replaced), and move one cell left or right.
• A finite set of state. The machine is always in exactly one state. Some of these are halt states: when the machine enter one, it stop forever.
• A transition table. For each combination of (current state, symbol under head), the table say: write what symbol, move which direction, change to which state.

That is it. No second tape. No clock. No fancy thing. When the machine halt, the output is whatever the tape say at that moment, and which halt state the machine reach. The discreteness matter. Cell, not continuum. One symbol per cell. Finite alphabet. A person with squared paper and a pencil could simulate any Turing machine, given enough patience. That is exactly the picture Turing have in mind from watching the human computer.

Grug give simple example. Suppose grug want a machine that take a tape full of 0 and 1, flip every bit to its opposite, then stop. Two state: q_run and q_halt. Three rule.

• In q_run, read 0: write 1, move right, stay in q_run.
• In q_run, read 1: write 0, move right, stay in q_run.
• In q_run, read blank: leave blank, stop, go to q_halt.

Three rule. The whole machine. Start it on a tape that say 0 1 1 0. Head move right four times. Tape become 1 0 0 1. Head move one cell further. Read blank. Machine halt. Done.

Now reader say: this is silly. Too simple to do anything important. But here is the strange thing. Turing show that with enough state and enough rule, a Turing machine can compute any number that any precise procedure can compute. Add. Multiply. Sort. Find prime. Solve equation. All of it. Simplicity is the point. If you can describe the procedure precisely, you can build a Turing machine for it. The machine just be much bigger.

one machine simulate any machine

Then Turing do the move that change everything. Up to here, every Turing machine is a different machine. Different transition table for every problem. Like having a different calculator for every job. Turing ask: what if one Turing machine could take, as part of its input, the description of another Turing machine?

Here is how it work. Take any Turing machine M. M have a transition table. The table is a finite list of rule. Each rule say "in state S reading symbol X, write Y, move L or R, go to state T". The whole table is just a string of symbol. So the table can be written on a tape.

Now build a special Turing machine called U. U have its own fixed transition table, built once and never changed. U expect its tape to contain three region.

1. The transition table of M, written out as a string. This is M program.
2. The current state of M, written as a single symbol.
3. The simulated tape of M, with a marker showing where M head sit.

U have one job: walk through M behaviour step by step, by reading and updating these three region. U follow this loop:

1. Read M current state from region 2. Read the symbol from region 3 at the head marker.
2. Scan through region 1, looking for the rule that start with this (state, symbol) pair.
3. When U find the matching rule, apply it. Overwrite the symbol at the head marker with the rule new symbol. Overwrite region 2 with the rule new state. Move the head marker one cell left or right.
4. Loop back to step 1.

U keep going until M reach a halt state. Then U halt too. So U is an interpreter. M transition table is data on U tape. U look up each rule by scanning the same tape that hold the simulated computation, then copy the rule effect onto the simulated tape. No magic. U can simulate any Turing machine. Just write the description of the machine on U tape. Want to simulate the bit-flipper? Write its three rule. Want a multiplier? Write its rules instead. Same U. This is the universal Turing machine. Turing put it in his 1936 paper.

The seed of something huge sit here, quiet. U is not more powerful than other Turing machine. What make U different is that the program of M live on the same tape as the data. Program and data, same stuff, same place. Reader who use a computer recognise this. The program is a file on disk. The data is a file on disk. Same disk. The CPU run whatever program you give it. This is what every computer in the world do. Big brain John von Neumann will see Turing paper a few year later and use this idea to build the first stored-program computer. Reader meet him in a later tale.

For now, in 1936, U is just paper. But U change what machine mean. A machine no longer have to be built for one job. One machine, given the right description, become any machine.

Lovelace see this ninety winter early. Looking at Babbage Analytical Engine, she write that the machine could operate on any thing expressed as symbol and rule. Number. Music. Logic. Any thing formalisable. Different card, different program, different behaviour. Same gears. Lovelace see the principle. Turing now have the proof.

hammer swing third time

Now Turing have a precise definition of mechanical procedure. Now he can attack the Entscheidungsproblem. To answer Hilbert question, Turing first prove a smaller, sharper question impossible. The question now called the halting problem. Question is: given a Turing machine M and an input I, does M halt when run on I, or does it run forever?

Grug must be honest here. This clean question, and the name halting problem, come later. Turing own 1936 version work a little different. His machine print digit of a number forever, one after another, and Turing ask whether a given machine belong to the well-behaved kind that keep printing proper digit, or the stuck kind that dry up. He call the good kind circle-free. Different dress. Later big brain, chiefly Martin Davis in a 1958 book, clean the question into the halt-or-run-forever shape grug give here, and give it the name. Grug tell it the modern way because it is clearer. But the hammer is the same hammer Turing swing, and the thing it break is the same thing.

Reader who know a little programming feel this question. Sometimes program get stuck in loop. You wait. You wait more. Is it stuck, or just slow? You cannot tell by waiting. You want a tool that look at any program and any input, and tell you: this halt, or this run forever. Such tool would be very useful. Turing prove no such tool can exist. Any Turing machine. Any input. No general procedure can decide.

Proof is third swing of the hammer. Same hammer Russell use to break Frege. Same hammer Gödel use to wound Hilbert. Self-reference. Proof go in three move.

Move one: assume the tool exist.

Call the dream tool H. H is a Turing machine. The whole question Hilbert ask is whether such a Turing machine exist. So H have the standard equipment. A tape. A head. Finite set of state. A transition table. Among the states are two special halt states. Call them YES and NO.

H expect its tape to contain the pair (M, I): a description of any Turing machine M, followed by an input I for that machine. H read the tape, follow its transition table, do its work. After finitely many step, H always finish in one of the two halt states.

• H finish in state YES if M halt when run on I.
• H finish in state NO if M run forever on I.

H itself never loop forever. H never wrong. Suppose H exist.

Move two: build a troublemaker on top of H.

H+ is H with two small modifications. The transition table of H+ contain all the states and rules of H, plus a few extra states wrapped around them.

Change one: duplicate the input. H expect the pair (M, I) on its tape. H+ expect only M. So H+ start with extra states that copy M next to itself, leaving (M, M) on the tape. Now the tape look exactly like what H expect, with I filled in by M itself.

Change two: flip the halt states. From the duplicated tape, H+ hand over to H. H eventually finish in state YES or state NO. But H+ do the opposite:

• If H finish in YES, H+ transition to a new spinning state that never halt.
• If H finish in NO, H+ halt immediately.

That is the whole of H+. Duplicate the input. Run H. Flip the answer. If H exist as a Turing machine, H+ exist as a Turing machine too. H+ have its own transition table. Its own description. Like every other Turing machine.

Move three: feed H+ its own description.

This is the move. H+ is a Turing machine, so H+ have a description: a finite string of symbol listing its states and transition table. Grug can write that description on a tape and feed it as input to any Turing machine. Including to H+ itself.

What does H+ do when given H+ as input? What is H+(H+)?

By change one, H+ duplicate its input, putting (H+, H+) on the tape. Then H+ hand over to H. H now run on the pair (H+, H+). Notice what this mean. H decide whether H+ halt when given H+ as input. That is exactly the question grug care about. H must finish in YES or NO.

• Suppose H finish in YES. That mean H predict H+(H+) will halt. But by change two, when H finish in YES, H+ enter the spinning state and run forever. So H+(H+) run forever. H predict wrong.
• Suppose H finish in NO. That mean H predict H+(H+) will run forever. But by change two, when H finish in NO, H+ halt immediately. So H+(H+) halt. H predict wrong.

Both case: H predict wrong. But H promise to never be wrong. Contradiction. No third case.

The only assumption that start the chain is that H exist as a Turing machine. So that assumption is wrong. No Turing machine can be H. No Turing machine can solve the halting problem.

From this, with one more step, Turing show the Entscheidungsproblem is also impossible. If grug have a procedure to decide whether mathematical statement have proof, grug could use it to decide whether Turing machine halt. But no procedure can decide whether Turing machine halt. So no procedure can decide whether mathematical statement have proof. Hilbert last question: answered. The answer is no.

some question have no answer

Halting problem is the first known undecidable problem. Not "hard". Not "open". Undecidable. No algorithm can solve it for every input. Forever. Once Turing have one undecidable problem, big brain quickly find many more. The list is now long. Computer science have a permanent border.

This is the second border mathematics know about itself. First was Gödel. Now Turing. Both built on self-reference. Mathematics cannot prove its own consistency. Programs cannot decide their own behaviour. Knowledge from inside a system has limit. Most discipline never know they have a border. Mathematics know. Computing know.

Church get there first

Now grug must turn west, across the ocean, to Princeton, New Jersey. While Turing lie in Grantchester meadows in summer of 1935, another big brain already finish the same problem with completely different tools.

Big brain Alonzo Church born in Washington, year 1903. Older than Turing by about ten winter. Quiet, polite, methodical. Spend almost all his working life at Princeton. Speak slow, in whole paragraph, each word laid down evenly, like a talking machine. Begin every lecture by erasing the blackboard until it spotless, with water and soap and brush, then wait in silence while it dry, ten minute gone before a word. Cover his important paper in glue to preserve them. Big brain who not waste motion, but not hurry it either.

Through the late 1920s and early 1930s, Church doing what last tale show is dangerous. Trying to ground all of mathematics in pure logic. Same family of project as Frege and Russell. Princeton this time. Church build a big formal system, publish first version in 1932. He think it capture all of mathematics. Lambda calculus sit inside as one piece. Then in 1935, his own students Stephen Kleene and Barkley Rosser find a paradox in the bigger system. Not Russell letter from across the sea. His own students. Church lose a system. Not twenty-five winter like Frege. Just a few year. But the message same: cannot build a foundation that talk about itself without care. Church keep the part that survive. The part without paradox. The lambda calculus.

Notice the difference from Turing. Turing start from a person at a desk with paper and pencil. Watch what they do. Build a definition that copy it. Church start from inside symbolic logic itself. The Principia tradition. Big formal system, refined under fire from his own students until only the consistent piece remain. Turing work bottom-up, from the physical act of computing. Church work top-down, from the algebra of pure reasoning. Two big brain. Same question. Opposite direction. Same answer.

Heart of lambda calculus is one operation. Substitution.

Grug try to give the flavour. In lambda calculus, every expression is a function. The notation is λx.E. This mean "the function that take input x and return the expression E with x plugged in". So λx.x is the function that take an input and return the input. Identity function. To apply a function to an argument, write them next to each other. So (λx.x)(y) mean "apply identity to y". The rule say: replace every x in the body with y. Result is just y. That is the whole machinery. No state. No memory. No time. No tape. Just function and substitution.

Reader say: this cannot be enough to do real computing. But Church and his students show otherwise. They show how to encode number as function. Trick is simple once grug see it. A number is just how many time you do a thing. So give the function two input: a thing f to do, and a start x. Number 0 is the function that do f zero time and hand back x, untouched. Number 1 do f once: f of x. Number 2 do f twice: f of f of x. Number 3, three time. To ask which number you hold, count how many time it do f. That is the whole encoding. Adding is then another function: do f as many time as the first number say, then as many time as the second, and count the total. True and false are functions too. Conditional is a function. Recursion is a function. All of arithmetic, built from nothing but do this thing again. The whole thing look like an alien language. But it work. By 1935, Church convince himself that lambda calculus capture everything any mechanical procedure can compute. Anything a human computer can do by following definite rule can be expressed as a lambda expression.

Church present this idea at the American Mathematical Society meeting in April 1935. He propose it as a thesis: that the lambda-definable function are exactly the function any mechanical procedure can compute. Then in April 1936, Church publish An Unsolvable Problem of Elementary Number Theory in the American Journal of Mathematics. In it he prove the Entscheidungsproblem unsolvable. Using lambda calculus.

Seven moon before Turing paper come out.

Newman write painful letter

Turing finish his paper in spring of 1936. Before sending it for publication, he show it to Newman. Newman read it. Newman recognise at once it is important. Then in late May 1936, Newman receive in the post an offprint from Princeton. Sent by Church. Same problem. Same answer. Different method.

Newman write to Church on 31 May 1936. The letter survive. Newman tell Church plainly. The offprint, in Newman exact words, give a rather painful interest for a young man at Cambridge about to send for publication a paper proving the same thing by different method. Newman ask if it would still be possible to publish Turing paper. He explain that the methods are quite different. He hope the paper still find a place. Church reply with grace. Yes, Turing paper deserve publication. The methods are different. Both would be valuable. Church even agree to be the one who review Turing paper for the journal.

The paper come out in the Proceedings of the London Mathematical Society in two piece, both in 1936: first piece on the thirtieth day of November, second piece on the twenty-third of December. A short correction follow later, in 1938, after big brain Paul Bernays find some slip. The paper carry a note added by Turing acknowledging Church earlier work. Title: On Computable Numbers, with an Application to the Entscheidungsproblem. By then Turing already in America. He sail to Princeton in September 1936. Spend two winter studying with Church. They become colleagues. Turing complete a doctoral thesis under Church supervision in 1938.

two definition give same answer

Now the obvious question. Turing machine and lambda calculus look nothing alike. One have tape and head and time. Other have only function and substitution. One feel like a mechanic with dirty hands on a real procedure. Other feel like algebra in pure abstraction. How can they be the same? But they are. Turing prove it himself, in an appendix to the 1936 paper, after seeing Church work. He show every function computable by a Turing machine is expressible as a lambda expression, and the reverse. Same power.

Then a third definition come in. Big brain Kurt Gödel, in lectures at Princeton in 1934, define a class called the general recursive function, building on a sketch by big brain Jacques Herbrand. Same set. A fourth come from Emil Post, an American big brain, who in October 1936 publish a small note describing a system of finite combinatory process essentially equivalent to a Turing machine. Same set. Four definition, each reached by its own road, each completely different in style. Same set of computable function.

This is the Church-Turing thesis. The thesis say: mechanical procedure, the informal idea everyone use but nobody had defined, match exactly the set of function any of these formal system can compute. They all give the same answer. That answer is what computation is.

The thesis is not a theorem. Cannot prove. The thing on one side, mechanical procedure, is an informal idea. Like tall person or good food. The thing on the other side, Turing-machine-computable function or lambda-definable function, is a precise mathematical set. You cannot prove an informal idea equal to a formal set. You can only argue that the formal set capture the informal idea correctly. Many big brain try to find a counterexample. Try to imagine some procedure clearly mechanical, clearly an algorithm, that no Turing machine can carry out. Nobody find one. Ninety winter on, none. The thesis stand. Not from first-principle proof, but because every formal system anyone build confirm it. Most big brain treat it like physicist treat conservation of energy.

calculator and computer split

Out of this come a useful word. Turing complete. A formal system or programming language or physical machine is Turing complete if it can simulate any Turing machine. Turing completeness is the threshold separating a calculator from a computer. The Pascaline not Turing complete. It add and subtract. Cannot loop. Cannot conditional. Just calculator. Babbage Analytical Engine, in design, is Turing complete. Loop. Conditional. The full toolkit. A calculator you can program is a computer.

Below the threshold: limited, decidable, safe, useful in a narrow way.

Above the threshold: unlimited power. Undecidable in general. Useful in every way.

Either the system can simulate a Turing machine or it cannot. No middle.

two paths walk away

The two definitions look nothing alike, and that difference echo through computing.

Turing tradition: state and tape. Time exist. State change. Step follow step. Side effect everywhere. This is what hardware actually do. Wire carry voltage, voltage change, register update, clock tick. C, Java, Python, Rust follow this tradition. Read line by line. Like Turing machine.

Church tradition: function and reduction. No time. No state. Only the relationship between function and value. Apply function. Get result. No memory of what come before. Lisp follow this. Haskell, ML, Scheme follow this. Some part of every modern language follow this.

Both equivalent in power. Anything one compute, the other compute. But they feel completely different to write program in.

These tales follow Turing tradition all the way down. State and tape. Step by step. Because that is what the hardware will turn out to be. Church tradition live in a parallel world of functional programming language. Powerful world. Beautiful world. But not the world grug walk through here.

what grug learn

Two big brain in 1936 give two answer to the same question. Turing: state and tape. Church: function and substitution. They look nothing alike. They are equivalent.

The Church-Turing thesis say: this set of function is what computation is. Confirmed by every formal system anyone build. Above the threshold of Turing completeness, all the power and all the limits. Below it, just calculator.

The proof use self-reference. Build a thing that ask a question about itself. Watch the answer break. Third swing of the same hammer Russell swing, then Gödel. Probably not the last.

what grug worry about next

Turing machine work. On paper. But Turing machine is paper. Ink and pencil. There is no Turing machine made of metal anywhere in the world. Turing himself not interested in building one. He build the definition to answer a question in mathematical logic. He treat the machine as a tool of proof. The fact that it accidentally describe the limit of every computing machine ever built since is one of the great surprises in the history of ideas.

And meanwhile, Boole algebra of logic from 1847 sit on the shelf for almost a century. Real, working, correct. With nobody applying it to anything physical. Two piece. The mathematics of logic, since 1847. The mathematics of computation, since 1936. Both purely abstract. Both never wired up to anything.

Then in 1937, just one year after Turing finish his paper, a twenty-one winter old at MIT will read both Boole and Turing. He will notice that the open and closed state of an electrical switch behave exactly like Boole true and false. He will write a master's thesis that bridge the algebra of logic to the engineering of switches. The bridge will turn out to be the most important master's thesis ever written.

Grug come to him next.