By William Troiani, The University of Melbourne
What can and can’t a computer do This question is central to the area of Mathematics now referred to as computability theory. In the early 1900’s, there was interest in not only finding solutions to specific questions in mathematics, but also in finding algorithms which can solve these problems for us. The first step towards achieving this is to first answer the question “what is an algorithm”?
Godel, Church, and Turing all came up with different looking, but logically equivalent definitions of exploring what kinds of problems can be solved by following an algorithm, and what kinds of problems can’t. Perhaps surprisingly, there are some general problems for which there exists no algorithmic solution. For example, it has been proven that there exists no algorithm which takes as input a mathematical statement, and returns “true” if the statement is true, and “false” if the statement is false. Note: the phrase “Mathematical statement” here means a statement of 1st order logic.
For this project, we focused on Church’s approach, which is that of the lambda calculus. Essentially, lambda calculus is a formal language used to describe functions. According to Church, an algorithm is a list of instructions to follow, where the tasks in the list can be described and executed in this language.
There has been a huge rush of developments in computer science over the past fifty years, and it is natural for one to wonder what the effects this explosion has had in the world of Mathematics. Alongside this muse, one might also consider the fact that it is frequently mentioned how hand in hand Pure Mathematics goes with Computer Science. This is an example of a somewhat strange phenomenon where the strength of such a connection seems so obvious, that one can’t help but to feel almost embarrassed when the inevitable realisation that explicit relationships are actually far from common knowledge comes to dawn. Alas, such relationships do exist, and they extend beyond the monogamy of Mathematics and Computer Science, indeed certain areas of Logic also become helpful along the way. We wish to explore such connections, whilst coming to grasp with the foundations of these topics outside of Mathematics, as this content is rarely introduced at undergraduate level, at least as far as the Mathematics department is concerned.