Are There Problems That Computers Can't Solve?

Birt 11 maí 2020
Áhorf 1 120 813
96

All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: is-stores.info/lstPL96C35uN7xGLLeET0dOWaKHkAlPsrkcha.html
Written with Sean Elliott SeanMElliott/
Graphics by William Marler wmad.co.uk
Audio mix by Graham Haerther haerther.net/
I'm at tomscott.com
on Twitter at tomscott
on Facebook at tomscott
and on Instagram as tomscottgo

Tom Scott
Tom Scott
Ummæli  
  • Tom Scott

    Tom Scott

    21 degi síðan síðan

    Both my co-author Sean and I are worried that we're oversimplifying here -- but then, this series is called The Basics!

    • Acecool

      Acecool

      4 dögum síðan

      If you can't over simplify, you don't know the material. I'd be happy to discuss this at length; this isn't something I had in my computer science education and I believe there is a way for anything.. I mean.. our human brains are computers and we can look at something and determine if it will look forever or not. We are limited in knowledge based on our life-time, motivation, etc.. but if we had perfect memory and infinite time then we could build a repo of knowledge which could answer the question as both yes and no to any program. Or we could give defininite yes or no answers... But with infinite time comes infinite evolution. so it really depends how in depth the problem is... I'll have to look it up to see the exact terminology as I haven't seen this example given before. But, based on the question posted in this video... I do believe it is possible.

    • NocturneInNeon

      NocturneInNeon

      13 dögum síðan

      If you didn't want to simplify the Halting Problem into a video that was less than 8 minutes long, you shouldn't have made a video about the Halting Problem that was less than 8 minutes long. All joking aside, amazing video.

    • Nicholas Hughes

      Nicholas Hughes

      14 dögum síðan

      It's good that it was simplified that much, for young viewers like me it's great to help us understand all of your videos on more complex subjects!

    • Thor Thorbjornsen

      Thor Thorbjornsen

      15 dögum síðan

      Incredible video! You own what you do. And that is far better than worrying and never offering better.

    • jm 101

      jm 101

      15 dögum síðan

      what if you make the code run the code in quietion in the background and then if it loops it will for certain loop

  • Ariel Shokrany

    Ariel Shokrany

    2 klukkustundum síðan

    everybody gangsta till your computer returns from work.

  • Facehunter2003

    Facehunter2003

    2 klukkustundum síðan

    0:42 I used to do that on the school calculators lel. Now I've graduated to making mini games on the school calculators.

  • Darth Musturd

    Darth Musturd

    4 klukkustundum síðan

    Basically
    If + then -
    If - then +

  • Viktor Vano

    Viktor Vano

    5 klukkustundum síðan

    That opposite machine sounds like a 'NOT' logic where the output of the 'NOT' transfer function feeds its output to its input. So 0 is 1 is 0 is 1 is 0... But it cannot be, because input should be equal to output because it feeds to itself, but the transfer function (logical NOT) says the opposite. 'NOT' logic inverts the value to the opposite value, but it should be equal, because output is connected to its input.... that's a paradox too.

  • CraftBasti

    CraftBasti

    8 klukkustundum síðan

    Tom: "... one of them came to be known as the....." My german brain: "Entscheidungsproblem. Makes sense for a name." Tom: ".... Decision Problem." Me: Oh right, didn't notice that

  • Dan

    Dan

    8 klukkustundum síðan

    1:52
    That word is pronounced "Entscheidungsproblem"
    You're welcome.

  • Wacking Cactus

    Wacking Cactus

    12 klukkustundum síðan

    Microprocessors are very interesting

  • E3kHatena

    E3kHatena

    Degi Síðan síðan

    But can computers show me why kids like the taste of Cinnamon Toast Crunch?

  • Lancer

    Lancer

    Degi Síðan síðan

    Are the solutions to which the problem has yet to be invented?

  • Alespic

    Alespic

    Degi Síðan síðan

    Determine this computer:
    I am lying
    Bet you can’t determine that you dumb metal box

  • ᴅʀᴇᴀᴍ

    ᴅʀᴇᴀᴍ

    2 dögum síðan

    Can a computer tell us what a computer cant solve

  • Mister A/M

    Mister A/M

    2 dögum síðan

    I know that this video is just a simplification but I have a question. How could a code(x) determine whether a code(y) will loop or not if the code(y) needs an input that will determine whether it will loop or not? I mean if code(x) would get code(y) as an input with the input for code(y), code(x) could give you the answer but if not it would be impossible not because the computer is not able to, but because it has insufficient information. The only problem is if the code(x) get as input code(x) which has as the input code(x) and so on, then it would only be possible to figure out a tendency, for example like if you would have a formula like y=x+1 and you would infinitely put x+1 as x. Then you would have something like y tend to infinity or something like that. But you would still get a result, even if it would be something like 1/2 or 0.5 or 0 or 1 or ∞ or -∞ (0 means the code will not loops and 1 means the code will loop).
    PS: sorry if the English was bad

    • sqrooty

      sqrooty

      6 klukkustundum síðan

      Halt(program, input) determines whether program halts on input. Opposite(program) then calls Halt(program, program). So Opposite(code of Opposite) calls Halt(code of Opposite, code of Opposite), which checks whether Opposite(code of Opposite) halts.

  • Bia Zarr

    Bia Zarr

    2 dögum síðan

    So. How do quantum computers play into this? Do superstates make a difference here?

  • Ervi Ari

    Ervi Ari

    2 dögum síðan

    Let Turing of the past try reproducing the same paradox with qubits and we'll see what happens. There is more to this world than binary. Todays ones and zeroes are limited to how much they can help solve today's medical ailments like cancers or viruses.

    • sqrooty

      sqrooty

      6 klukkustundum síðan

      Quantum computers are turing complete and hence cannot decide the halting problem.

  • Kael Aaron

    Kael Aaron

    2 dögum síðan

    O ÷ 0


    Am i a joke to you?

  • Dark Rainbow

    Dark Rainbow

    2 dögum síðan

    Divide zero cookies among your zero friends.

  • Neko

    Neko

    2 dögum síðan

    simple, 0 divided by 0.

  • Dum Dum

    Dum Dum

    3 dögum síðan

    Hasn't it already been answered in Godel's incompleteness theorem?

  • noa van der hoorn

    noa van der hoorn

    3 dögum síðan

    Answer: Yes, me having no social life.

  • thirteen13stuff

    thirteen13stuff

    3 dögum síðan

    why did this video explain the halting problem 1000 times better than my lecturer ever could

  • Jacob Degeling

    Jacob Degeling

    3 dögum síðan

    I'm a computer scientist and you really over-simplified that and skipped a lot of things

  • doggywhiskerbut

    doggywhiskerbut

    3 dögum síðan

    What is 0/0?

  • Charles Rankin

    Charles Rankin

    4 dögum síðan

    Will Quantum Computing change any of this, since it doesn't work on the same laws traditional Computers do?

  • Max Quizon

    Max Quizon

    4 dögum síðan

    Nice. This topic just killed 10 of my braincells😅

  • Radu Coroi

    Radu Coroi

    5 dögum síðan

    Let me save you some time and answer the question in the title real quick. The answer is yes.

  • Gaming Doe

    Gaming Doe

    5 dögum síðan

    An error occurred. Please try again later. (Playback ID: 3shaUIqlBSdcKxjb)
    Learn More

  • bouhannache abdallah

    bouhannache abdallah

    5 dögum síðan

    The halt loop machine isnt so clever
    I guess that the(result will definelty loop) and so it will think that the program feed to it self will loop also (that not considering recursion ).

  • megatrook

    megatrook

    5 dögum síðan

    looping or not looping isnt... solving or not solving... like, you're not wrong, but you're also asking two things

    • tawtawta gWRgRWhETE6j

      tawtawta gWRgRWhETE6j

      5 dögum síðan

      "does it loop or does it halt" is the problem that we are trying to solve. You misunderstood

  • Timo jissink

    Timo jissink

    5 dögum síðan

    In human logic we recognize that it is a paradox, so we halt

  • Pro QBr

    Pro QBr

    5 dögum síðan

    This channel is a blessing. Such a variety of interesting content.

  • Touami

    Touami

    5 dögum síðan

    This whole concept is like the paradox "This statement is not true"

  • Cairo Fahrenheit

    Cairo Fahrenheit

    6 dögum síðan

    Watching this whilst off your head on Ketamine is a very bad Idea

    • mixio hili

      mixio hili

      5 dögum síðan

      say the earth is large. But now look at the sun and you see the earth is small. Its all relative.

  • TriggAndSides

    TriggAndSides

    6 dögum síðan

    How come we can tell which program will infinitely loop and which will halt, how are our brains fundamentally different from a computer in the way they function ? What makes our brains different? I don't believe there is a difference therefore I speculate something like machine learning or any neural network based code could be able to solve this problem.If you disagree then you must believe our brains are not fundamentally computers or at least don't function in the same way but then how do they?

    • mixio hili

      mixio hili

      5 dögum síðan

      way above one of earths poles. You look down and see it spinning clockwise. Now float around the earth to above the other pole. And look down. You now see its spinning

  • yroohj gouy

    yroohj gouy

    6 dögum síðan

    great vid babe

  • hameedullah jasat

    hameedullah jasat

    6 dögum síðan

    Hi Tom great video... How does this relate to humans and AI

    • yroohj gouy

      yroohj gouy

      6 dögum síðan

      Yes. Try to ask my computer why the internet is down.

  • Nelson Yeung

    Nelson Yeung

    6 dögum síðan

    This sound so similar to the Gödel's incompleteness theorems. Are they related?

  • Lemonade Boys Official

    Lemonade Boys Official

    6 dögum síðan

    Hey Tom Scott did you really Change your YouTube language to millennial language? I’m trying it right now

  • Evan Davies

    Evan Davies

    6 dögum síðan

    large prime product factorization

  • Kenneth Dias

    Kenneth Dias

    7 dögum síðan

    Computers can’t solve problem. People solve problems computers are the tools we use.

  • pyroawsome

    pyroawsome

    7 dögum síðan

    Thanks for the flashbacks to CS classes. Ouch, my head does not comprehend advanced math enough to understand the full P =/= NP proofs.

  • amazingmikeyc

    amazingmikeyc

    7 dögum síðan

    On BBC basic you have too have a semi colon at the end of the print statement or it goes on to the next line

    • bilinas mini

      bilinas mini

      7 dögum síðan

      Why is your body so small

  • mazhar said

    mazhar said

    7 dögum síðan

    can u help at all ? im looking for Lander with sound fx? for the Acorn Archimedes A3000? thanks.

  • Adam Fakes

    Adam Fakes

    7 dögum síðan

    possibly meta-analysis could work here, while we cannot be 100% certain would could have a probabilistic answer, say we might know with 95% that this program will halt or not. Will a rock thrown from a building always hit the ground. What we know of the environment and it's initial conditions, can can supply a answer with a high degree of confidence. So we don't have to run the program to know what the outcome will be.

    • sqrooty

      sqrooty

      7 dögum síðan

      In what parameter would the answer be probabilistic? In computer science, there is a machine called a "probabilistic turing machine" (PTM) that is intended to model a certain useful notion of probability, namely roughly that a turing machine only has to correctly accept/deny an input more than 50% of the time. It turns out that PTMs are turing complete, i.e. they too cannot solve the halting problem.

  • Shauka Hodan

    Shauka Hodan

    7 dögum síðan

    Me: googles "Are there any problems a computer can't solve?" Computer: ERROR 404

  • faisal does everything

    faisal does everything

    7 dögum síðan

    Me :


    Pi

    • Shauka Hodan

      Shauka Hodan

      7 dögum síðan

      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 fi

  • Shu Ning Lim

    Shu Ning Lim

    7 dögum síðan

    So you're saying you feed the output of opposite back into itself? But dont you need some starting input to start it off?

    • sqrooty

      sqrooty

      7 dögum síðan

      Tom simplified a lot. In the real halting problem, we ask whether a turing machine halts on a specific input, and then a halting problem decider is a program H(program_code, input_to_program). The opposite machine only takes a single input; it is a program O(program_code). O calls H(program_code, program_code), i.e. it passes the program code it got for the parameter as *both* the program code and the input. Now, whether O(code_of_O) halts depends on whether H(code_of_O, code_of_O) halts, which by the definition of H again depends on whether O(code_of_O) halts. So O does indeed not need some starting input, because it passes the code it gets as both the program and the input to H. We can then derive a contradiction from this circularity because we defined that O halts if and only if H does not halt.

  • Tony

    Tony

    8 dögum síðan

    Love the Hitchhiker's Guide to the Galaxy reference there 👍🏻

  • Youva Boutora

    Youva Boutora

    8 dögum síðan

    As true as it is in theory. it's hard to think of real world problems computers cannot solve. I mean computers are basically extremely obedient and extremely dumb slaves, you can't ask a slave to solve the Riemann Hypothesis but you can ask him to file your taxes.

  • Stephen Dickens

    Stephen Dickens

    8 dögum síðan

    Is it like saying which way does the earth rotate? Do you think you know which way it rotates? Truth is it rotates in both directions at once. How can that be. Imagine your in space way above one of earths poles. You look down and see it spinning clockwise. Now float around the earth to above the other pole. And look down. You now see its spinning counter clockwise. Understand now? Everything is simply a relation to something else to define its truth. You can say is the earth large or small. And then look at the moon and say the earth is large. But now look at the sun and you see the earth is small. Its all relative.

  • dave z

    dave z

    8 dögum síðan

    The real question is are there any problems that a computer can solve?

  • Tom5tom Entertainment

    Tom5tom Entertainment

    8 dögum síðan

    Yes. Try to ask my computer why the internet is down.

  • rautermann

    rautermann

    8 dögum síðan

    I'm not too impressed, to be honest. This is just saying that logic machines can't solve a paradox - which is defined by being unsolvable by logic. I don't see the surprise there.

  • Lilitu, The Betrayer

    Lilitu, The Betrayer

    8 dögum síðan

    Advanced AI: Well, hello there!

  • ablationer

    ablationer

    8 dögum síðan

    So that's why paradoxes always make robots blow up in movies.

  • bilinas mini

    bilinas mini

    8 dögum síðan

    Me: googles "Are there any problems a computer can't solve?" Computer: ERROR 404

  • anidog

    anidog

    8 dögum síðan

    SOMETHING RUDE

    • bilinas mini

      bilinas mini

      8 dögum síðan

      Tom: Are there problems computer can't solve? Captcha: Am I a joke to you?

  • Hamed Hosseini

    Hamed Hosseini

    8 dögum síðan

    yes, naming a computer file a "CON"

  • Boiled Egg

    Boiled Egg

    8 dögum síðan

    Why is your body so small

  • gtiman

    gtiman

    8 dögum síðan

    6:12 thanks Douglas Adams. 👌

  • Shadow VI

    Shadow VI

    8 dögum síðan

    Life

  • featureEnvy

    featureEnvy

    9 dögum síðan

    I originally deleted this because I was afraid it was a stupid question but you know what I kind of just want to know...So I'm gonna leave it here anyway. I'm new to quantum computing, and I admit I don't really have a good understanding of it yet. But I was wondering, does this apply to quantum computers? The way I understand it, to know whether the program halts or continues, wouldn't you have to actually observe the result? So wouldn't it be that, in the case of a quantum computer, you COULD solve EVERY problem, but only some of the time?

    • mikea hiooi

      mikea hiooi

      9 dögum síðan

      42

  • Adam Hoelscher

    Adam Hoelscher

    9 dögum síðan

    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).

    • mikea hiooi

      mikea hiooi

      9 dögum síðan

      42

  • Yasir Javed

    Yasir Javed

    9 dögum síðan

    Yes. Computer can't solve emotional and feelings problems. Can't fix broken heart, can't do anything by its own actually

  • Oliwer G.

    Oliwer G.

    9 dögum síðan

    1:14 legit thats how gta online works

  • mixio hili

    mixio hili

    9 dögum síðan

    I feel that getting into a debate with Turing would have been a bad idea..

  • Timothy Murauzi

    Timothy Murauzi

    9 dögum síðan

    Yes, no Super Computer can work out why I don't have a girlfriend

  • HarrysDog malaysia

    HarrysDog malaysia

    9 dögum síðan

    Anyone remember GLaDOS?

    • mixio hili

      mixio hili

      9 dögum síðan

      I know! Those sometimes illogical mathematical textual tasks.

  • Max M

    Max M

    9 dögum síðan

    Why doesn’t Tom have a late night show yet..?

  • LazarPal

    LazarPal

    10 dögum síðan

    i mean, some computer found out that the meaning of life is 42

  • Ben S.

    Ben S.

    10 dögum síðan

    So... im German, so I could read that

    Dunno why I had to say that

  • mek Is cool

    mek Is cool

    10 dögum síðan

    Yes

  • TheTiger107 - PUBGM,Gaming,Technology & More

    TheTiger107 - PUBGM,Gaming,Technology & More

    10 dögum síðan

    Tom: Are there problems computer can't solve?
    Captcha: Am I a joke to you?

  • TheTiger107 - PUBGM,Gaming,Technology & More

    TheTiger107 - PUBGM,Gaming,Technology & More

    10 dögum síðan

    Tom: Are there problems computer can't solve?
    Captcha: Allow me to introduce myself...

    • Vaibryn

      Vaibryn

      10 klukkustundum síðan

      That's kinda ironic, cause computers are used to generate those Captchas.

  • Wilson

    Wilson

    10 dögum síðan

    Windows XP can't cure my AIDS

  • MisterQuantum77

    MisterQuantum77

    10 dögum síðan

    Only humanity, but maybe computers will fix that problem someday too. All hail our future robot overlords!

  • Thefreakyfreek

    Thefreakyfreek

    10 dögum síðan

    42

    • alida flus

      alida flus

      10 dögum síðan

      crash/destroy your computer? Please, let me know what the answer is.

  • Thefreakyfreek

    Thefreakyfreek

    10 dögum síðan

    42

    • Thefreakyfreek

      Thefreakyfreek

      7 dögum síðan

      @alida flus 42

    • alida flus

      alida flus

      10 dögum síðan

      When you live-stream (with face-cam) and you're watching your own on stream. You get a "droste effect" question: But what if you have that "droste effect", will it ever stop or

  • Thefreakyfreek

    Thefreakyfreek

    10 dögum síðan

    42

  • Thefreakyfreek

    Thefreakyfreek

    10 dögum síðan

    42