The Halting Problem: The Unsolvable Problem
One of the most influential problems and proofs in computer science, first introduced and proved impossible to solve by Alan Turing. The video provides the idea of this incredibly clever proof. I highly recommend anyone who is comfortable with mathematical proofs to read the formal proof to the problem (look at additional resources below for information).
Also, the video does not cover this, but the significance of this unsolvable problem cannot be understated. By logically proving that the Halting Problem is impossible to solve, this means that there is an entire class of problems that can never be solved through computing (i.e. undecidable problems). For example, the Halting Problem tells us that it is impossible to come up with a general algorithm/program/machine that tells us if another algorithm/program/machine will ever halt. This means it would be impossible to come up with an algorithm that does something as simple as determine if a program only prints "A". This is because we can reduce the problem of determining whether a program halts to the problem of determining whether a program prints “A”: Take the description of the original program and change every exit/return statement to a “print A” statement. The new program prints “A” precisely if the original program halts, and being able to determine if the program prints "A" would mean we can determine if the program halts and, therefore, solving the Halting Problem. However, as Turing had proved, the Halting Problem is unsolvable, an algorithm that determines if another algorithm halts cannot exist; what more determine if a program prints something?
___________________________________________________________
Additional resources to understand this INCREDIBLE PROOF:
Turing, A.M. (1937), On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42: 230-265. doi:https://doi.org/10.1112/plms/s2-42.1.230
- Alan Turing's original paper and proof to the Halting Problem. This is also the paper where he first introduced the idea of Turing Machines. It might be interesting to note he did not call it the Halting Problem in this paper. In fact, it wasn't until a later paper that the term 'halting problem' was introduced.
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
- The main source of my Theory of Computation knowledge (a textbook). Read Chapter 4.2: Undecidability to learn about the diagonalization technique used in this proof, and to see a more formal proof.
Hodges, Andrew, "Alan Turing", The Stanford Encyclopedia of Philosophy (Winter 2019 Edition), Edward N. Zalta (ed.), https://plato.stanford.edu/archives/win2019/entries/turing/.
- To read more about Alan Turing and his ideas!
___________________________________________________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
Видео The Halting Problem: The Unsolvable Problem канала lydia
Also, the video does not cover this, but the significance of this unsolvable problem cannot be understated. By logically proving that the Halting Problem is impossible to solve, this means that there is an entire class of problems that can never be solved through computing (i.e. undecidable problems). For example, the Halting Problem tells us that it is impossible to come up with a general algorithm/program/machine that tells us if another algorithm/program/machine will ever halt. This means it would be impossible to come up with an algorithm that does something as simple as determine if a program only prints "A". This is because we can reduce the problem of determining whether a program halts to the problem of determining whether a program prints “A”: Take the description of the original program and change every exit/return statement to a “print A” statement. The new program prints “A” precisely if the original program halts, and being able to determine if the program prints "A" would mean we can determine if the program halts and, therefore, solving the Halting Problem. However, as Turing had proved, the Halting Problem is unsolvable, an algorithm that determines if another algorithm halts cannot exist; what more determine if a program prints something?
___________________________________________________________
Additional resources to understand this INCREDIBLE PROOF:
Turing, A.M. (1937), On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42: 230-265. doi:https://doi.org/10.1112/plms/s2-42.1.230
- Alan Turing's original paper and proof to the Halting Problem. This is also the paper where he first introduced the idea of Turing Machines. It might be interesting to note he did not call it the Halting Problem in this paper. In fact, it wasn't until a later paper that the term 'halting problem' was introduced.
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
- The main source of my Theory of Computation knowledge (a textbook). Read Chapter 4.2: Undecidability to learn about the diagonalization technique used in this proof, and to see a more formal proof.
Hodges, Andrew, "Alan Turing", The Stanford Encyclopedia of Philosophy (Winter 2019 Edition), Edward N. Zalta (ed.), https://plato.stanford.edu/archives/win2019/entries/turing/.
- To read more about Alan Turing and his ideas!
___________________________________________________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
Видео The Halting Problem: The Unsolvable Problem канала lydia
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![The Halting Problem - An Impossible Problem to Solve](https://i.ytimg.com/vi/t37GQgUPa6k/default.jpg)
![Why study theory of computation?](https://i.ytimg.com/vi/SV57Yv8BXBc/default.jpg)
![Halting Problem & Quantum Entanglement 2020 Breakthrough result [MIP*=RE]](https://i.ytimg.com/vi/2H8629BCbkM/default.jpg)
![Proof That Computers Can't Do Everything (The Halting Problem)](https://i.ytimg.com/vi/92WHN-pAFCs/default.jpg)
![P vs. NP and the Computational Complexity Zoo](https://i.ytimg.com/vi/YX40hbAHx3s/default.jpg)
![The unsolved math problem which could be worth a billion dollars.](https://i.ytimg.com/vi/8COArd_EREw/default.jpg)
![Turing & The Halting Problem - Computerphile](https://i.ytimg.com/vi/macM_MtS_w4/default.jpg)
![](https://i.ytimg.com/vi/Eg4ap4pyZo4/default.jpg)
![Impossible Programs (The Halting Problem)](https://i.ytimg.com/vi/wGLQiHXHWNk/default.jpg)
![Are There Problems That Computers Can't Solve?](https://i.ytimg.com/vi/eqvBaj8UYz4/default.jpg)
![What is the Pumping Lemma](https://i.ytimg.com/vi/qtnNyUlO6vU/default.jpg)
![CSC180: The Halting Problem: a 7 minute proof](https://i.ytimg.com/vi/r24f3RmMjHs/default.jpg)
![Undecidable Problems: Reducibility (Part 1) | What are Reductions?](https://i.ytimg.com/vi/U4yGQp5aCTM/default.jpg)
![Turing Machines Explained - Computerphile](https://i.ytimg.com/vi/dNRDvLACg5Q/default.jpg)
![Why is the Halting Problem Undecidable?](https://i.ytimg.com/vi/4tbCR10QGTI/default.jpg)
![Alan Turing - betrayed by the country he saved](https://i.ytimg.com/vi/ynTAFPukXBk/default.jpg)
![The Halting Problem](https://i.ytimg.com/vi/6XZvw9W9QSc/default.jpg)
![Halting Problem in Python - Computerphile](https://i.ytimg.com/vi/r__GZ7ubU0M/default.jpg)
![Nonregular languages: How to use the Pumping Lemma](https://i.ytimg.com/vi/Ph7Z9YttM0Q/default.jpg)
![The Simplest Math Problem No One Can Solve - Collatz Conjecture](https://i.ytimg.com/vi/094y1Z2wpJg/default.jpg)