Turing & The Halting Problem - Computerphile

Deepest V neck of all time.

I think some people who aren't understanding the problem. The problem isn't "Can I write a program that will halt every time I run it?" or "Can I determine if my specific program X comes to a halt?" (trivial examples are easy to come by). The question people were considering at the time was, "If we could create Turing machines (you can read "computer" for "Turing Machine" in most senses) which accept an input and give an output, will they be able to solve any problem put them, or will there be problems which the machine will not be able to solve?" It needs to be understood that if your hypothesis is that "ALL problems given to the Turing Machine can be solved by the Turing Machine", then to disprove this hypothesis, you only have to come up with ONE counterexample. To demonstrate that there are SOME problems that a Turing Machine will not be able to solve, he created the halting problem. Somewhat trivial examples are being used to demonstrate that a contradiction occurs and the program would never halt (and therefore never return an answer to the problem), but the halting problem is a specific problem that cannot be solved. Basically, the point is that for the halting problem, for any given halting program of any complexity, an input can always be devised such that you can cause a halting program to eat itself and go into an infinite loop. As you only need one counter-example to prove that a Turing Machine cannot solve ALL problems, this is considered a proof that there are limitations to what can be proven in any formalized system, such as a Turing Machine, or as with Gödel's Theorem, arithmetic with natural numbers.

I think there's a little misunderstanding here, the Halting problem asks if there can be ONE GENERAL algorithm that can ALWAYS decide if a program A (whatever it may be), given an input B (whatever it ma be), will terminate or not. Turing, and this demonstration, show that such an algorithm cannot exist, because there is at least ONE CASE when such a program would not give you any answer. In other words: such an algorithm cannot exist because there is one particular case that we can make up when it does not work, and that case we can make up is not a logical fallacy. On a closing note: there are a lot of comments about Zeno's paradox. Zeno's paradox is not really a paradox, in the sense that we can solve it (not by simply observe of the phenomenon). We can logically demonstrate that an infinite sum of numbers can give you a finite answer.

I did a depth-first search on this page, it returned his V-neck.

2:38 when he said "Think about your computer running", my network froze and started buffering the video!! Thought it was some kind of joke!! Computerphile never fails to make me smirk

What's also interesting is if you could build an "oracle" (ie a machine that solves the halting problem), you could use it to immediately solve many unsolved mathematical problems, such as the Goldbach conjecture or the Twin Prime conjecture. Simply make a program that starts looping integers and halts if it finds an integer where the conjecture doesn't hold. Normally doing this would be useless since you'd have to run it forever, but if you had an oracle you could simply input into the oracle and it'd immediately tell you if it ever halted and if it did, conjecture is false; otherwise it's true.

What if it simultaneously halts and doesn't halt until it is observed?

What would happen if pinocchio said: My nose will grow

I love how there's tea and cups behind him :D

I have noticed, as both a computer scientist and amateur mathematician, that logical systems seem to break down quite readily when we allow self reference. Case in point, the Incompleteness theorem

H+ instead of H'. I'm concerned

When someone asks whether h+ halts or not: Well yes, but actually, no.

As a child I always thought about something someone once told me. They asked me what would happen if Pinocchio said: "this statement is a lie". Would his nose grow? Pinocchio's nose is a decision machine: given the input (something Pinocchio says), is the statement a lie? Yes, (nose grows), no (nose stays the same). I had no idea that this conundrum is exactly what Turing saw in the decision problem. Turing was a goddamn brainy bastard.

When H+ is fed back in (to the H+) as the program to which we give input H+, there aren't enough inputs (for that H+) as it needs two inputs to give the answer (halting or not halting) and its only receiving one - previously called i.

Yes exactly. He is purposefully doing something to reach a contradiction, and that's fine. Why? Think of it like this. We want to prove H does not exist, but we're having a hard time doing that, so we assume it DOES exist. Using H, it is very easy and possible to construct H+ as they said in the video. So far we know, if H exists, then H+ exists. Agree? Continue reading if you do. Now using H+ we arrived at the contradiction, showing that H+ cannot exist. But how is that if we showed how to make H+ using H in a valid logical way? That must mean our original assumption was incorrect, in that H can indeed not exist. Hope that made things clearer.

After listening to this, my brain halted :P

Turing is a true genius. I read a bit about him in Simon Singh's Code Books. I hope the movie with Benedict Cumberbatch will represent him in a good way.

Turing didn't invent a computer program to demonstrate that a particular something was impossible, he invented the entire idea of computers and programs for the purpose of showing that this something was impossible. Think about that for a moment.

Thank you so much for this video! I was starting to worry I wasn't every going to get this and with an assignment deadline dawning I was dreading having to send it in knowing that it was going to be wrong. The way you have described it has made it very clear to me.

Can't remember the last time i was confused this much.But your explanation is better than the other guys so cheers!