Turing was not alone in thinking about computers in the early part of the past century. Mathematicians had been thinking about computable functions for some time. Turing drew from colleagues' work at Princeton University during the 1930s. There, Alonzo Church was defining Lambda calculus (which later formed the basis of the Lisp programming language). And Kurt Gödel worked on the incompleteness theory and recursive function theory. Turing employed the work of both mathematicians to create a conceptual computing machine.

His 1936 paper described what would later become known as the Turing Machine, or a-machine as he called it. In the paper, he described a theoretical operation that used an infinitely long piece of tape containing a series of symbols. A machine head could read the symbols on the tape as well as add its own symbols. It could move about to different parts of the tape, one symbol at a time.

"The Turing machine gave some ideas about what computation was, what it would mean to have a program," said James Hendler, a professor of computer science at the Rensselaer Polytechnic Institute and one of the instrumental researchers of the . "Other people were thinking along similar lines, but Turing really put it in a formal perspective, where you could prove things about it."

On its own, a Turing Machine could never be implemented. For one, "infinite tapes are hard to come by," Kahn joked. But the concept proved invaluable for the ideas it introduced into the world. "Based on the logic of what was in the machine, Turing showed that any computable function could be calculated," Kahn said.