Turing & The Halting Problem - Computerphile

Channel:Computerphile · Length:6:14 · Published:2014-08-21 · Views:921555

Watch on YouTube

Summary

A Computerphile video in which Mark Jago of the University of Nottingham explains Turing's halting problem and how it led to the blueprint for the modern computer.

Why HN recommends it

Offered as a short, clear explanation of the halting problem and its link to decidability.

Here's a short video on it — HN, 2021

Computability & complexity theory

Subtitles (excerpt)

Today we are going to be talking about a problem in logic and how in solving that problem, Alan Turing almost inadvertently invented the modern digital computer. So we start back at the beginning of the 20th century, where mathematicians had posed this problem - in logic we're interested in finding "Do these premises entail this conclusion?" So premises are the bits you start off with in an argument they are your -- the bits you know at the beginning or your assumptions and the conclusion is the bit you want to establish the bit that you reason to with your argument and we want to know is there a test that will tell us yes for sure these premises do or don't entail this conclusion. Is there an automatic way of finding out whether they do or whether they don't? So that's the problem, it's called the decision problem. The mathematicians wanted to find out "Is there an answer to the decision problem for first order logic?" that's the kind of logic you learn in philosophy or mathematics at university so lots of mathematicians were trying to work out is first order logic decidable that is can we automatically test whether the premises entail the conclusion Alan Turing was one of the first to discover that first order logic isn't

On Hacker News

>Like what? The halting problem is (I think?) the standard example. Here's a short video on it [VIDEO] — gammalost, 2021-06
For one practical example, Gödel's incompleteness is directly related to decidability problems in CS. there's this glorious liar paradox machine discussed by Computerphile [0]. [0] [VIDEO] — mar77i, 2019-12
no, it's all in software because you can create any smart contract and it can call any other. There is a difference in knowing after the transaction has finalized and predicting beforehand, which is when you would want to block the transaction. [VIDEO] — verdverm, 2022-08
In my view, this isn't really a software problem. Your plan is on the right track though. We already know its neigh impossible to ensure software is bug and vuln free. We have to reckon with the fact that secure software is possible, but extremely hard and impractical to achieve with any regularity. Because of well known computer science problems such as the Halting Problem[0] and more that I am … — cartoonworld, 2021-07

Related videos