Joint Pure Math/C&O Grad Colloquium

Rian Neogi, Combinatorics & Optimization, University of Waterloo

"The Birth of Computation"

In 1928, Hilbert posed the Entscheidungsproblem, which is informally stated as follows: "Given a mathematical statement, is there a well-defined procedure by which one can decide whether the statement is true or false?". This is a natural question for mathematicians to ask. Essentially the question asks whether one can solve mathematical problems in some automatic and structured manner, or must we rely on human insight, wit and intuition?

In order to answer this question, one must formally define what a 'procedure' is. In 1936, Turing gave an answer to Hilbert's problem. Turing's formalization of 'procedure' led to the notions of algorithms and computation, and gave birth to the field of computer science. In this talk, we will explore Turing's work. We will answer some fundamental questions about computation:

• What functions can be computed, and what functions can't?
• Can one write a program that gives a proof (or disproof) of a mathematical statement?
• Can one write a program that is able to predict the behavior of another program?

If time permits, we will also take a look at modern theory of computation and how the mathematical community has built upon Turing's ideas over the years.

MC 5501