Are There Problems That Computers Can't Solve?

Tom Scott
10 812 Áhorf 1,1 m.

All about Hilbert's Decision Problem, Turing's solution, and a machine that vanishes in a puff of logic. MORE BASICS: ispulse.info/list-PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha.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

Ummæli

  1. Tom Scott
    Tom Scott
    14 dögum síðan

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

    1. NocturneInNeon
      NocturneInNeon
      6 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.

    2. Nicholas Hughes
      Nicholas Hughes
      7 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!

    3. Thor Thorbjornsen
      Thor Thorbjornsen
      8 dögum síðan

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

    4. jm 101
      jm 101
      8 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

    5. Dragonfury
      Dragonfury
      9 dögum síðan

      The "Opposite" program needs an input in order to do something. Without an input, it sits there and does nothing at all. So if you feed the opposite program itself, the correct answer wouldn't be "halts" or "doesnt halt", it would be a third option called "Nothing happens"

  2. pyroawsome
    pyroawsome
    11 klukkustundum 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.

  3. amazingmikeyc
    amazingmikeyc
    11 klukkustundum 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

  4. mazhar said
    mazhar said
    14 klukkustundum síðan

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

  5. Adam Fakes
    Adam Fakes
    22 klukkustundum 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.

    1. sqrooty
      sqrooty
      19 klukkustundum 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.

  6. Shauka Hodan
    Shauka Hodan
    23 klukkustundum síðan

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

  7. faisal does everything
    faisal does everything
    Degi Síðan síðan

    Me : Pi

    1. Shauka Hodan
      Shauka Hodan
      23 klukkustundum 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

  8. Shu Ning Lim
    Shu Ning Lim
    Degi Síðan 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?

    1. sqrooty
      sqrooty
      19 klukkustundum 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.

  9. Tony
    Tony
    Degi Síðan síðan

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

  10. Youva Boutora
    Youva Boutora
    Degi Síðan 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.

  11. Stephen Dickens
    Stephen Dickens
    Degi Síðan 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.

  12. dave z
    dave z
    Degi Síðan síðan

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

  13. Tom5tom Entertainment
    Tom5tom Entertainment
    Degi Síðan síðan

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

  14. rautermann
    rautermann
    Degi Síðan 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.

  15. Lilitu, The Betrayer
    Lilitu, The Betrayer
    Degi Síðan síðan

    Advanced AI: Well, hello there!

  16. ablationer
    ablationer
    Degi Síðan síðan

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

  17. bilinas mini
    bilinas mini
    Degi Síðan síðan

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

  18. anidog
    anidog
    Degi Síðan síðan

    SOMETHING RUDE

    1. bilinas mini
      bilinas mini
      Degi Síðan síðan

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

  19. Hamed Hosseini
    Hamed Hosseini
    2 dögum síðan

    yes, naming a computer file a "CON"

  20. Boiled Egg
    Boiled Egg
    2 dögum síðan

    Why is your body so small

  21. gtiman
    gtiman
    2 dögum síðan

    <a href="#" class="seekto" data-time="372">6:12</a> thanks Douglas Adams. 👌

  22. Shadow VI
    Shadow VI
    2 dögum síðan

    Life

  23. featureEnvy
    featureEnvy
    2 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?

    1. mikea hiooi
      mikea hiooi
      2 dögum síðan

      42

  24. Adam Hoelscher
    Adam Hoelscher
    2 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).

    1. mikea hiooi
      mikea hiooi
      2 dögum síðan

      42

  25. Yasir Javed
    Yasir Javed
    2 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

  26. Oliwer G.
    Oliwer G.
    2 dögum síðan

    <a href="#" class="seekto" data-time="74">1:14</a> legit thats how gta online works

  27. mixio hili
    mixio hili
    2 dögum síðan

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

  28. Timothy Murauzi
    Timothy Murauzi
    3 dögum síðan

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

  29. HarrysDog malaysia
    HarrysDog malaysia
    3 dögum síðan

    Anyone remember GLaDOS?

    1. mixio hili
      mixio hili
      2 dögum síðan

      I know! Those sometimes illogical mathematical textual tasks.

  30. Max M
    Max M
    3 dögum síðan

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

  31. LazarPal
    LazarPal
    3 dögum síðan

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

  32. Ben S.
    Ben S.
    3 dögum síðan

    So... im German, so I could read that Dunno why I had to say that

  33. mek Is cool
    mek Is cool
    3 dögum síðan

    Yes

  34. TheTiger107 - PUBGM,Gaming,Technology & More
    TheTiger107 - PUBGM,Gaming,Technology & More
    3 dögum síðan

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

  35. TheTiger107 - PUBGM,Gaming,Technology & More
    TheTiger107 - PUBGM,Gaming,Technology & More
    3 dögum síðan

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

  36. Wilson
    Wilson
    3 dögum síðan

    Windows XP can't cure my AIDS

  37. MisterQuantum77
    MisterQuantum77
    3 dögum síðan

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

  38. Thefreakyfreek
    Thefreakyfreek
    3 dögum síðan

    42

    1. alida flus
      alida flus
      3 dögum síðan

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

  39. Thefreakyfreek
    Thefreakyfreek
    3 dögum síðan

    42

    1. Thefreakyfreek
      Thefreakyfreek
      23 klukkustundum síðan

      @alida flus 42

    2. alida flus
      alida flus
      3 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

  40. Thefreakyfreek
    Thefreakyfreek
    3 dögum síðan

    42

  41. Thefreakyfreek
    Thefreakyfreek
    3 dögum síðan

    42

  42. Thefreakyfreek
    Thefreakyfreek
    3 dögum síðan

    42

  43. Eurosauce
    Eurosauce
    4 dögum síðan

    Just add a check that checks for an opposite paradox, and put a third output that tells the user that their mom doesn't actually love them because they fed a paradox to their machine, eh?

  44. PurpleHazeRunner X
    PurpleHazeRunner X
    4 dögum síðan

    I know! Those sometimes illogical mathematical textual tasks.

  45. Chris Hofmann
    Chris Hofmann
    4 dögum síðan

    Poke 808,234

  46. lreinirz
    lreinirz
    4 dögum síðan

    "vanishes in a puff of logic" Aha now there's a subtle Hitchhiker's reference

    1. mikea hiooi
      mikea hiooi
      4 dögum síðan

      our maths and computers cant..... what about aliens

  47. enno s.
    enno s.
    4 dögum síðan

    What you could do is that you implement in the Code of the Programm some kind of Signature that this is a code checking programm and then the computer ignores te Part of the Code where the possible input would be the code itself. And I know that the Programm is than skipping some parts of a code and the answer would not be true, but the Code would check every other part of the code.

    1. mikea hiooi
      mikea hiooi
      4 dögum síðan

      the hitchhiker's guide to the galaxy

  48. SALT!
    SALT!
    4 dögum síðan

    Wouldn't the solution be to just make sure the prompt was never entered?

  49. Bretzel
    Bretzel
    4 dögum síðan

    Best question to ask a computer is [any number]÷0

  50. Nitro CENTRAL
    Nitro CENTRAL
    4 dögum síðan

    you filmed this at the computer history museum in cambridge, tom scott

  51. Joe O Sullivan
    Joe O Sullivan
    4 dögum síðan

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

  52. KokahZ777
    KokahZ777
    4 dögum síðan

    I don't get it: Opposite has a case where it infinitely loops so feeding opposite into opposite should always halt

  53. Denver Morgan
    Denver Morgan
    4 dögum síðan

    They really paid Turing back for his help.

  54. monika laosi
    monika laosi
    4 dögum síðan

    Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

  55. Sebastiaan van de Wetering
    Sebastiaan van de Wetering
    4 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 crash/destroy your computer? Please, let me know what the answer is.

    1. monika laosi
      monika laosi
      4 dögum síðan

      "then it vanishes in a puff of logic" Hitchhiker's Guide reference?

  56. Bloxxed
    Bloxxed
    4 dögum síðan

    It can’t solve my marriage

  57. Roverdrive X
    Roverdrive X
    5 dögum síðan

    I'm not entirely convinced by the answer that inputting Opposite's own code into Opposite will create a paradox, but I assume that's a result of the simplification. What the Input Opposite's "Halts" outputs shouldn't matter at all to the external Opposite, it would only care about the output of the internal "+"'s reversing code. If you provide the Input Opposite with halting code, then + will create an infinite loop as the ultimate result of the code, and so the external Opposite would process that in its Halts and its + would halt the program. If you provide the Input Opposite with looping code, + will halt, and the external Opposite would then loop. If you're judging Opposite purely with its potential results in mind, Opposite's code alone is not enough to determine whether or not it will halt. It requires an input in order to determine anything. It wouldn't create a *paradox*, it just wouldn't be able to provide an answer because the code you inputted was incomplete; it doesn't run. The only problematic and potentially paradoxical scenario would be if you also provided the Input Opposite with Opposite's code, and that Input Input Opposite with Opposite's code as well, infinitely. Only then would the answer be indeterminable and self-contradictory, but that scenario is impossible to execute in reality and therefore, arguably, not very useful for determining the abilities of our computers.

    1. dlarge6502
      dlarge6502
      2 dögum síðan

      > The only problematic and potentially paradoxical scenario would be if you also provided the Input Opposite with Opposite's code That is what the video and the problem is about. Its even said in the video. Opposite is given its OWN code to test. Thats the problem and thats the reason there can never be a solution to figuring out if any particular program will halt or not. Remember this is simplified, the program you would test in real life would be something much bigger with many inputs and code paths. Turing proved that computers can not solve ALL problems because this paradox exists thus if a computer can not determine if Opposite will halt or not given Opposite as its own input then that is at least 1 problem that can never be solved. The next question is, is this the ONLY problem that a computer can not solve? The problem here is as Turing proved, you cant prove a program will ever halt, so...

  58. Gavin B.
    Gavin B.
    5 dögum síðan

    You just need Captain Kirk to reason logic with a computer, and it will eventually self-destruct.

  59. noob gamer
    noob gamer
    5 dögum síðan

    Alex Turing? the guy who made the turing test? or is that another guy?

  60. Diggnuts
    Diggnuts
    5 dögum síðan

    The problem precented does not quite melt human brains, now does it? Brains being computers of a type can spot the paradox and output the third choice, namely this machine is bollocks. I'd call that solved.

    1. mikea hiooi
      mikea hiooi
      5 dögum síðan

      Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

  61. apollion888
    apollion888
    5 dögum síðan

    I got my Comp Sci degree 30 years ago and really enjoyed this, thanks

    1. mikea hiooi
      mikea hiooi
      5 dögum síðan

      1:13 you got me there for a sec

  62. delete delete
    delete delete
    5 dögum síðan

    the hitchhiker's guide to the galaxy

  63. delete delete
    delete delete
    5 dögum síðan

    our maths and computers cant..... what about aliens

  64. vicdmise
    vicdmise
    5 dögum síðan

    "Vanishes in a puff of logic...". Thank you, Douglas Adams, wherever you are."

  65. jason rieder
    jason rieder
    5 dögum síðan

    I would love to see a more in depth version of this video.

  66. Froyo Time
    Froyo Time
    5 dögum síðan

    BBC micros

  67. Matrix Teknologies [Joseph Clarke]
    Matrix Teknologies [Joseph Clarke]
    5 dögum síðan

    if human can't resolve a paradox, why would a computer be able solve when some thing has infinite solutions or can't reach the ultimate state using recursive it can't be solve. the world is finite but boundless count the numbers between zero and 1 try to approach zero with a function that reduce it self to zero try to count to infinite

  68. AdamBomb
    AdamBomb
    5 dögum síðan

    So the answer to the question, *is* the question?

  69. Gill Bates
    Gill Bates
    5 dögum síðan

    sure cant solve 0 divided by 0

  70. Alejandro Fernández
    Alejandro Fernández
    5 dögum síðan

    Not only is impossible for a computer yo solve, it is impossible for anyone to solve.

  71. Ariel Schoonover
    Ariel Schoonover
    6 dögum síðan

    "then it vanishes in a puff of logic" Hitchhiker's Guide reference?

  72. Haameem Hashmi
    Haameem Hashmi
    6 dögum síðan

    This is the only channel where I am FORCED to watch the vids in 0.5x

  73. Liam McGowan
    Liam McGowan
    6 dögum síðan

    it simply requires a subjective analysis. what the opposite box does is introduce the concept of scale. not amount, numbers, mathematics etc... SCALE this is a subjective concept that cannot be processed in absolute terms without defining 3 axis of space in order to define SCALES (which may or may not be infinite) in which to place comparative analyses, so that we may compare the recycled opposite box to the active opposite box. this is required because on/off / 0 and 1 / any binary mechanism cannot distinguish subjective data because it is not stereoscopic in it's nature. if turin had based his science on a rheostat instead of a switch we would have been using a superior alternative to binary from the outset. instead of a 'transistor' reading 0 or 1 and nothing else, thereby limiting all computers to the momentum of their absolute origins we might have had something akin to a diode which could be on, off, flowing one direction, flowing the other direction, in an alternating state with a zener buffer or in a resistive state (open at both ends) the problem with academics who focus their lives on specialization is the more specialized they become, the narrower the thinking. the qbit revolution has arrived so this is all irrelevant. we could have saved ourselves a lot of limitations in the meantime by constructing our transistor wafers as a pair of isolated circuits with semiconducting junctions forming a matrices and tailoring machine code to take advantage of this. hardware ascii if you will. in conclusion, it is not a 'problem computers cannot solve' but more a 'problem that cannot be solved by using switches, no matter how complex the circus, the limitations of the switch is fundamental' Liam

    1. sqrooty
      sqrooty
      5 dögum síðan

      Quantum computers cannot solve the halting problem either because you can simulate a quantum computer with a turing machine. It's turing complete.

  74. =NolePtr
    =NolePtr
    6 dögum síðan

    The halting problem is flawed because it's determined by an undefined initial state, ie. input. The resulting input of Opposite(Opposite(FN)) is just Halts(FN). Since FN is unknown, Halts(FN) is obviously unknown.

  75. Brian Kerr
    Brian Kerr
    6 dögum síðan

    What is the answer to the question of life the universe and everything ?

    1. Passeron
      Passeron
      6 dögum síðan

      47

    2. slam zamillion
      slam zamillion
      6 dögum síðan

      47

  76. Tavas
    Tavas
    6 dögum síðan

    <a href="#" class="seekto" data-time="73">1:13</a> you got me there for a sec

  77. alida flus
    alida flus
    6 dögum síðan

    Alan Turing: "Hey guys. I have broken through the german code!" British government: "Why are you gay?"

  78. Shawn Boudreau
    Shawn Boudreau
    6 dögum síðan

    When you try to solve a mathematical problem so hard that it turns into a philosophical one.

    1. alida flus
      alida flus
      6 dögum síðan

      Gödel's incompleteness meme?

  79. BmnGameBoy
    BmnGameBoy
    6 dögum síðan

    It can't solve its own problems

  80. Alison Hörn
    Alison Hörn
    6 dögum síðan

    /0