Computer Science & AI · 1936
On Computable Numbers, with an Application to the Entscheidungsproblem
Alan M. Turing
Overview
Turing introduced an abstract machine — now called the Turing machine — to make 'computation' precise. He used it to prove that some problems are undecidable, settling Hilbert's Entscheidungsproblem in the negative and founding the theory of computation. (Read in 1936; published in the 1937 volume.)
Founded theoretical computer science and defined the limits of computation.
Key findings
Methods
A constructive mathematical argument: Turing formalised mechanical computation as symbol manipulation by an abstract machine, then used a diagonalisation argument to exhibit a non-computable problem.
Keywords
Related papers
Computer Science & AI
Highly Accurate Protein Structure Prediction with AlphaFold
AlphaFold solved a 50-year grand challenge in biology: predicting a protein's three-dimensional shape from its amino-acid sequence. Its accuracy approached that of experimental methods, transforming structural biology.
Computer Science & AI
Attention Is All You Need
The paper that introduced the Transformer, an architecture built entirely on attention mechanisms with no recurrence or convolution. It became the foundation of modern large language models such as GPT and BERT.
Computer Science & AI
Mastering the Game of Go with Deep Neural Networks and Tree Search
AlphaGo became the first program to beat a professional human at the ancient board game Go, long considered a grand challenge for AI because of its astronomical complexity. It combined deep neural networks with Monte Carlo tree search.