Mechanizing Computation

In 1935, a pivotal moment at Cambridge University saw a young mathematics student, Alan Turing, encounter the decision problem. His fascination with this challenge led him to ask: Is there a mechanical process that, in finite steps, can determine the truth of any proposition in predicate logic? Turing's quest for an answer revolutionized our understanding of computation.

Turing envisioned computation not as an abstract activity, but as a mechanistic process. He imagined a human computer, methodically writing symbols on paper, and abstracted this into a linear sequence of boxes, each containing a symbol. As the human's attention shifted from box to box, changing symbols and states, Turing saw the foundation for a new kind of machine. This machine, which he later termed the "Turing Machine," would operate on simple rules: moving between boxes, reading and writing symbols, transitioning through finite states. Turing's machine was not just a theoretical construct; it embodied a universal model for computation, capable of simulating any calculation or logic function.

The implications of Turing's work were profound. He demonstrated that no machine, not even his Turing Machine, could resolve the decision problem, as such a capability led to paradoxes. This revelation, however, did not diminish the impact of his work; rather, it laid the groundwork for the future of computing.

In the years following Turing's breakthrough, the development of electronic digital computers like UNIVAC and BINAC realized his vision of mechanized calculation and reasoning. Turing referred to these as 'a-machines', highlighting their automatic nature. They were the culmination of a dream: to make computation accessible to all, not just the expert calculators.

Yet, Turing also recognized the limitations of these automatic computers. He proved that certain tasks, such as determining the outcome of a program or detecting a virus, were beyond the capabilities of any machine. This acknowledgment has shaped the field of Computational Theory (CT), which focuses on finding partial solutions to problems that automatic computers cannot solve.

Turing's merger of calculation with logic has had a lasting impact, underscoring logical thinking as an essential component of computational thinking. His work remains a cornerstone in the field, a testament to the power of combining logical thought with the potential of machines.