Skip to content
Hallway
0:00 / 0:00

#haltingproblem#alanturing#undecidability

Proof That Computers Can't Do Everything (The Halting Problem)

udiprod

158K subscribers • 2 videos on Hallway

YouTube
  • Recommended by 4 people: 4 in engineering communities.

Beginner. No background in the topic needed.

2.7M views13 years ago4 recommendations

Computer scienceComputation and complexityAlgorithms

An animated video explains Alan Turing's Halting Problem and why some computational problems are undecidable.

If you disagree or get confused by this video, read this FAQ: udiprod.com/halting-problem/#faq Visit my home page: udiprod.com This video gives an informal presentation of Alan Turing's Halting Theorem, a serious, highly influential result in computer science. A few more comments on this video: 1) This video skips a lot of technicalities for sake of simplicity. There are many rigorous descriptions of this proof easily found on the web. 2) There really is an unbeatable checkers machine. See here: en.wikipedia.org/wiki/Draughts#Computer_draughts

Why it's here

4 people recommend this

What people say. Recommended as a clear, simple, and highly visual explanation of the halting problem.

u/TheHumanParacitein r/compsci • Recommends

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

I agree, the Mr Smith shit was way off the mark for making it understandable. Here is a better explanation for anyone interested link to this video
16View on Reddit

u/saihtamtellimin r/compsci • Recommends

On “What is an uncomputable function?”

link to this video Try and watch this, it's just a simple animation explaining the halting problem (an uncomputable, or, rather undecidable function). Well made and easy to wrap one's head around it.
12View on Reddit

u/MagicallyVermiciousin r/compsci • Recommends

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

I think the problem is in the visual language of your video when using the Mr. Smith analogy. You don't have a clear way of presenting the cause-and-effect of how X uses H, as in the link to this video that /u/TheHumanParacite linked. You abstract away the key fact about computer programs being a series of instructions, and don't show how inputting X to machine X causes H to simulate feeding X to X, and how the output of that simulation causes the real machine X to do the opposite of the prediction, thus causing a contradition. At 3:09 to 3:25 in your video, you show the oracle with a car in her crystal ball and then slide in (real) Mr. Smith in standing position. Then you jump cut and show in the cry…
3View on Reddit

u/wolfman1911in r/compsci • Recommends

The halting problem: can anyone explain this to me in a way that doesn't sound pedantic?
0View on Reddit

u/MegaIngin r/compsci • Mentions

On “re: turing's diagonals”

To quote the first remark from the page you linked: > The undecidability of the halting problem itself certainly has proofs that arguably do not invoke diagonalization (some of them are listed here). ***READ STUFF***. You are not exceptional, neither am I. There are 50+ years of computer sciences to look back on, please do that instead of trying to invent new techniques after one day of university. (in fact that link provided is even more restrictive than what you want since it also forbids self-reference which is the most common way I have seen the Halting problem being solved. E.g. in this video)
4View on Reddit