The Halting Problem - An Impossible Problem to Solve

This episode is supported by SkillShare. There are some problems computers just can't solve. Computer, what is the meaning of life? Will I ever stopped being a disappointment to my family? Who do you think would win between a platypus and a wombat? But today I wanted to talk about one problem in particular called the halting problem. It's a really cool piece of computer science and I think the most interesting thing about it was actually the way it was answered, but before we get into that let's talk about how it came about. See in 1928 the mathematician David Hilbert (who even has his own space named after him) challenged the mathematics community with three questions especially close to his heart. Number one: is mathematics complete? Can we prove everything that's true? Number two: is mathematics consistent? Does it give us non contradictory answers? And number three: is mathematics decidable? Meaning for every mathematical problem is there some kind of step-by-step method we can take that will tell us whether a statement is true or not? Hilbert was an optimist and thought all questions would be answered with a resounding yes! As he famously put it, "In mathematics there is no ignorabimus", roughly translating to, "there is no 'we cannot know'". It was Hilbert's third question which got a young mathematician Alan Turing thinking about another seemingly different problem. He wondered, "Can we write a program to tell us whether any other program will halt or run forever?". This is now known as the halting problem and to understand it properly we first need to talk about programs and inputs. A program is just a sequence of instructions written in a language that a computer can understand, for example for the question "given two values x and y, does x evenly divide y?" we can write a program that takes y and divides it by x. If the remainder is 0 the program returns a "yes" if the remainder is anything else it returns a "no". But the question does x evenly divide y doesn't make any sense unless we give it some values for x and y. These are called the inputs and programs will behave differently given different inputs. Some more complicated programs can even have other programs as inputs, and some can even have themselves as inputs! Now that we've gotten that out of the way we're ready to talk about the halting problem. So first let me tell you why this is such a big deal. There's a famous question in mathematics called the Goldbach Conjecture and it goes: can every even number greater than 2 be written as the sum of two primes? Although every even number we've ever encountered is the sum of two primes we haven't come up with a way to prove it. We've kind of just brute forced it. That's why even though it's probably true it's still considered a conjecture. But what if we wrote a computer program that went through all the even numbers and ran an algorithm that checked all the different ways to write this number as two positive whole numbers, x plus y? When it finds two primes it moves on to the next even number. If it fails to find a prime value for x and y it stops and prints out this message. If this program ever stopped we know that it had found an even number that wasn't the sum of two primes so the Goldbach conjecture would be proven wrong! But how long do we let it run before we decide it's been enough? A year? A million? The age of the universe? If we could write a program that could tell us whether this program ever halted we could solve the Goldbach Conjecture and many others like it. That's why the halting problem is so important. Can we find a program that can predict whether any other program and its input will halt or run forever? Turing answered this in a really interesting way. He first imagined that such a program does exist. Let's call it Hal. Hal claims he is capable of saying whether any other program in its input will halt or run forever, but what if we built another program, Barrie, who does the opposite of what Hal predicts. So if Hal outputs "halts", Barrie runs forever, and if Hal outputs "runs forever", Barrie halts. Seems simple enough. So let's see what happens when Barrie is given a random program, Randy, as input. Barrie does the opposite of Hal so he first needs to know what Hal would say about Randy. Does he halt to run forever? So he runs Hal with program and input Randy. If Hal returns "Randy halts", then Barrie runs forever, and his Hal returns "Randy runs forever", Barrie halts. So far so good. Now the genius thing that Turing did was ask Barrie to use itself as input. So just like before he needs to look at what Hal would say so he can do the opposite. He runs Hal with program and input Barrie and if Hal returns "Barrie halts", then Barrie will run forever, and if Hal returns "Barrie runs forever" he'll halt! If Barrie halts Barrie runs forever and if Barrie runs forever Barrie halts. What?! We've reached an impossible contradiction! Barrie can't both run and halt forever, so Hal can't exist! It was by this way of contradiction that Turing proved that the halting problem is impossible. We can't write a program that will tell us whether any other program will halt. In the same paper Turing also managed to answer Hilbert's third question, that no, mathematic is undecidable. There are some problems that we simply can't solve. The philosophical implications of this are pretty interesting. The human brain has often been compared to a computer and actually when Turing wrote his paper he didn't even have machines in mind. He was thinking of the people that carry out computations with pen and paper. If the human mind is just a complicated program that means there are problems we fundamentally can't solve. Not because of limitations of technology and time, but because the halting problem says so. This video focused mainly on the theory of computation but if you'd like to complement that with the more practical side of things SkillShare.com has loads of classes to teach you programming. You can learn a variety of different programming languages like Python, Java and C++. Even if you've never programmed before and you have no idea what any of those words meant SkillShare is very beginner friendly giving step-by-step instructions from installation to more advanced aspects of coding like data visualization and GPU programming. But if programming is not really your thing Skillshare still has plenty of classes for you to explore like this one on how to make french macaroons. Skillshare is offering a promotion to my viewers where you can get the first two months totally free. Just sign up using this link on screen and in the description. Just quickly before you go one of my viewers from the University of Aahrus Denmark has created this game where you can try and solve the same kind of problems as quantum computers. I know it sounds hard but it's really fun and the data will help scientists study the differences between the way we solve problems compared to the way a quantum computer would. It's a good cause and all you have to do is play a game. Links are in the description. Thanks for sticking with me to the end here guys I really appreciate it. I hope you enjoyed the video and I'll see you next week. Bye!

Channel: Up and Atom

Views: 249,901

Keywords: halting problem, the halting problem, computer science, university of nottingham, halting problem explained, the halting problem of turing machine, halting problem proof, turing halting problem, up and atom, turing test, turing machine, alan turing, turing halting theorem, turing halting problem video, what is the halting problem, theory of computation, turing problem, halt machine, goldbach conjecture, fix, proof by contradiction, turing, computerphile, computers, logic

Id: t37GQgUPa6k

Length: 7min 36sec (456 seconds)

Published: Fri Jul 20 2018