[Alta-Logic] Alan Turing Centenary Lecture Series: Alan Turing an the Decision Problem (Jan 24)

[Richard Zach]

2012 marks the centenary of Alan Turing, mathematical genius, WWII
codebreaker, pioneer of computing, and gay icon. The Departments of
Computer Science and Philosophy with support from the Faculties of Arts
and Science as well as the Pacific Institute for the Mathematical
Sciences are holding a series of lectures on Turing's life and work
throughout 2012.

ucalgary.ca/turing
facebook.com/TuringYYC


Alan Turing and the Decision Problem

Richard Zach, Department of Philosophy

Tuesday, January 24, 4-5:30 pm, ICT 122
http://ucalgary.ca/turing/node/6

Many scientific questions are considered solved to the best possible
degree when we have a method for computing a solution.  This is
especially true in mathematics and those areas of science in which
phenomena can be described mathematically: one only has to think of the
methods of symbolic algebra in order to solve equations, or laws of
physics which allow one to calculate unknown quantities from known
measurements.  The crowning achievement of mathematics would thus be a
systematic way to compute the solution to any mathematical problem.  The
hope that this was possible was perhaps first articulated by the 18th
century mathematician-philosopher G. W. Leibniz. Advances in the
foundations of mathematics in the early 20th century made it possible in
the 1920s to precisely formulate the question of whether there is such a
systematic way to find a solution to every mathematical problem. This
became known as the "decision problem", and it was considered a major
open problem in the 1920s and 1930s.  Alan Turing solved it in his
first, groundbreaking paper "On computable numbers" (1936), by showing
that no such procedure can exist.  In order to do this, Turing had to
provide a convincing analysis of what a computational procedure is. His
abstract, mathematical model of computability is now known as the Turing
Machine model of computation.