Turing & The Halting Problem - Computerphile
Channel:Computerphile · Length:6:14 · Published:2014-08-21 · Views:921555
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
- Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim Weirich · Confreaks · 53:21
- 28c3: The Science of Insecurity · 28c3 · 59:23
- "Propositions as Types" by Philip Wadler · Strange Loop Conference · 42:43
- Break Me00 The MoVfuscator Turning mov into a soul crushing RE nightmare Christopher Domas · Adrian Crenshaw · 46:19
- Math's Fundamental Flaw · Veritasium · 33:59
- On The Turing Completeness of PowerPoint (SIGBOVIK) · Tom Wildenhain · 5:33
- Life in life · Phillip Bradbury · 1:30
- Lambda Calculus - Fundamentals of Lambda Calculus & Functional Programming in JavaScript · Fullstack Academy · 1:02:15
- All the Numbers - Numberphile · Numberphile · 14:26
- P vs. NP and the Computational Complexity Zoo · hackerdashery · 10:44
- Ruby Manor 3 - Programming with Nothing by Tom Stuart · Confreaks · 40:49
- David Beazley - Lambda Calculus from the Ground Up - PyCon 2019 · PyCon 2019 · 3:26:34
- Great Impractical Ideas in Computer Science: PowerPoint Programming · Tom Wildenhain · 51:32
- Matt Might - Winning the War on Error Solving the Halting Problem and Curing Cancer · Curry On! · 48:36
- Stephen Wolfram: Cellular Automata, Computation, and Physics | Lex Fridman Podcast #89 · Lex Fridman · 3:11:08
- Let's #TalkConcurrency Panel Discussion with Sir Tony Hoare, Joe Armstrong, and Carl Hewitt · Erlang Solutions · 1:06:44