Challenging the frontiers of computability: On the legacy of the Church-Turing thesis and its significance in the twenty-first century

Abstract

When Alan Turing and Alonzo Church proposed their formal characterizations of the process of computation in 1936, the word “computation” simply referred to human calculation as performed with the help of paper and pencil. Their work inspired the development of computing machines and sparked an unprecedented revolution that to this day continues to impact our daily lives. Intuitively, it seems plausible to expect that somewhere in the course of this dramatic technological growth, through innovations such as the internet and artificial intelligence, a more sophisticated type of computation has emerged that transcends the “primitive” process of human computation as modeled by the Turing machine. Several authors have argued that this is the case.

After laying a solid theoretical and historical foundation, this thesis analyzes a collection of articles by Jan van Leeuwen and Jiří Wiedermann in which the authors assert that the interplay between three particular ingredients of modern computation gives rise to properties that cannot be modeled by a classical Turing machine. I argue that on the contrary, on the most fundamental level modern computation still relies on the same primitive principles as it did in 1936, and that the three ingredients proposed by Van Leeuwen and Wiedermann can in fact be modeled quite elegantly with a classical Turing machine.