Alan Turing and the Decision Problem

Alan Turing Year

授课人:Richard Zach

机构:Pacific Institute for the Mathematical Sciences(PIMS)

关键词: Scientific;    Mathematics;    Computational Complexity;    Discrete Mathematics;    Information Theory and Cryptography;    Logic and Foundations;    Computer Science;   

加拿大|英语

【 摘 要 】

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 first 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). In order to show that there cannot be a systematic computational procedure that solves every mathematical question, Turing had to provide a convincing analysis of what a computational procedure is. His abstract, mathematical model of computability is that of a Turing Machine. He showed that no Turing machine, and hence no computational procedure at all, could solve the Entscheidungsproblem.

【 授权许可】

CC BY-NC-ND   
Except where explicitly noted elsewhere, the works on this site are licensed under a Creative Commons License: CC BY-NC-ND