Are There Problems That Computers Can't Solve?
Вставка
- Опубліковано 10 тра 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
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
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
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.
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
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.
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.
+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
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 UA-cam
lmao
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
"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.
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
God, what a focus. Explaining this kind of subject perfectly for 8 minutes straight isn't for everyone
"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...
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
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
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.
ah, i hate when my belongings disappear in a puff of logic
I envy this guy ability to make all this awesome content in just one take
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.
Tom: "The, uh. The... Uh. The. Decision Problem"
Me: (laughs in german)
same
Same lul
Laughs in Dutch
*laughs in bilingual*
germans laugh?
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
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.
"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 ;)
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 😂
"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?_
Humans: Computers can't solve paradoxes
Computers: Well humans can't too.
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
"Vanishes in a puff of logic"
The bablefish really was far too convienient
The editor of this video should get a raise. By that, I'm sure it's Tom himself. Give yourself a raise Tom.
the editing on these videos always amazes me
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
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 UA-cam that summarize the rest of the content.
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.
"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!
you know tom is working hard when the pinned comment was 4 hours ago instead of 2 weeks to a month
I asked Chat GTP wether it could solve the halting problem and it made the decision to tell me: "no".
The steps for troubleshooting a specific computer issue typically involve the following:
1. Identify the specific problem - Determine exactly what the issue is that you are experiencing.
2. Break down large problems into smaller ones to make them more manageable.
3. Consider the scope of the problem and who or what is affected.
4. Ask the right questions to quickly discover the root problem.
5. Document the troubleshooting process, including both successful and unsuccessful fixes, for future reference.
These steps are part of a structured troubleshooting approach that can help you effectively address and resolve computer problems.
"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.
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.
I love the energy you gave to the disclaimer for the computer scientists
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.
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
"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)
This has been the clearest statement of the P NP and the halting problem I’ve seen. Thank you.
You mean R and RE
1980s: *Purposefully makes a computer loop a message*
"Did it!"
2022: *Forgets to set while loop to false*
"Why can I never get this working?"
"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!)
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
2:12 Hilbert’s optimism is engraved in his gravestone: it says “We must know, we will know” in German
"vanishes in a puff of logic" is a phrase I will start using in my own proofs by contradiction
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?
"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.
I'm gonna write this into a riddle for DnD.
This might be the nerdiest idea I've ever had.
The editing is top notch in every video.
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.
“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 🤔
I have worked on Computers my whole life and I never knew this, thank you.
thank you for saving me a day before my presentation on undecidable problems!
"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
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?
Immediately upon hearing the Decision Problem I thought of the classic "The sentence is false." It causes the same paradoxical looping.
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'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?
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.
“Vanishes in a puff of logic.” Hitchhiker reference. 😊
i just got an ad about learnng to solve problems before this video
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.
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.
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
This video should be played in every lecture of Theory of Computation
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?
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)
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.
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.
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
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.
This went completely above my head
"Any program that you write in any programming language can be converted into something you can run on a Turing machine."
*aggressive motors moving in tune to the doom theme intensifies*
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
"vanishes in a puff of logic"
Nice reference.
What's the reference to?
@@Jont828 Hitchhiker's Guide to the Galaxy
i love how tom just does away with entscheidungproblem
Coming back to this after Vertasiums latest video talking about decidable and undecidable math, this video prepared me for that!
Same!
"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.
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
@@WhiteThunder121 Minecraft with shaders*
virgin Computer Philosopher vs Chad DOOM porter
"where did my happiness go?"
dawg I got permanently blacklisted from youtube for using an adblocker but I bet this video is absolute fire. Liked
"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
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.
Anything divided by zero is a good example in my professional opinion
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.
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
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.
Would be fun to hear Tom's full lecture series on it
Now we know why it came up with something ridiculous like "42".