Tracing Solvability. A historical, philosophical and mathematical anlysis, with a special focus on tag systems.

Period 01-10-2003 to 30-09-2007
Type Predoctoral Fellowship
Promotor(s) Prof. Dr. Erik Weber
Fellow Liesbeth De Mol
Funding agency Special Research Fund of Ghent University (BOF)

What do we mean when we say something is computable? This was exactly the question that lies at the roots of some results from the twenties and thirties, that, together with Gödel’s incompleteness results, touched upon the fundaments of mathematics and logic. Emil Post, Alonzo Church as well as Alan Turing showed there exist certain decision problems within the body of mathematics,  which cannot be solved through finite procedure, i.e. no algorithm will generate a solution in a finite time. Despite the mathematical character of this result, it is a philosophical kind of argumentation that is fundamental for these results: the proofs are only valid in as far one accepts the general thesis of identifying our intuitive notion of computability with certain formalisms such as Turing machines. It is exactly this identification that will be questioned within the context of this research. Closely related to this question is the link between the theoretical developments and methods within the context of unsolvability and the so-called “discourse” of the computational systems the theory is about. 
This research will consist of two parts. A first part concerns a more historical analysis of the notions computability and unsolvability, and starts from an analysis of the original texts by Church, Post and Turing.  It will be shown how the actual “discourse” of the formalisms developed by Church and Post (and to a lesser extent Turing) was fundamental for the formulation of their respective theses.  In this first part, it will furthermore be shown how the results by Church, Post and Turing, are connected to the physical realization of the notion of computability, i.e. the computer. The computer has made it possible to directly access the behaviour of the formalisms it can be considered the physical realization of, and, in this way, made more explicit the notion of experiment within the framework of mathematics. Furthermore, the computer plays an important role in the recent discussions one Turing’s thesis.
The second part of this research focuses on a a specific class of computational systems, called tag systems, developed by Emil Post in the early twenties. On the basis of a thorough study of these systems, it will be argued that research on the behaviour of certain computational systems  might be basic in the context of research on the limits of solvability. In this second part, computer experiments should thus be considered as an indispensable method. It will be shown here that tag systems could serve as a complementary framework to further study the limits of solvability: they are not only basic to the known small universal machines, but, as will be proven, a certain hard number theoretical problem called the Collatz-problem, can be reduced to a very small tag system. This last result indicates that the limits of solvability in tag systems are lower than those in Turing machines. Furthermore, it will be argued why tag systems can play an important role in the context of research on the solvability line, independent of the universality line. Finally, the study of tag systems, will be linked to the discussions on Turing’s thesis from the first part.