Why Alan Turing is a hero to programmers

We in the programming world have few heroes. That is, we have few heroes who are programmers. There are people such as Bill Gates and Steve Jobs, but they were businessmen and visionaries, but not programmers.

Yet we do have a few heroes, a few programmers who have risen above the crowd. Here is a short list:

Grace Hopper Serving in the Navy, she created and advocated the idea of a compiler. At the time, computers were programmed either by wire (physical wires attached to plug-boards) or with assembly language. A compiler, converting English-like statements into machine instructions, was a bold step.

Donald Knuth His multi-volume work The Art of Computer Programming is a comprehensive work, comprising machine design, assemblers, compilers, searching, sorting, and the limits of digital computation. He also created the TeX language and the notion of "Literate Programming".

Brian Kernighan and Dennis Ritchie Created the C language.

Larry Wall Creator of the Perl language; also the creator of the 'patch' program used to apply changes across systems.

Fred Brooks The chief designer of IBM's operating system for the System/360 computers, his book The Mythical Man-Month has several interesting observations on the teams that construct software.

Gerald Weinberg Known for his books on system analysis and design, I find his work The Psychology of Computer Programming much more useful to programmers and program team managers.

All of these folks are (were) smart, creative, and contributors to the programming art. Yet one has a special place in this list: Alan Turing.

Alan Turing, subject of the recent movie "The Imitation Game", has made significant contributions to the programming craft. They are:

• Code-breaking in World War II with the Bombe computer
• The Turing Test
• Turing Machines
• The Halting Problem

All of these are impressive. Turing was many things: mathematician, biologist, philosopher, logician.

Of all of his accomplishments, I consider his proof of the halting problem to be the one act that raises him above our other heroes. His work with code-breaking clearly makes him a programmer. His idea of the Turing Test set clear (if perhaps unreachable) goals for artificial intelligence.

The notion of Turing machines, with the corresponding notion that one Turing machine can emulate another Turing machine is a brilliant insight, and enough to make him a hero above others.

Yet it is the halting problem, or more specifically Turing's proof of the halting problem (he proved that one cannot tell, in advance, that a program of sufficient complexity would be guaranteed to stop) is what pushes him across the line. The proof of the halting problem connects programming to mathematics.

Mathematics, of course, has been with us for centuries. It is as old as counting, and has rigorous and durable proofs. Euclid's work is two millennia old, yet still used today. It is these proofs that make mathematics special - math is the "Queen of the Sciences" and used by all other branches of knowledge.

Mathematics is not without problems. There is a proof called the Incompleteness Theorem, which states that any system of axioms (rules) that includes integers, there exist theorems which are known to be true yet cannot be proved with that system of axioms. (The Incompleteness Theorem also states that should you add an axiom to the system to allow such a proof, you will find that there are other theorems which are known to be true but not provable in the new system.)

That sounds a lot like the halting problem.

But the Incompleteness Theorem is the result of thousands of years of study, and computing is young; we have had digital computing for less than a century. Perhaps we can find another corresponding mathematical surprise, one that occurred earlier in the history of mathematics.

Perhaps Turing's proof of the halting problem is closer to the discovery of irrational numbers. The Greek philosophers were enchanted with mathematics, bot geometry and arithmetic. The reduction of physical phenomena to numbers was a specialty for them, and they loved integers and ratios. They were quite surprised (and by some accounts, horrified) to learn that numbers such as the square root of two could not be represented by an integer or a ratio of integers.

That kind of problem sounds close to our halting problem. For the Greeks, irrational numbers broke their nice, neat world of integers. For us, the halting problem breaks the nice, neat world of predictable programs. (To be clear, most of our programs do run "to completion" and halt. The theory states that we cannot know in advance that they will halt. We simply run them and find out.)

Turing gave us the proof of the halting problem. In doing so, he connected programming to mathematics, and (so I argue) us early programmers to the early mathematicians.

And that is why I consider Alan Turing a hero above others.