Impossible Programs (The Halting Problem)

there it is the spinning wheel of death caused by an infinite loop in a computer program wouldn't it be great if we had something that could find these infinite loops so that we could catch them let's be clear about what we mean for example the program while true print hello world will loop forever but the program that is just print hello world halts after printing hello world what we want to do is create an algorithm the decider that takes in a program and an input for the program and can tell you if the program halts or loops forever when run on the input it may seem a little weird to feed a program into another program but to a computer a program is just a text file as we will see in a future video this means that it's really just one big number and giving a number to a program isn't really a big deal determining of a program loops or halts on an input is known as the halting problem and is extremely hard in fact it's so hard that it's undecidable or impossible to solve I want to emphasize that when I say impossible I don't mean that we're looking for a better solution or that we're trying to find an answer I mean that no matter what we try to do we'll never come up with a program that can solve the halting problem let's think of a naive algorithm or procedure to get an intuition as to what makes this problem so hard for example our solution might be always say it halts our solution could also be always say loops for any given program one of these two solutions must be correct but the other will also be wrong let's try making a program that won't give a wrong answer maybe our algorithm lets the program run on an input for a second and then we check if it halted or not if it didn't well maybe it just needs 10 seconds if it still didn't well maybe it just needs an hour this quickly turns into a slippery slope where a decider just loops forever if the input program loops instead of giving an answer rather than solving the problem we just reiterated it in order to prove that the halting problem is undecidable we'll use a technique called proof by contradiction if you don't understand how it works check out our previous video where we prove that there are different sizes of infinity x' so assume for the sake of contradiction that we solve the halting problem that means that we have a magical Oracle which will be able to tell you with 100% accuracy whether a given program halts on a given input what we're going to do is create a brand new program let's call it mr. Smith mr. Smith takes it in a program as input and then asks the Oracle what happens when that program is run with itself as input if the Oracle says that it loops forever then mr. Smith will halt and call it a day if the Oracle says that the program will halt the mr. Smith will loop forever now here's the interesting question does mr. Smith when given itself as input loop or halt let's say that the Oracle predicts that mr. Smith will loop forever when running itself but what does mr. Smith actually do in that case it halts but if the Oracle predicts that mr. Smith will halt the mr. Smith will actually loop forever like a rebellious teenager mr. Smith is designed to do the opposite of whatever the Oracle says it should do this means that whether mr. Smith actually loops or halts the Oracle must always give the wrong answer which means that the Oracle is a sham contradicting our assumption that the Oracle solves the halting problem all of these shenanigans with looping if it halts and halting if it loops and programs getting fed into itself can all be very confusing so let's think about this proof in another way using Cantor's diagonal ization be sure to check out our previous videos on comparing infinities and Catherine's diagonalization for a better understanding of this alternate proof we'll start our new explanation the same way assume for the sake of contradiction that there exists an Oracle that solves the halting problem as stated before computer programs are really one big number which means that the amount of all programs is countably infinite so we can list out all of the possible programs we can then create a grid by using all the possible input programs each program when run on each input will either loop or halt for example maybe program a loops when run on a halts when run on B loops will run on C etc maybe program B halts on all inputs let's take this list as an example of what each program might do when run on each input now we create a new row by taking each element off the diagonal and flipping halt to loop and loop to halt where does this new row appear on the list by the diagonal argument it can't appear anywhere on this list since it's different from every row in at least one place since the list is a complete list of all computer programs that means that we can never write a program that matches the new row that we generated on all inputs however if we had the magical Oracle that could solve the halting problem it would be pretty easy to make the program that matches this row in fact that's what we did with mr. Smith if you notice what mr. Smith does it looks at what a does when run on itself and then does the opposite the same for B C and every other program that we could write since we know that mr. Smith can't actually exist it must mean that the magical Oracle also can't exist the undecidability of the halting problem is interesting in and of itself but was also integral to the history and development of computation as well as the nature of computation this proof first appeared in Alan Turing's landmark paper on computable numbers with an application to the ink sytems problem where he created Turing machines which formed the basis of what computers are today these undecidable problems may show fundamental limitations in computation but Turing also demonstrated the universality of his machines in the appendix of the same paper that work continued into what is now called the church-turing thesis which says that all models of computation are the same as Turing machines if you had any doubt as to how powerful Turing machines really can be just take a good look forward or in your pocket computers may not be able to solve the halting problem but they sure can do a lot

Channel: Undefined Behavior

Views: 158,380

Keywords: halting problem, diagonalization, diagonalisation, diagonal argument, turing, turing machine, proof by contradiction, infinity, undefined behavior, Entscheidungsproblem, computer science, programming, computer program, computer, the halting problem, undecidable, alan turing, cantor, algorithm

Id: wGLQiHXHWNk

Length: 6min 50sec (410 seconds)

Published: Mon Nov 14 2016