Skip to content
Hallway
0:00 / 0:00

#haltingproblem#turingmachine#alanturing

Turing & The Halting Problem - Computerphile

Computerphile

2.6M subscribers • 70 videos on Hallway

YouTube
  • Recommended by 2 people: 2 on Hacker News.
  • Presented by Mark Jago, Assistant Professor at the University of Nottingham

Beginner. No background in the topic needed.

919K views12 years ago2 recommendations

Computer scienceComputation and complexityAlgorithmsHistory of computing

Mark Jago explains Alan Turing's halting problem and how it demonstrates the fundamental limits of what computers can solve.

Alan Turing almost accidentally created the blueprint for the modern day digital computer. Here Mark Jago takes us through The Halting Problem. Turing Machines Explained: youtu.be/dNRDvLACg5Q Busy Beaver: youtu.be/CE8UhcyJS0I VR Simulator: youtu.be/Lm0lA0enPSk What on Earth is Recursion?: youtu.be/Mv9NEXX1VHc Thanks to Assistant Professor Mark Jago of the University of Nottingham. facebook.com/computerphile twitter.com/computer_phile This video was filmed and edited by Sean Riley. Computer Science at the University of Nottingham: bit.ly/nottscomputer Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels

Why it's here

2 people recommend this

What people say. Recommended as a clear, short explanation of the halting problem and its implications for computability.

Moments people linked to

mar77ion Hacker News • Recommends

On “Kurt Gödel and the Mechanization of Mathematics”

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 link to this video
View on Hacker News

gammaloston Hacker News • Recommends

On “DeepMind says reinforcement learning is ‘enough’ to reach general AI”

>Like what? The halting problem is (I think?) the standard example. Here's a short video on it link to this video
View on Hacker News

u/thenerdstationin r/compsci • Mentions

Question on the halting problem Using the example here The H Turing machine requires 2 inputs, one of another TM and one of its input. But when you make H both of its input, the simulated H only has 1 input instead of its required 2. Doesn't that mean that the input is ill formed?
5View on Reddit

u/Pour_Louisin r/compsci • Mentions

On “Impossible Programs: video explaining the Halting Problem (using Cantor's diagonalization)”

link to this video Computerphile always does a good job of explaining things
4View on Reddit

cartoonworldon Hacker News • Mentions

On “Up to 1,500 businesses affected by ransomware attack, Kaseya CEO says”

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 Problem0 and more that I am totally ignorant of, the only alternative is extremely thorough verification like happens in planes1. The rub is that unlike aerospace and other critical controls, we cannot define the software security problem as closely as is possible in those other critical systems. Doing so will undo the benefi…
View on Hacker News

verdvermon Hacker News • Mentions

On “Tornado Cash and collateral damage”

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. link to this video
View on Hacker News

u/earlnwin r/compsci • Mentions

I want to confirm if I understand the halting problem. resources I used for research https://www.reddit.com/r/explainlikeimfive/comments/2ec9hv/eli5\_the\_halting\_problem\_in\_computer\_science/ [video I have a few question about the halting problem. The halting problem is the idea is that a machine for every computer program that can tells me if the program halts or does not halts. I then feed the output of the machine as input into the same machine. So the input that is fed into the machine gives me halt or infinite loop. The second time I feed the information into the machine I get again two results. The results are if an infinite loop it it halts. The other result is…
0View on Reddit