Are There Problems That Computers Can’t Solve?
All about Hilbert’s Decision Problem, Turing’s solution, and a machine that vanishes in a puff of logic. MORE BASICS: https://www.youtube.com/playlist?list=PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha
Written with Sean Elliott https://twitter.com/SeanMElliott/
Graphics by William Marler https://wmad.co.uk
Audio mix by Graham Haerther https://haerther.net/
🟥 MORE FROM TOM: https://www.tomscott.com/
(you can find contact details and social links there too)
📰 WEEKLY NEWSLETTER with good stuff from the rest of the internet: https://www.tomscott.com/newsletter/
❓ LATERAL, free weekly podcast: https://lateralcast.com/ https://youtube.com/lateralcast/
➕ TOM SCOTT PLUS: https://youtube.com/tomscottplus
👥 THE TECHNICAL DIFFICULTIES: https://youtube.com/techdif
@TomScottGo
October 2, 2025 at 5:27 pm
Both my co-author Sean and I are worried that we're oversimplifying here — but then, this series is called The Basics!
@drstogiehead
October 2, 2025 at 5:27 pm
Who was Kurt Gödel?
@icaropassosmissel7435
October 2, 2025 at 5:27 pm
Problems no computer can solve are not problems but solutions
@tako_tech_tips
October 2, 2025 at 5:27 pm
My life, the economy, the human condition
@sontaclaws
October 2, 2025 at 5:27 pm
This can be explained in 3 words
The Halting Problem
@justdude7222
October 2, 2025 at 5:27 pm
This is interesting 🤔 but is this the same with AI?
@FriedMonkey362
October 2, 2025 at 5:27 pm
I may ne missing something but when you feed a program into "halts" weather or not it halts depends on the input of said program
Because a program can halt based on its input
When you dont give said input also to halts its impossible to say if itll halt
If you had a program
If (input == "something")
{
while(true)
{
print("something rude");
}
}
else
{
print("hello world");
}
This when you feed this program to halts it doesn't know the input and therefore cannot determine if something will halt
If you made "halts" but also made it take the given input that would be something thats possible to create
So when you feed "oposite" to "oposite" you must also provide the program that youd feed the "oposite" with and the input for that program as well
@emachine003
October 2, 2025 at 5:27 pm
Why am I watching this I took a whole class specifically about this
@danielberkovich2964
October 2, 2025 at 5:27 pm
5:41 But isn't that like saying you can't divide because dividing by zero is impossible?
@nagyandras8857
October 2, 2025 at 5:27 pm
That ain't no question . Computers can solve any problem , as long as we can properly ask them to do so. So the question is , can we describe every roblem properly ?
And Tourings findings says no.
@gauravverma5692
October 2, 2025 at 5:27 pm
Is that a BBC micro computer?
@WinstonSmith-ro
October 2, 2025 at 5:27 pm
i didnt understand anything in this video
@tosendeelemente7586
October 2, 2025 at 5:27 pm
I can solve this problem:
Yes it will halt
As every thing dose at some point the computer, humanity, the earth , the universe everything will halt it might restart but it will halt
@obscureskeleton
October 2, 2025 at 5:27 pm
how did you explain the halting problem in like 3 minutes and make it more understandable and simple then that animation i keep seeing explaining the same thing in the slowest most convoluted way possible.
@laughingman7882
October 2, 2025 at 5:27 pm
Bro explained in 4 minutes what Veritasium took 20 minutes to explain 😂
@goeuldi
October 2, 2025 at 5:27 pm
if(code.contains("while(true)") {…} 😎
@madontherun
October 2, 2025 at 5:27 pm
I finally get it after watching about 10 videos. Well done my man
@Larsh512
October 2, 2025 at 5:27 pm
Dividing by zero.
@WatermelonEnthusiast9
October 2, 2025 at 5:27 pm
Okay so, the machine reads the code right? So when it's looking at the code, the machine should not be changing it's own answer, you did not feed it itself in some Ouroboros type fashion, you just fed it the code. The machine will look at the code, see that there is a point somewhere it will halt, output yes, and loop forever. There is no paradox. There is no reason for it to change it's answer because it was not fed itself, it was fed it's code.
You can argue with me if it and it's code are different, I think that they are, you can argue if I'm being pedantic, I think it's an important distinction, but from what I can tell there is no paradox here.
Also I know I spell Ouroboros wrong, I don't know how to spell it, it's some weird Greek word. My point still remains.
@Synthematix
October 2, 2025 at 5:27 pm
Yes
Humans
@tihzho
October 2, 2025 at 5:27 pm
42
@Walker299
October 2, 2025 at 5:27 pm
Rust kinda solves this besides from logical issues
@Mici1234-star
October 2, 2025 at 5:27 pm
Me: trying to make a division function in assembly
@Pesti_Donat
October 2, 2025 at 5:27 pm
I dont think, this proof is true. What did I miss?
If this proof were true, that would mean we can prove with the same logic:
bool f( g : function ){
return not g();
}
is also an uncomputable function (simply by asking what f(f) returns).
Which makes no sense. If this were true, computability wouldn't have any practical meaning.
So the proof in those videos does not say anything about the problem of determining if a program will halt, but about the problem of recursively feeding a program itself as a parameter.
—————————————————–
Side note, in case my pseudo code is not clear:
The meaning of
bool f( g : function ){
return not g();
}
Is a program which needs a program as an input parameter. It runs the program, and returns with the negation of the result.
@legendgames128
October 2, 2025 at 5:27 pm
If you think Alan Turing is wrong, prove him wrong! All it takes is ONE counter example! I'll be waiting =)
bool decision_problem_solver(string program, string inputs[]) // written in C++, you could write this with Javascript, Python, or even on a Turing Machine, etc.
{
bool result;
// put your code here to look at "program" and determine if, given "inputs[]", does "program" halt? "result" should be true if it does halt, and "result" should be false if it doesn't.
return result;
}
@travisgrudzinskas8384
October 2, 2025 at 5:27 pm
This is what we have metaheuristics for
@davidothus191
October 2, 2025 at 5:27 pm
The problem is that Turing was trying to constrain the answer to yes / no when the answer to this and many other problems is outside of that paradigm and requires a greater description to give proper clarity. Often, like in the case of this paradox, the answer is outside of the scope of a simple yes / no..
@CWA19310
October 2, 2025 at 5:27 pm
Recent veritasium video…😅
@angelolampro5047
October 2, 2025 at 5:27 pm
so not only do we know some problems can't be solved, we also can't solve for which problems those are
@zackpane7973
October 2, 2025 at 5:27 pm
By what do you mean computer is at that point
Comments are closed.