Skip to content
Hallway
0:00 / 0:00

#haltingproblem#turingmachine#alanturing

Are There Problems That Computers Can't Solve?

Tom Scott

6.7M subscribers • 29 videos on Hallway

YouTube
  • Recommended by 1 person: 1 in engineering communities.
  • Presented by Tom Scott

Beginner. No background in the topic needed.

3.2M views6 years ago1 recommendation

Computer scienceHistory and cultureComputation and complexityHistory of computing

Tom Scott explains Hilbert's decision problem, Alan Turing's proof of the halting problem, and limits of computation.

All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: youtube.com/playlist?list=PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha Written with Sean Elliott twitter.com/SeanMElliott/ Graphics by Willow Marler wmad.co.uk Audio mix by Graham Haerther haerther.net/ 🟥 MORE FROM TOM: tomscott.com/ (you can find contact details and social links there too) ❓ LATERAL, free weekly podcast: lateralcast.com/ youtube.com/lateralcast/ 👥 THE TECHNICAL DIFFICULTIES: youtube.com/techdif

Why it's here

1 person recommends this

What people say. Recommended as an engaging explanation of the halting problem that prompts deeper questions about computability limits.

u/npinguyin r/compsci • Recommends

How do we know The Halting Problem isn't only impossible to implement for itself? I've been aware of The Halting Problem since university, but it's not until Tim Scott just did a video on it that I realized a basic question: Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist by coming up a counterexample that causes a paradox. That of course dismisses the possibility of "all" programs from being decideable. But is this result actually meaningful? Do we know of other relevant programs that cannot be evaluated? Or is it just a thought experiment?
123View on Reddit