Are There Problems That Computers Can't Solve?
Vložit
- čas přidán 10. 05. 2020
- 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.com/newsletter/
❓ 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
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
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
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.
@@Beateau link?
@@Beateau link?
@@Beateau Link?
"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.
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.
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
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"
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
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.
"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
"Some nerd sneaks into the shop and sets it into a loop"
Hey, that's me!
oh so you did it
@@netkv ¬_¬ maybe. And hi btw, imagine bumping into you in the expanse of CZcams
lmao
+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
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
God, what a focus. Explaining this kind of subject perfectly for 8 minutes straight isn't for everyone
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
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 video really puts into perspective how much of a massive genius Alan Turing was
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.
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
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
"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...
Tom: "The, uh. The... Uh. The. Decision Problem"
Me: (laughs in german)
same
Same lul
Laughs in Dutch
*laughs in bilingual*
germans laugh?
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.
ah, i hate when my belongings disappear in a puff of logic
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.
"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 ;)
"Any program in any programming language can be converted into something that can run on a turing machine"
Cyberpunk 77: _Oh, you're approaching me?_
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.
"Vanishes in a puff of logic"
The bablefish really was far too convienient
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
One of the best openings I have seen in entire CZcams that summarize the rest of the content.
the editing on these videos always amazes me
"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!
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 CZcams. What a moment.
You are the lucky pigeonhole in the pigeonhole problems
This compliments the concept of the "opposite" machine bizarrely well
This has been the clearest statement of the P NP and the halting problem I’ve seen. Thank you.
You mean R and RE
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.
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
you know tom is working hard when the pinned comment was 4 hours ago instead of 2 weeks to a month
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.
I have worked on Computers my whole life and I never knew this, thank you.
"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.
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
I love the energy you gave to the disclaimer for the computer scientists
The editing is top notch in every video.
"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!)
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.
thank you for saving me a day before my presentation on undecidable problems!
Humans: Computers can't solve paradoxes
Computers: Well humans can't too.
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
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?
1:28 so Turing's halting problem. Got it. Don't need to watch the rest of the video but I will anyway because I like your explanations 😃
The editor of this video should get a raise. By that, I'm sure it's Tom himself. Give yourself a raise Tom.
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?
"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.*
@@joeyjojo91 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.
Coming back to this after Vertasiums latest video talking about decidable and undecidable math, this video prepared me for that!
Same!
I'm gonna write this into a riddle for DnD.
This might be the nerdiest idea I've ever had.
"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)
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.
great explanation of theory of computation
my simple ass brain:
"its opposite day"
"that means its not opposite day"
"but by not being opposite day the statement 'its opposite day' is in fact true and it is opposite day."
"but that means that its not opposite day"
boom, 6:32 theres your paradox
1:55 It's pronounced 'Entscheidungsproblem'
aw gee thanks for the help
End-shy-dunk-s-problem
Thanks I was stuck on that
Thanks
Haha very funny jokez
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.
2:12 Hilbert’s optimism is engraved in his gravestone: it says “We must know, we will know” in German
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.
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'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.
wow the animations are amazing
Thank you again Mr.Turing.
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.
"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
Would be fun to hear Tom's full lecture series on it
I'd hope that computer scientists would know that you're giving a simple explanation to people that you'd likely confuse or lose going really into depth on coding and internal workings of a computer, This form makes it so much more accessible to people like myself who have an interest or curiosity.
“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 🤔
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?
“Vanishes in a puff of logic.” Hitchhiker reference. 😊
i dont understand most of the things you are saying, but i still enjoy those videos so much i cant stop watching
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.
"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.
I've been thinking about the problem a lot and I find a great way to simplify it is this:
Computers are logic machines and can only take in logic and give out logic.
A paradoxical problem is by definition not adherent to logic and therefor can not be computed, because for a problem to be computable it needs a logical answer.
The issue with the halting problem is therefor not that computers simply can't solve it, it is that it has no logical solution
i just got an ad about learnng to solve problems before this video
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
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 went completely above my head
Great editing btw.
"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 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)
This video should be played in every lecture of Theory of Computation
So the halt not halt machine is literally a "this statement is false generator".
"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
"vanishes in a puff of logic"
Nice reference.
What's the reference to?
@@Jont828 Hitchhiker's Guide to the Galaxy
"vanishes in a puff of logic" is a phrase I will start using in my own proofs by contradiction
I'm just curious to know what "vanishing into a puff of logic" would look like. I would love to see someone create a basic version of this paradox (if that is even possible) and see what the compiler does. Will it throw an exception? Will it just not run at all? I am curious.
it's will result to a runtime error (stack overflow)
@@zeroanims4113 would that be equivalent to throwing an exception in C++? I'm not as good with programming languages as I used to be 😅
@@BigBoiiLeem yes for some platform like windows it throws an exception albeit an asynchronous one
@@BigBoiiLeem Yes, specifically the infinitely recursive recalculating of "halts, will not, halts, will not, halts, will not, ..." would overflow the stack and throw an exception
Many coding languages throw an exception if a code runs for too many repetitions, assuming it's an infinite loop. If a language doesn't have that it'll just go on forever until you kill it. But that repetitions check is just arbitrary, it's possible to write a code which will do something 90 quadrillion over and over then do something different.
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.
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?
If you use the output of the "opposite" machine as input, you'd then have to give that machine it's own input or the input is incomplete. Given a set of input doesn't start with incomplete input, you can tell whether or not it will halt. What am I missing?
same question here
That's one hell of a existential crisis for any intellectual being to deal with, as my thought. Remember, humans are also a kind of "computers", so, in other words, there will be some statements/problems that are inherently true/false but unprovable by any thing or any system of logical reasoning. As a child, i would dream about being able to know and solve everything, then later in life, after knowing the physical probabilistic limit stopping us humanity to actually "know everything for certain", i gave up on the dream of knowing everything in hoping for humanity to actually "solve everything", every hypothetical and practical questions, using the very own formal logical system we created. Then we prove it ourselves that we can't do so, ironically, the problem in which whether or not we can prove every problem, lies in the "provable" domain. No matter what axioms we will add or cross out, we can't prove everything using intelligent logical processes. As a species of intelligence, we come into realization that we can't be omniscient nor we can be omni-intelligent (made up word). That is devastating, at least for me.