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.