The halting problem

Alan Turing Alan Turing is best known for his role in breaking the Enigma cipher during World War II, which significantly aided the Allied war efforts against Nazi Germany. He is also considered a father of theoretical computer science and artificial intelligence. Beyond these accomplishments, his theoretical work in the mid-20th century laid the groundwork for modern computing. The Halting Problem The halting problem, introduced by Turing in his seminal 1936 paper titled “On Computable Numbers, with an Application to the Entscheidungsproblem,” addresses a basic question: Is there a general algorithm that can determine whether any given program will eventually stop running (halt) or will run indefinitely? [Read More]

Turing & The Halting Problem - Computerphile Alan Turing almost accidentally created the blueprint for the modern day digital computer. Here Mark Jago takes you through The Halting Problem. The Halting Problem - An Impossible Problem to Solve One of the most influential problems and proofs in computer science, first introduced and proved impossible to solve by Alan Turing. The video provides the idea of this incredibly clever proof. Understanding the Halting Problem The halting problem is an important problem in computer science that asks whether we can construct an algorithm to determine whether a computer program will run forever. [Read More]

Is there a problem with the proof?

Almost no one believes that.

Turing Machines Explained - Computerphile Turing Machines are the basis of modern computing, but what actually is a Turing Machine? Assistant Professor Mark Jago explains. Turing Machines - How Computer Science Was Created By Accident Turing machines explained visually A Turing machine is a model of a machine which can mimic any other (known as a universal machine). What we call "computable" is whatever a Turing machine can write down. [Read More]