Are There Problems That Computers Can't Solve?
Вставка
- Опубліковано 7 лют 2025
- All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: • The Basics
Written with Sean Elliott / seanmelliott
Graphics by William Marler wmad.co.uk
Audio mix by Graham Haerther haerther.net/
🟥 MORE FROM TOM: www.tomscott.com/
(you can find contact details and social links there too)
📰 WEEKLY NEWSLETTER with good stuff from the rest of the internet: www.tomscott.c...
❓ LATERAL, free weekly podcast: lateralcast.com/ / lateralcast
➕ TOM SCOTT PLUS: / tomscottplus
👥 THE TECHNICAL DIFFICULTIES: / techdif
Both my co-author Sean and I are worried that we're oversimplifying here -- but then, this series is called The Basics!
Tom Scott nice video
Sometimes you just have to simplify things, or else, you'll spend days talking about subjects
Are you going to talk more about BASIC
Basic Bro
Keep the complexities basic
When you try to solve a mathematical problem so hard that it turns into a philosophical one.
Was this a mathematical problem ?
Was a mathematical computer the right tool to use in this instance ?
Mathematical proof is based on philosophy
It's to opposite.
The original problem is philosophical: "Is there a chance, even the slightest, that maybe some day far in the future we will have answers to all questions in the universe?"
Maths and logic brought the definitive answer: "Nope. We can prove that it's impossible with just the subset of mathematical questions. And the full set of all questions is far larger than that."
Mathematics is actually a branch of philosophy, so... technically every mathematical problem is philosophical.
Maths is essentially philosophy
+1 for vanishing in a puff of logic...
Alan Turing was also a vanishing puff
careful where you stick the fish
Yes, I'm tempted to make a rude comment about Alan Turing. Just I don't want to.
Babel fish go brrrrrr
@@lightlysalted7790 Don't panic
Tom’s way of speaking is always so engaging. You just feel inclined to listen to him and it’s so easy to follow along. Glad this guy decided to become an educator, it’s always a pleasure!
Imagine having him as like a lecturer or teacher. It'd be great
I have a video of him explaining things at my school.
(edit) it's the one on my channel
XBC Video
Link? Asking for a friend
Well said!
I agree
Fun Fact: you can build a fully functioning Turing machine within the rules of Magic: The Gathering and given a perfect starting hand you can even set it up legally in a tournament game. There’s even a paper on that, for those that are interested.
Could I have the source?
@@kasoy5239 I believe Kyle Hill did the video Fabian is referring too.
@@Malaphor2501 link?
@@Malaphor2501 link?
@@Malaphor2501 Link?
Yes. Try to ask my computer why the internet is down.
Surely it can Google the answer.
@@theblackwidower well if you have only one internet access then it's not possiblle to google the answer xD
@AlphaGT
r/whooosh
Or just ask the computer to read a captcha.
@@TauCu hey thanks I haven't got this in a while
Socrates: "The next thing Plato says will be false."
Plato: "Socrates has spoken truly."
prints " thats deep "
* infinitely *
This is hurting my brain.
This doesn't seem paradoxical, please can someone explain? It seem that socrates is just wrong here.... Or plato is wrong theres no loop here
@@anim8dideas849 If socrates is wrong then plato is wrong, which makes socrates correct, etc etc
When two people lie and a third person doesn't understand complicity and deception, then they are truly more stupid than machines.
"Is 'no' the answer to this question?"
Computer dies
Meanwhile Human: "Yesn't"
A computer can be made to recognize that "answer" and "response" aren't synonymous. Hell, any automatic grading system already knows just putting text in the box doesn't mean you put the right answer.
Probably not
It could just answer it in a different language.
Definitely.
Me: “this is really complicated”
Tom: “sorry for massively over-simplifying”
That's literally the best flex for every "nerd" to say lmao
The core of the idea is simple, proof by contradiction that you can always create. But to actually *prove* that that proof works requires a college computer science course. Hence massive oversimplification. The main takeaway is that a "universal computer" *isn't.* Some things are inherently non-computable. Theory of Computation is then the branch of computer science that tries to figure out what those things are and aren't, among other things.
It is massively over-simplifying. There is a reason why there are half-a-semester course on just this particular subject. If you don't want simplify / to gloss over the details, and actually fully understand the details. Then it takes a very long time to explain.
@@tylisirn No offense but my brain had a seizure reading this im so sorry for my dumbass not understanding..
@@LowBudgetJustinY Computer compute many computations but not all. Smart people compute what computations computers cannot compute.
6:11 "Vanishes in a puff of logic" is one of the best Hitchhiker's Guide references.
Computers are logic machines at their core. It's an important class in Computer Science programs, because underneath at the most base level chips just send electrons through AND, OR, NOR, etc gates incredibly fast. And that same logic can bubble up into even high level languages.
haha yes I knew I couldn't be the only one to get that reference!
Also a NetHack reference.
42
Also important, various other forms of logic will sift down from very high level language theories and inform the nature of types and programs, so logic ends up being in both directions when it comes to computers.
So that means redstone is technically a computer, because of all those logic gates.
This actually ended up being an extremely important discovery, as ever since this there have been many other problems that have likewise been proven to be uncomputable, most often by finding a way for "If we CAN compute X, then by doing Y and Z we can then use X to solve the Halting Problem." But as we know that's impossible, then X must ALSO be uncomputable.
I wonder is that has resulted in people ruling out things that almost solve the halting problem.
It wasn't a discovery; philosophers had already contemplated the "this statement is false" concept long ago; Turing merely framed it in computer terms.
@@TheAkashicTraveller it is definitionally impossible to solve the halting problem. You can't almost solve something. It's a binary thing: either it's solved or not. An unsolvable problem isn't unsolvable because it's difficult to solve, it's unsolvable because it is a logical impossibility. The problem inherently contradicts itself.
@@user-vn7ce5ig1z Keep in mind though, there are a lot of ways to resolve this "this statement is false" "paradox", but you can't do that for the halting problem
It reminds me of np problems and how you can convert from one to any others, so that if you show one np is p, then all are.
David Hilbert: "I look very smart and trustworthy. Therefore I will wear this hat to dispel that image."
Was looking for this comment.
I think the hat makes him stand out amongst other mathematicians
I mean, it makes him quite a bit taller. Probably easy to find in a room.
True.
The above statement is false.
We need some symbolic notation to be sure
1:52
That word is pronounced "Entscheidungsproblem"
You're welcome.
@ilimango and he's being sarcastic x3
ilimango r/wooooosh
Ents-schei-dungs-problems
Zaymly
woooosh has 4 o’s
@Zaymly r/foundthemobileuser
I told my computer to try and imagine Tom Scott had a different colored shirt besides red and it exploded
paint bucket in photoshop
How much TNT?
lmao
You need to download 256 GB RAM to make it possible
420th like
"Any program that you write in any programming language can be converted into something you can run on a Turing machine."
So... Another thing you can run doom on?
Well I wouldn't put it past Bethesda to port Skyrim to a Turing machine.
Sent from my Turing machine
But can it run crysis?
@@7_7_5 Given enough tape, yes, it can
@@jimmydiaz1502 Can a Turing machine overheat? The answer is no.
Can any computer run Crysis without overheating? The answer is also no.
Run Crysis on a Turing machine - get another paradox.
People don't realize the mindblowing genius that was Alan Turing. Not only did he invent the modern computer in his HEAD. He even went as far to measure its potential when he didn't even know anything about the philosophies of coding, memory management, storage management and general computer science. I think he was a product of an alien species that wanted to push is into the next age.
Fr
"Are there problems that computers can't solve?"
INSUFFICIENT DATA FOR MEANINGFUL ANSWER
I came here for this.
In the end, there was nothing.
Or was it the beginning?
Is that a SCP reference?
@@adityapathak5761 No, it's a reference to Isaac Asimov's short story "The Last Question"
It has always struck me that the problem of The Last Question was improperly translated for the Multivac, Adell and Lupov was, after all, discussing having an eternal source of energy and the possibility of escaping the inevitability of entropy, but what they asked Multivac was how to reverse entropy.
Rather than working on some way to win "The Game" the ACs were working on some way to replay the same game.
So, humanity in that story is stuck in a time loop, one of many trillions of years, but still, they are doomed to replay this one timeline forever. Though, I suppose that is really the fate of any character in any form of linear literature or story telling...
"It's a paradox, there is no answer!"
-A Computer Says To Another Computer In Portal 2
@real gamer hmmm... TRUE
Um... I’ll go true. Eh that was easy
Nice try, but my head was built with paradox-absorbing crumple zones.
I AM NOT A MORON
@@duncanhw that was a quote ;)
One of my college math professors with "Scott" in his name introduced this problem to me, and another professor with "Sean" in his name taught me about Turing machines. Now I'm seeing a script written by someone "Sean" and some "Scott" talking about those topics on UA-cam. What a moment.
You are the lucky pigeonhole in the pigeonhole problems
This compliments the concept of the "opposite" machine bizarrely well
Will this code halt or loop?
Quantum Computer: *"Yes"*
Actually, that is the solution. This problem IS SOLVABLE as of 2020, when a team of 5 compscis solved the halting problem using quantum entanglement.
@@jamielonsdale3018 nice! Do you have a link to the paper, I would love to read it?
@@jamielonsdale3018 lmao no
@@MegaAgamon I'll have a look when I finish my shift :)
well, actually
Quantum Computer: "Yes, No, Yes and No"
Tom: "The, uh. The... Uh. The. Decision Problem"
Me: (laughs in german)
same
Same lul
Laughs in Dutch
*laughs in bilingual*
germans laugh?
"Vanishes in a puff of logic"
The bablefish really was far too convienient
Finally watched a Tom Scott video that isn’t from 3 years ago!
This comment's gonna be really funny in 3 years.
Yum.
I know that feeling
Ive started from 10yrs ago video, watched a bunch of 3yrs ago video and i m here now and this comment makes sense
I can totally relate to this
God, what a focus. Explaining this kind of subject perfectly for 8 minutes straight isn't for everyone
you know tom is working hard when the pinned comment was 4 hours ago instead of 2 weeks to a month
"And that boss, is why I didn't bother checking my code with different cases, 'cause what's the point eh ?"
10/10
Case in point.
hahaha best comment!
AC at the end of the Asimov story:
“Ah, the one unsolvable problem. How annoying. Lemme jus infer the answer from available data, test it, reject if wrong, loop infinitely till solution reached, Let There Be Light and done”
Edit: what the hell happened down there guys
INSUFFICIENT DATA FOR A MEANINGFUL ANSWER
@Xeno Phon Can you explain what an optimal trade distribution and currency system would look like?
@Xeno Phon Do you want a society you actually enjoy living in, or do you just want to be a cog in a societal machine? Besides, no computer can decide what you really need or desire. What about new innovations and changes? Do we even *know* what all the resources in the world actually are? We don't really have enough information to even give as input.
@Xeno Phon ok commie
@@macsnafu Maybe being a cog in something can make one happier than anything else. You are making assumption after assumption, any of them can be mistakes. But we're just supposed to trust them.
Tom Scott and James May are the only two people I know who can make topics that don't particularly interest me sound absolutely fascinating.
That’s the talent of being a good writer and a good presenter
ppp
ppp
I am a computer science engineer and, yes, *I do appreciate your "deliberate semplification".* May all of us be able to explain things like you are. All with that commendable, pervasive sensation of you having actual cognizance of what you are talking about.
Happy recent subscriber of yours.
As an Electrical Engineer my take on deliberate/oversimplification. If you cannot explain a concept without using math or hyper technical jargon then you don't understand the concept.
Basic example, the Fourier Transform, it is defined with integrals and dummy variables and complex numbers and all this junk that takes at about 1.5 years of college to be able to perform.
But what does this painful math actually do, it converts songs from audiofiles to sheet music (assume instrumental only).
Obviously this isn't all its good for or even exactly what it does, but the full answer takes litteral years to build up to. A more accurate description is that is converts functions from time domain to frequency domain, but those aren't universal concepts like instrumental only music and sheet music. (I assume everyone is forced to do atleast a little bit of music theory in elementary school)
2:37 The guy who animated this "computer" deserve respect)
yes indeed
Tom has one of the best editors in his crew)
Looks like it's William Marler
Me: *German*
Tom: *staring at "Entscheidungsproblem"*
Me: where's the problem
Me: oh
haha, same :D
Me too :D
What's the joke😂
Ich dachte mir exakt das selbe 😂
@@amyj4106 that it's a long and complicated word to say for those who don't speak German fluently 😂
I envy this guy ability to make all this awesome content in just one take
I'm glad you mentioned that this problem is _mathematically_ impossible to solve. The two other videos I've watched about the halting problem made it sound like it was only impossible for computers specifically, when really it's a logical paradox, impossible for everybody.
exactly a more human friendly representation of this problem would be "if true then false if false then true"
Human analysis (and in fact, computer analysis if you know how to write it down in a program) can detect some infinite loops, but it’s not possible to solve whether ANY program halts.
I don’t get it. The opposite function loops or halts depending on its argument. If we feed the opposite function to itself without any arguments then isn’t the answer just undefined?
@@Ripred0219The real halts machine has two inputs, one for the program's code and the program's input. You then just add a third machine to the beginning that copies whatever input it receives to it's two outputs.
"and then it vanishes in a puff of logic"
Is that a Hitchhiker's Guide reference I see?
God says "I shall never prove that I exist, for proof denies faith, and without faith I am nothing."
Then, People discover a thing, something which could not have occurred naturally, something which could only be created, but which nobody but God could have created.
People show this thing to God and say "But this thing clearly shows you exist. Therefore, you should not exist, for we have found proof of your existence that would deny the faith which keeps you existing. Q.E.D."
And God says "Ah, crap. I didn't think of that." and vanishes in a puff of logic.
Afterwards, People, feeling full of itself, goes on to prove that white is black and subsequently dies at the next zebra crossing.
As opposed to a toke. Which might be ... I don’t know ... Cheech & Chong maybe ...
I mean his team in that BBC program named themselves Hitchhikers bc of that
@@Blue-Maned_Hawk I kinda have the need to read Hitchhikers Guide now
To be fair, it was already on my list.
@Blue-Maned Hawk The Babel Fish, a fish that feeds on brainwave patterns and excretes a telepathic matrix that allows you to decode any speech you hear if you stick one in your ear... a naturally occurring creature so mind-bogglingly useful that it was widely considered to be the final proof of the Nonexistence of God. (No doubt you knew that, Blue-Maned Hawk; I just thought I’d elucidate a bit!)
Now this is a way of starting off my morning.
This video made me kinda sad tho. But it's Monday so what did I suspect xD
Same
In India its night
@@crystal_royal3405 no
l'll say "What a way to end a Monday"
This video really puts into perspective how much of a massive genius Alan Turing was
I’ve never seen someone who looks so old yet so young at the same time
agreeedd!!
Hahaha
Like a very wise teenager
Maybe he's a paradox! 😳
It seems you do not know the German politician Philipp Amthor :D
2:36 - Was impressed the pre-recorded movements lined up with the post-production graphics .... twice! Also a nice touch that the buttons 'depressed' simulating being pushed.
chrisjlocke It's almost as if the post production graphics editor could see the pre-recorded footage and had the ability to line it up with onscreen Tom! The pinnacle of video editing, I say! :D
It's interesting to see that the English word "computer" comes from 'compute' + -'er' (person or thing doing an action). - In Swedish, we have the word "dator", which is a portmanteau of 'data' and 'motor'; an engine that runs through data. Quite clever.
In German it's Rechner and basically means calculator, or... well, computer.
Although the Anglicism "Computer" is more common nowadays.
In Chinese it literally translates to "electrical brain"
@@unicornspilot That makes sense. Although the irony is human and animal brains are electrical too. Not sure about tiny things like bacteria though.
That construct exists in most language. The concept is called (in English, of course) the 'active agent' form of a verb. The do-er.
Mike Spearwood I guess “semiconductor brain” doesn’t have as much of a ring to it?
Even though you’re “oversimplifying” I still have to pay a lot of attention to keep up. The simplification is making the video very accessible to people who cannot code and who doesn’t know much about computers
"This statement is false!";
"New mission: refuse this mission!";
"Does a set of all sets contain itself?";
Pinocchio comes from school and explodes
NO, the last one is true, the set of all sets, by definition contains itself, the paradox however, is
Does the set of all sets that don't contain themselves contained within itself?
If it is contained in itself, then by definition it isn't contained within itself, etc.
@@tonydai782 I was quoting a video game's reference known as Portal.
It is always cool to know about these paradoxes.
The real question however is, can a computer solve such paradoxes?
If a set of all sets existed then of course it would contain itself. That isnt really where the issue lies.
@@martinshoosterman Yes, in some exotic set theories, there is a set of all sets, and they work just fine.
"Are there problems Computers can't solve?"
Captcha surveys: _"Now this looks like a job for me"_
𝘴𝘰 𝘦𝘷𝘦𝘳𝘺𝘣𝘰𝘥𝘺 𝘫𝘶𝘴𝘵 𝘧𝘰𝘭𝘭𝘰𝘸 𝘮𝘦
Fairly sure these are more efficient at filtering out humans than machines
*NOW SELECT All SQUARES WITH BUSES. FIFTY TIMES.*
@@heynowureallstar This one has 1/8 of a bus showing do i count it?
Yes
What about this one that's the exact same thing?
NO HOW COULD YOU THINK THAT WOULD WORK.
When you need to select all squares with cars, but it's a photo of a truck
@@Daniel_WR_Hart In this case you shouldn't select it. In this kind of captcha the pictures are not the filter. The filter is how long it takes you and how you move the mouse. The pictures are only there to train image recognition AI. You are stating "This truck is not a car." And after some number of people (50-100?-idk) solved the same picture in the same way, it is fed into the AI as training data.
"We take its code." The fact that we can do that is very important. It seems obvious talking about programs but this is the hardest step when you try to do this with other things like Gödel did with proofs over natural numbers.
Wouldn't the code for opposite that is fed into the program opposite, require itself another parameter in order to be run/analysed?
@@jpobi9880 That's where I'm confused as well.
@@jpobi9880 You're right. A slightly less simplified proof uses the hypothetical program HALTS(P, I), which takes a program P and input I as parameters. This program answers True if program P will halt when given input I and False otherwise. Then, you create OPPOSITE(P) which takes a program P as input and runs forever if HALTS(P, P) returns True and halts otherwise. That is, OPPOSITE uses the program HALTS on program P using the same program P as input. Finally, you analyze what happens if you run OPPOSITE(OPPOSITE). This will run forever if HALTS(OPPOSITE, OPPOSITE) answers True. But, wait! HALTS(OPPOSITE, OPPOSITE) answers True only if OPPOSITE(OPPOSITE) halts. So, OPPOSITE(OPPOSITE) will run forever if OPPOSITE(OPPOSITE) halts and vice versa. This contradiction means that the program HALTS(P, I) cannot exist. More accurately, any version of the program HALTS(P, I) that can be written cannot determine the correct answer for all programs, only a subset.
@@jpobi9880 I've thoroughly confused myself: it probably doesn't matter and if we do need to we just pass the simplest code like the assembly `HALT` or the C style `return`
@@HenryLahman It does matter; refer to JohnnyAdroit's explanation above.
I love how much of this show is Tom reassuring computer scientists that this show called "The Basics" is only going over "The Basics"
As a software engineer, I can say that your simplification is reasonably adequate :-).
BTW, Kurt Goedel basically arrived at a similar conclusion with its two incompleteness theorems. A brilliant work.
Gödel's Incompleteness Theorem also follows this self-referential principle to arrive at paradoxes, but the consequences are even deeper. The fact that it implies that any set of mathematical axioms either produce truths that cannot be proven by those axioms alone, or that they outright contradict themselves, is amazing. Just imagine how many problems we have right now that are worth a million dollar prize, some of them might literally be true, yet have no formal mathematical proof. It makes my head spin.
The big problem that I know of that could be this way is the Riemann Hypothesis. However, if we could prove that the Riemann Hypothesis is unsolvable from the axioms of math, then that means that it is true because if it were false we would have a way of proving it false from the axioms.
And the thing is, the paradox is a deceptively simple "This sentence is a lie." formulation. It almost seems silly that this could tie logic up in knots, but there you have it. The fundamental flaw in formal logic.
@@efulmer8675 That doesn't mean it's true, it means it can be both.
@@TheBraude Numberphile has a video on Godel's Incompleteness Theorem and they mention implication that the implication that the Riemann Hypothesis is true if it cannot be proved true from the axioms.
It's not a Tom Scott video without a pinned comment at least 4 hours ago.
yes
And the red shirt
And the moving gestures?
I'm new to the Tom Scott page... Is the 4hr pinned comment a regular thing?
@@B-RaDD It can range from hours to weeks at times.
It's like the "everything I say is false" paradox but for computers
"Ummm... 'true'. I'll go 'true'. Eh, that was easy. I'll be honest, I might've heard that one before, though."
@@imveryangryitsnotbutter "For God's sake, you're boxes! With legs!"
I don't think this is a paradox since this statement could be false without contradicting the negation of "everything you say is false" which is "it exists something you say that's true". If the statement is false, maybe another statement you said could be true, who knows.
A real paradox should be more specific to the statement like "This sentence is wrong."
For what it's worth, the answer to that paradox is that they're lying to you. Not /everything/ they say is false, just one statement.
It should also be noted that most paradoxes are less logical contradictions and more "failures of sentences to form a concept" or failing to take into account a 'third option'.
To use an example of the latter: What happens when an unstoppable force meets an immovable object? They pass through eachother. The force does not stop, the object does not move.
To use an example of the former: "Can God draw a square circle?" No, because the term 'square circle' doesn't actually mean anything. Similarly, God could not create a tornado over water, because then it'd be a water spout.
As someone who has TAed an intro Theory of Computation course several times, this was a really good layman's explanation.
Of course one funny thing I like to point out is that for any computer that we can ever possibly hope to build, the halting problem is actually solvable. This is just because unlike a Turing Machine, computers we can actually build don't have infinite memory. They're not Turing Machines, they're finite automata. This means I can look at the "state" of a particular computer executing any program (the contents of its registers, memory, disk, etc) and wait until either the the program halts, or I see the same state appear twice (in which case I know the program will loop)
In practice however, this is obviously infeasible. Just considering 8GB RAM for the moment, that's 2^(36) bits so 2^(2^(36)) possible states.
Also, interestingly, some low-level languages like C aren't in fact Turing-complete because the C standard defines a finite constant for the width of a pointer in bytes and the number of bits in a byte, which implies that the amount of addressable memory, and hence the number of possible states the program can be in, is finite. This doesn't actually rely on the hardware limitations i mentioned before. Or rather it demonstrates that those limitations are built into the C abstract machine.
Another funny consequence of this is that all C programs that halt run in O(1) time. Since they halt, their runtime is bounded by O(2^(2^(CHAR_BIT * sizeof (void*)))) which is a constant (albeit typically a very, very, large one)
interesting take on the subject
I mean, if talking real world, it would eventually halt given the heat death of the universe (or a power cut) but this doesn't solve the logic question
Nice video with a good treatment of the problem. There's always one thing I wish presenters would bring up, and Tom flirted with it.
One of the key assumptions in the halting problem is that we're working with an idealized Turing machine, which is related to Hilbert's problem. In the real world no computer is truly a Turing machine because it has finite memory. You can definitely answer the halting problem for a machine with finite memory; you just need a larger machine that is able to simulate the smaller machine. For any given state, the big machine simulates the small machine until the small machine goes back to a state it has already been in (loops forever) or gets to the halt state (halts).
I think perhaps my favorite thing is that everything loops back around to a core truth, no matter who's asking or how-
The answer to "Is _x_ limitless?" is always "No, and you pure theory types need to stop asking." Physicists and chemists, mathematicians and engineers, the question never changes and neither does the answer XD
Yet, the paradox does not rely on the machine being infinite.
Regardless of how the machine looks like: if it detects a halt, it runs forever, if it detects a run forever, it halts. Feed it to itself and you have the paradox.
Does a program like
while (user input != "Ctrl+C"){}
terminate?
Even with just one byte of memory, this is undecidable. Because we do not know if there is a user and if they will somewhen press Ctrl+C.
The infinite band of the Turing machine does not EQUAL the internal memory, that's just more of an analogy. Rather it may also contain other information like inputs and time passing depending on how you transform a real-world system into a Turing machine.
Interesting is that the problem is not symmetrically undecidable. It is rather easy to prove if there exists a path in a program / model / machine that is terminating. But we cannot prove, that ALL paths will EVENTUALLY terminate. We cannot even determine, whether a "loop" is executed infinitely often or just once or several times before branching to a terminating path.
Oh, another nice code example:
do {
x = randomize();
} while (x != 5)
Statistically, this might be likely to terminate. But we cannot be sure, if we have an unlucky run and never hit 5. Moreover the "big machine simulating the small machine" might see the state "x = 4" several times, decide, that there is a loop and decides the program does not terminate but in the next iteration, x is 5 and the program does terminate. Big machine failed.
@@Aderendhuelse Well when you're talking about impure programs where you're waiting for input from the user, essentially the answer is almost always that it won't necessarily halt, because the user could just never press anything and the program would go forever. The question of whether the program will halt is essentially a "is it possible for this program to not finish and go indefinitely?" Once you introduce any kind of awaited user input, that almost always becomes the case.
As for random numbers, if the randomize function is truly random and capable of producing a 5 result then the program will eventually end. You don't know when it will end (assuming the RNG is totally random), but eventually it will. There's no such thing as an unlucky run, because there's no set time limit where we give up and call the program frozen. Given infinite time, it will eventually end.
@@taragnor You could easily modify the function:
x = randomize()
if x == 5{
loop
} else {
halt
}
If the number is truly random there is no way to know if this function will halt or not. Of course there is the issue of whether or not truly random numbers even exist, but the main contradiction is in the halting problem.
Do you have an opinion on pheasant pluckers?
If I remember correctly, it would only pring "SOMETHING RUDE" horizontally like that if you included a semicolon on the print line, otherwise it would just print one per line.
Spot on. Was that you I saw in Dixons?
Came here to make this comment 😄
Yep, you’re right. 😎
Or if you had a trailing comma it would insert a tab afterwards.
the better troll is to load up a legitimate pong game or whatever that only every few minutes prints a few pages of obsenities then goes back to the game after clearing the screen.
They really paid Turing back for his help.
Oof. Happy pride month :/
The minds we lost to discrimination of any kind.... sad world.
No good deed goes unpunished.
@@TestarossaF110 And a lot of it founded in some religious doctrine of one form or another.
@@TheKazragore oh no not religion!
Imagine blindly accepting a proposition, that certainly doesn't apply to anyone here.
This feels like Russell's "Set of all sets that don't contain themselves", but on a computer.
Yes, exactly. Russell's or Cantor's "diagonal argument" was very likely the inspiration for this proof.
Weirdly enough, though this was only tangentially related, it helped me better understand how Magic the Gathering can be used as a Turing Machine.
Do enlighten me
Because Science already has a video doing exactly that
Same with microsoft power point, same with HTML5+CSS3. The important thing to know is that a Turing machine can compute *anything* given enough time. Turing machines (aka computers) are actually quite powerful
Chris Wyllie Did you watch the video?
@@birdrocket Correction: A turing machine can compute anything that is computable
This just reminds me of GLaDOS's failed effort to disable Wheatley by telling him "This sentence is false."
Um… true, I’ll go true. Huh, that was easy.
Don't think about it.
same, i was thinking that too lmao
"vanishes in a puff of logic"
Nice reference.
What's the reference to?
@@Jont828 Hitchhiker's Guide to the Galaxy
6:07 can someone explain this better to me? If it thinks it will halt, it will loop. But that just means it will loop given this specific input. Of course, if we take all of this again and take it as another input, fair enough it will halt, but I don't see where the self-contradiction comes from, since we never stated that we refeed its output infinitely
Clearly this went right over your head...
@@cerealkilla378 What an explanation!!!
The program goes in infinite loop of halts and loops within itself. That's the contradiction.
It's like in time machine paradox: after developing time machine and killing yourself in the past using it - what will happen? If you die - you can't create a time machine. Then you wouldn't travel in the past and won't kill yourself. But that means that you will be alive. Which mean that you will make time machine in the future and will kill yourself. But that means that you are dead and can't make time machine, go back in time and kill yourself. But that means that you are alive... And so on.
The Opposite starts a loop similar to this: if the "inserted" Opposite is running - then the "main" Opposite will stop. But since the inserted program have ability to stop, the main Opposite must run forever.
It's somewhat resembles the superposition: because the inserted program can do both infinite looping and halting, the main Opposite must looping and halting simultaneously too. Which will break it, until someone deliberately breaks this loop by makig some changes to how both programs should work.
@@Yash-ML-Sharma I have my moments.
One way to think about this is to observe that in order to have a machine that can answer a query, the query must be finite: for example, a program that finds the largest number does not exist, because it would need to be "x = 1 + (1 + (1 + ...))". If a question is impossible, so is the answer.
To get OPPOSITE to halt, you ask it "do the opposite of (a program that prints something rude forever)", and to get it to loop forever, you ask it "do the opposite of (a program that prints hello and exits)". But when you feed in its own source code, you are asking it: "do the opposite of (a program that does the opposite of (a program that does the opposite of (...)))", and this query expands infinitely. A machine that answers an infinite query cannot exist, therefore OPPOSITE cannot exist.
QUESTION: Can computers solve the question of where David Hilbert got that sweet hat style?
Solve? no.
Discover? Yes ( ͡° ͜ʖ ͡°)
Do you mean brian david Gilbert?
@@Otzkar BDG is actually the oldest immortal. That's why hes Like That.
@@Otzkar Do you mean Hugh Brandity?
"This sentence is false!"
"Umm... true. I'll go true."
Is the answer to this question no?
Its an paradox. THERE IS NO ANSWER!
too stupid to realise that it's a paradox, or, in other words...
blissfully ignorant
@@vendybirdsvadl7472 This place is gonna blow up if I don't get back in my body!
@@moved8575 In classical bi-state logic it does not have a value, you could say that it isn't actually a proposition which can have a truth value attached to it (again, in bi-state logic)
“Are there problems computers can’t solve?” The Balkans.
хехе
press 'Launch'
Europe's most dysfunctional family
Just bring a bottle of rakija with you and all the problems are solved
oh wow that's...yea. I feel like an idiot now 🤔
One of the best openings I have seen in entire UA-cam that summarize the rest of the content.
1:55 It's pronounced 'Entscheidungsproblem'
aw gee thanks for the help
End-shy-dunk-s-problem
Thanks I was stuck on that
Thanks
@@okaydayy Kind of, but more like End-shy-dungs-propleem. You can't really find a word for the "dungs" part which sounds correct
I'm German, so when there was "Entscheidungsproblem" appearing and Tom paused I was like, huh? What's the issue?
And then I noticed that it's not English 😂
Jep
Same. And then I remember that such long words must look really intimidating to pronounce for someone who doesn't speak German. I'd have loved to see him try tho
@@luka_8 Break it down, it's actually a very simple word to say. Most long German words are
@@calum5975 for us germans yes, but I've seen *so* many people have problems with the harder pronunciation of longer German words
@@luka_8 Tschechisches Streichholzschächtelchen.
just put it in a try catch bruh
exactly
+1
the thing is what should it return after a catch: doesn't halt or halt?
@@moved8575 the catch means HALTS might halt therefore I could theoretically exist in this case.
@@PastyMancer oh
I can simplify the answer even more. Any problem can be solved as long as you can put it into a form the computer can parse.
On the topic of the example paradox, if the program is capable of causing a paradox, then it _MUST_ loop. If the code does not loop, it cannot recur to create the paradox. That's actually built into the code itself; the code loops as long as it would stop, but it also just stops if it should ever loop, once the code stops, it is no longer running to cause the paradox but it had to loop at least once to reach that point.
It's like the +1-1 ad infinium "paradox," the answer could be 1 or 0 depending on whether infinity is odd or even, but 0.5 is also an answer.
"Is the answer to this question no?"
Computers: "uuuhhh"
Computer: "Yesn't."
"It is not."
You: "Is the answer to this question no?"
Computer: "Nah m8, of course it isn't"
This sentence is... False
Bertrand Russell’s answer was “bottom”.
No, that wasn’t a more polite way of saying “bum”, it was the name of the “⊥” symbol for the (non)result of a nonterminating computation.
This is what we might call "The Strong Halting Problem":
Question: Can one algorithm determine whether another will halt?
Answer: No, because if it could, it still couldn't when applied to itself with a "negation" module appended.
So, how about a "Weak Halting Problem"?
Question: Can an algoithm determine the halting of another, provided the analyzed algorithm does not contain the analyzing algorithm?
Recall Russell's paradox of the "set of all non-self-containing sets", and his proposed solution of a hierarchy of self-containment.
Still, the concept of "not containing the analyzing algorithm" isn't really well defined. Even if it doesn't literally contain it, it could contain something isomorphic to it.
The big example here is how Russell and Whitehead made a system that talked about numbers but not about itself, and then Gödel showed that it could manipulate those numbers in a way that made it talk about itself, leading to the usual self referencing paradoxes.
The whole point of Turing's contradiction proof was NOT a counterexample that showed that "ok since I found one case where it doesnt work then it can never work for ALL cases"
The proof was more like "assume it's possible, that assumption leads to literal nonsense, hence the whole notion of a "halting machine" is literal nonsense and is not even a coherent idea (even if the incoherence of the idea is non trivial to see)"
I dont see how relaxing the conditions of such a machine would fix this, I feel like the proof strongly suggests (even if it does not prove, I'm not wise in the ways of decidability enough to know haha) that the machine is simply impossible as a logical concept
Again that's complete non-rigorous bs that comes more from gut feeling rather than proof
This wouldn't work. You would need to specify what does it mean for an algorith to contain another. If I make a little tweak that changes the literal program but all the outputs remin the same, is it the same algorithm? This will probably lead to a definition of equivalent algorithms: Two algorithms are equivalent if and only if they output the same thing when they receive the same input. Okay, that one is solved. But now you need to verify that there is a program that can check if two algorithms are equivalent. This program can't exist, as it would have to go iver every posible input and wouldn't halt. Maybe you can think in other ways of solvibg the "contains the analyzing algorithm" but the problem will remain, verifying wether two algorithms behave the same is not computable.
There is a different way of proving the halting problem that doesn't rely on passing the machine as an input to itself. You can define a function that no turing machine can do (essentially, number all turing machines and all inputs, and then when given an input, output the opposite of what the turing machine with the same number would output on that word), and then you can demonstrate that, given a turing machine which solves the halting problem, you can make a turing machine which accepts the function that we just found to be impossible.
@@jarredallen3228 Is the set of all turing machines countable?
My computer can’t solve why it sounds like jet engine when I open 2 tabs.
How is it starting the calculation? Is it custom software or?
It's just having an identity crisis. It think's its a jet not a computer. Put little wings on it, might make it happy.
Use the new Microsoft edge it really helped me had the same problem
Never looked back
clogged fans
Could it be one of those pages has a cryptominer hidden in it?
I have worked on Computers my whole life and I never knew this, thank you.
One problem a computer can't solve: Fixing "Paper Jam" in a printer.
SkeletonSyskey 😂 True!
Also:
Printer: Replace yellow ink.
Me: But I'm only printing using black, no colors.
Printer: Replace yellow ink.
@@Monkeyb00y For me it's "Magenta In Da Printer"
@@SkeletonSyskey many printers actually use colored ink, when you print black and white, to make it run out faster, so that you have to replace it.
Never let a printer know you are in a hurry... they can smell fear.
When I was studying Turing I tried to understand this but oh my god I didn't find any source in the entire internet that explained it well and I never understood it
Thank you so much
I understood what he's saying, but the concept still doesn't make sense, the program before it is entered into itself isn't complete, it's missing a data point. A program is a process, it doesn't have a result until you give it a reference point to start processing. I think the nuance might make it more convincing though
@@PropheticShadeZ Well that's because it's oversimplified.
"then it vanishes in a puff of logic" Hitchhiker's Guide reference?
Tom was a leader of a team Hitchhikers on Only Connect.
haven't -heard- read that part yet
ah, i hate when my belongings disappear in a puff of logic
"Oh dear," says God, "I hadn't thought of that," and promptly vanishes in a puff of logic.
That sounds like something Terry Pratchett would write
I love The Hitchhiker's Guide to the Galaxy
@@ankitaishwarya5586 it's actually from Douglas Adams' The Hitchhiker's Guide to the Galaxy
ahaha! I get that reference!
@@ankitaishwarya5586 Also dry, brtish and satirical like Douglas Adams, just on the fantasy side of things :P
Who needs to ask “Can it solve every problem” when instead we can ask “Can it run DOOM”
What we should ask is that given infinite time and memory, could a Turing machine run Crysis.
Found the computer engineer
@@synchronos1 Could it run Yandere Simulator
@@smort123 Minecraft with shaders*
virgin Computer Philosopher vs Chad DOOM porter
"Not enough data for a meaningful answer"
"LET THERE BE LIGHT"
maps with Greenland on them be like
*There is as yet insufficient data for a meaningful answer
Objects in Motion You would have to forgive me, I’ve read it in Bulgarian and this was my translation based on the original English - Bulgarian translation.
This has been the clearest statement of the P NP and the halting problem I’ve seen. Thank you.
You mean R and RE
Everybody gangsta until Tom stares at the Entscheidungsproblem
Tom Scott was that kid typin something rude on the computer
Just a clarification: it’s not just that there’s no computer that can solve these problems, it’s that no algorithm exists that can solve these problems which means that there’s nothing at all that can solve them (as in no human can solve them either).
Exactly.
A neat counterexample: Write a simple while loop of searching for zeros of the Riemann zeta function where the break condition is finding a zero which is not on the critical line, thus disproving the Riemann hypothesis. If the program halts we know that Riemann was wrong, and even if it takes billions of years that would still be a mathematical precise result. But if we could simply "tell" or use a "halting machine" to determin wether it will ever halt... then this would classify as proof of teh Riemann hypothesis. You could re-phrase this procedure for basicly every math problem. Computers can find counter examples, but they can (almost) never proof an infinite logical pattern. The only exceptions i know of where computers actually prooved the thing without any human understanding what they did in fulld etail is the proof of the four-colour-map-theorem and Hales proof of the Kepler-conjecture. Both showed results, but you gain no insight on the topic by knowing something is true. You gain insight by understanding why something is true; an insight a computer may never be able to give.
A problem that Tom Scott can't solve: How to produce a Tom Scott video that's not interesting.
Now that would be a paradox!
You're not seen his Million VS Billion thing
@@lazaraleksandrov2808 Not interesting, but quite relaxing
2:35 that's amazing edit!
everybody gangsta till that that computer gives one hour long lecture when you feed it its own code
2:12 Hilbert’s optimism is engraved in his gravestone: it says “We must know, we will know” in German
So basically, such a machine is impossible because its existence will contradict itself
yes, that's the video
But since it can not exist it also can not contradict itself! Therefore it can exist....
@@S3Mi87 yep, that's the paradox
Only if you feed it an infinite recursive stack as input.
@@VecheslavNovikov I suppose you're right. The machine gets another machine as input. But that input is the same machine getting the same input itself. That's an infinite self-referential loop of machines which basically tries to compute the answer to the question "Is the answer 'No'?". That's a paradox question with no correct answer so of course computers cannot find an answer. But apparently it's a big achievement to proof mathematically that you cannot tell the answer if there is none.
Poor Turing,never got the right treatment during his life even though he's a genius.
British Parliament did give him an official posthumous apology... Although it's... Several decades too late. Hmph...
@@Teck_1015 its better than nothing, its not like the parliment which issued the apology was alive to stop his abuse
Turing could have cured cancer and brought world peace and the authorities still probably would’ve castrated him.
Drew P. Weiner and, well that's the sad thing. Without him so many things would have not been possible, or at least been postponed until someone else invented the same thing. And we probably would have lost the war. The whole enigma code etc.
@@bearmugs1408 I did a school project about him and the enigma code. I'm surprised about how little there is about him (at least with my search engine)
Right answer: the last digit of π
edit: only now, after 3 years, do i realise that i made an accidental Homestuck reference
The last digit of pi is definitely "yes"
We all know that the last digit of π has to be 2...
@@irgendwieanders2121 I don't get it
@@irgendwieanders2121 no. It’s 9 for sure.
@@user-dh8oi2mk4f Too young to get it? Or not nerd enough?
The editor of this video should get a raise. By that, I'm sure it's Tom himself. Give yourself a raise Tom.
2:45 imagine having a job as a computer and thinking you're set for atleast another 50 years, and then getting a letter in the post saying you're getting replaced by electronic computers.
And then realise that your entire career has led to the development of the machine that replaced you.
So basically, imagine your are half the modern workforce in 10 years time?
Me before this: yes
Me now: yes, and I also need a therapist because I am more confused than ever.
It is basically the "This sentence is a lie" paradox, just as a computer version.
*MY BRAIN HUUUUUUUUURTS!*
Same
Alan Turing is always the answer to any who computer science question
Except when it's John von Neumann
And George Marsaglia when it comes to psuedorandom number generators.
And my dong
Or Claude Shannon
This video should be played in every lecture of Theory of Computation
i watched this whole video, not knowing anything about computer science, just waiting for that hitchhikers guide to the galaxy reference
42
42
Next time you're waiting for such a reference, it might be wise for you to bring a towel.
As soon as i read the title i thought of Hilbert, Gödel and the incompleteness theorem. Thank you for making me feel somewhat smart 😆😂
>"Herbert's Decision Problem"
Poor David Hilbert :(
Hilbert, Turing and Gödel lived great lives and impacted much of maths. I recently read a book called The music of the Primes by Marcus de Sautoy with chapters on them. Definitely worth a read.
When is "The Advanced" going to ve released?
It's called a degree
omg, I was using a GPU heavy program on my other screen and actually thought I had overloaded my GPU when the video started to buffer xD
Drinking game: Take a shot everytime Tom says he's oversimplifying something
Are you the devil?
Are you crazy? You want us to get alcohol poisoning? (JK)
Coming back to this after Vertasiums latest video talking about decidable and undecidable math, this video prepared me for that!
Same!