Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

The Halting Problem: The Unsolvable Problem

lydia4:14 247.055 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 26 Zeilen
Herunterladen
  1. Computers have helped us solve and achieve many things They run complex algorithms fast and allow us to analyze incredibly large data sets to answer our questions
  2. Save and access our work from anywhere and make and watch videos So as our computers become faster and more powerful, is there ever a limit to what computers can do
  3. As in, is there anything that even the most powerful supercomputer with an infinite amount of memory and processing power will never be able to solve
  4. In fact there are Queue the halting problem
  5. The halting problem asks, is it possible to write a program that determines whether another program halts? By halt we mean whether it ultimately stops and exits
  6. A program that never halts is one that has an infinite loop for example Alan Turing both proposed and proved that the halting problem is in fact
  7. unsolvable using a formal proof by contradiction We won't go through the formal proof, but here's the idea of the proof
  8. We assume that we do in fact have a program that always correctly determines whether another program halts Let's call this magical program H
  9. H takes in another program as input and after scanning through the program it tells us if the program will halt or if the program will run forever
  10. Now let's create a bigger machine D that encompasses H D is designed such that for every input it gets it gives it to H
  11. and whatever H says, it does the opposite So if H says the program runs forever, then D will halt and if H says that the program halts
  12. then D never halts So that's our machine D
  13. The contradiction arises when we give machine D its own program So when D takes in its own program as input. It passes it to H and H decides whether D will halt
  14. Let's say H determines that D will halt but because D is designed to do the opposite of what H says Then D ends up running forever
  15. Even though H said D will halt This means H is wrong
  16. but we assumed in the beginning that H is always right So let's try again D takes in its own program and process it to H
  17. but this time H says D does not halt and runs forever And again, because D is designed to do the opposite of what H says, D halts
  18. H is wrong again But remember in the beginning
  19. we assume that this magical program H always correctly tells us if a program will halt exists But our experiment with D just showed that if H existed and we built D using H
  20. Then H can be wrong This contradicts our initial assumption that H is always right
  21. Therefore a program such as H that correctly determines if another program will halt cannot exist So that's the halting problem and again not even the most powerful
  22. supercomputer will be able to solve the halting problem Asking a supercomputer to solve the problem would be like asking
  23. the supercomputer to come up with a triangle with four sides Logically, it makes no sense
  24. So yeah, the halting problem is pretty significant And mind-blowing when you really think about it
  25. It's also just incredible how mathematicians and computer scientists have rigorously proved that there are problems that can never be algorithmically solved
  26. So the next time someone tells you that computers will one day solve everything just tell them about the halting problem

Zum Nachlesen

HalteproblemDas Halteproblem beschreibt eine Frage aus der theoretischen Informatik. Wenn für eine Berechnung mehrere Rechenschritte nach festen Regeln durchgeführt … DiagonalspracheDie Diagonalsprache ist die zentrale Konstruktion im Beweis der Unentscheidbarkeit des Halteproblems. Die Konstruktion der Sprache basiert auf dem Prinzip der … RekursionssatzDie Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case. NP-SchwereNP-Schwere bezeichnet die Eigenschaft eines algorithmischen Problems, mindestens so schwer lösbar zu sein wie die Probleme der Klasse NP.