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.
Why is it specific to halting? Can't one use the same trick on say return or output value? "Oracle said I'll return x. So I'll return x+1". What's so specially about "halting"?
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.
Best explanation! yes, the whole point people, it to show that it cannot exist, since there is going to be at least one case where it does not work properly, meaning it's not perfect and cannot detect HALT. Which means no machine can exist that does it.
But you see that the contradictory machine itself is bogus? You can't really determine the 2 outputs. Looping forever and stopping at some point in the future are not different. Because the stopping could take place in billions of years. If you fed the program into it, you would never be able to determine whether it loops or stops.
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.
Nice! Yes for Goldbach's, but not for twin primes. You can't write a program that checks if integer has no twin primes after it without checking all primes bigger than it so it will loop forever whether twin prime conjecture is true or not.
@@rupen42 no this isn’t a machine you can actual use or build the same way you could a TM. In essence, oracle machines provide a way of comparing harder problems to each to see if they are in the same class. While this machine could “solve” the halting problem for Turing Machines, there now introduces a halting problem for Oracle Machines which is basically just as hard as the regular halting problem if not “harder”
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
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.
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.
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.
I'm also not sure I really understand how we're proving anything either. The paradox described feels like it implies that that having this specific input ran through the machine would result in looping, but we can't know if that would even be the case? The question was never about whether H+ could exist but whether H could exist. Is it because H is a product of H+ that it implies failure? I don't think it is valid to say 'your machine with 100% success rate in deducing if carrots are peeled or not is foiled because I added extra machines at the end of it that peels the carrot if it is deemed peeled'.
That can easily be solved by turning the input of H and H+ into a single input that describes both the turing machine and its own input to be tested. That way everything is receiving the correct number of inputs and the paradox still happens.
@@Outwardpd You see, the problem is that your peeled-carrots-detector example does not create a paradox, so there's no problem. A proof by contradiction starts out assuming something that you don't know is true (or exists) is (or does). Then it shows that, if that is true, than something completly absurd and impossible would also be true, automatically. Therefore, what you assumed to be true cannot be, in any way, shape or form. The halting problem assumes a turing machine that solves it exists. Then, using some simple steps, creates a set of inputs that makes it not work. Therefore it couldn't exist, at least not as described. There's no program that can determine if any problem halts, because we just showed how to create a program that wouldn't work, using itself. A contradiction. Contradictions cannot be true, so your assumption can't be either. Basically if A, then B. If B then not A. Therefore, A can't be true.
Think of H+ as a program. It's a program that takes _any_ program as input, determines if that program halts, and then gives an output in the form of halting (if the input loops forever), or looping forever (if the input halts). In order for H+ to exist, then it must also be able to take H+ as an input, determine if H+ halts or not, and output accordingly. Remember we must assume that H+ is solvable, and therefore must output either by halting or looping forever. So let's say that H+ halts. If we give H+ as input to H+, the machine determines that it halts, and then loops forever. Vice versa applies too, so let's say H+ loops forever. If we give H+ as input to H+, the machine determines that it loops forever and then halts. This is the contradiction - the machine gives contradictory outputs for itself. This contradiction means that the assumption was wrong, meaning that there _cannot_ possibly exist such a program that can take _any_ program as input and then determine whether or not it halts.
I cant seem to understand the part "If we give H+ ad input to H+, the machine determines that it halts, and then loops forever." Why does it loop on forever after determining that it holds? Why doesnt it just determine that it halts and then halts?
@@paulvorderegger1522 It loops forever because that's what H+ has been designed to do. If you feed it a program that halts, then it will loop forever. If it did anything else, then it wouldn't be H+. If you gave H+ an input program that halts, and H+ cannot loop forever, then this would also imply that H+ can't exist.
@@gordonfreeman5958 Ok I finally understood this after seeing the following pseudo code: def thisFunction ( ): if halts(thisFunction): loop_forever( );
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
@MrBigbanan imagine you are trying to actually learn something and you ask a very hard question to your computer. If it "runs forever" you will never be sure that its a no, maybe its just slow and it will eventually say yes. And you cannot ask another computer to tell you if it will run forever...
there is not really any self referencing here, H+ is defined without H+, same for H. Imagine H+ is some actual .exe file that needs a file as an input, you are allowed in the real world to give the .exe file to your .exe program.
What makes the 'machine looping forever when reaching a yes' upgrade count as being relevant to the original question? Is it because the machine is suppose to account for all programs in a form of universal sets, including the added upgrade?
He proves asking that type of question about anything is absurd. look up Proof By Contradiction. He says that if it WERE possible, something else would happen that we know to be false. and since the rest of his arguments are valid, the premise must be absurd.
@@ximbabwe0228I understand that it doesn’t matter in the end, but this unexplained noise is so jarring. If it doesn’t matter if it halts or not, when the answer of the machine h was an “yes”, then it’ll be far nicer if he just said “this doesn’t matter in the end but let’s say it just doesn’t halt, just loops.” rather than just giving me the definition as if it’s logically meaningful role. My wrong assumption was that the output supposed to try to give an answer to the original problem because the no leading to halt sounds like an intuitive upgrade to give an answer to the original problem.
in the final example we are feeding H+[1] the input "H+[2] evaluating input [H+3]", however, h+ needs both the program and it's input to determine if it's going to halt. what is the input into H+[3]?
i watched 2 videos so far , inclusing this , still dont understand the halting problem because , why would you put and loop when it give a yes answer ? it it halts let it just halts and its done ? why forcing it loop ?
4:42 but doesnt H+ expect two inputs? the description of H+ is "given the following input, will this code half or not" so when we give H+ itself as the "input" input, we need to actually give it something else, because the H+ in the "code" input expects two inputs?? i hope this makes sense
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.
***** if it would not grow then he must have said the truth. The sentence "This statement is a lie" must be true. But then if he said a lie his nose should have grown.
No, his nose only grows when he lies; you can say something that is neither a lie nor a truth. For example, I could say "Zerg is the best race" and, as it would be an opinion, it cannot be true or false.
***** I understand what you mean; please consider that I don't deal with coding or computer programming at all. I see that the output (the nose growing) depends on the fact what is correct (true) or not. The problem comes when you use the statement as the argument of the statement itself. So when the statement is true, then "This statement is a lie" is true, which means actually the statement is a lie, but if he said a lie, then "This statement is a lie" is not a lie, which means he said the truth... You see? The process never ends.
+BroadcastBro Think I got it... I couldn't understand why they were reversing the output. But could you possibly explain with the example of H+? Because if you feed H+ into itself, well H+ cannot solve H+ right? Which makes it a No, which halts the machine. So that stops it. Which means H inside H+ was right.
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.
I can design a program to determine whether a closed loop program (I.e. one that doesn't have any inputs) repeats forever. It executes that program and examines the memory allocated to it, and as soon as it sees a repetition in the memory, it terminates that program and outputs yes, that program repeats forever. It avoids the halting problem because it requires an input, rendering it incompatible as an input.
Error: H+ cannot be converted to type Input for parameter 'i' at line 4:40. H+ is a program, not a program and input pair, which is the input required for H+ p.
I saw a comment who fixed that error by letting H+ have a single input P and send to H and of course do the if halt loop and if loop halt at the end. When it is done like this, if you give H+ the single input H+ you'll find that if H+ halts on H+, H will have determined H+ shouldn't have halted in the process, and if H+ doesn't halt on H+, H will have determined H+ should halt on H+ during that process.
The comment didn't bring up this, but I realize that not all programs can accept themselves as inputs. I imagine we can also extend H such that no will be the answer if the input is not allowed (because it should halt with an error)
*****: 1. Regarding the multiple simultaneous clips at the end, have you though of using a black 50% alpha mask to subdue the clips whose audio is muted? It might increase the visual appeal of those clips sections. 2. What are the applications that you use to create the phosphor green animations? I don't care so much about the color, of course, but the animations are quite well done and I'm curious about the tools.
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.
That confused me too, because the video glosses over technicalities. But I realised it looks like this: bool h(alg, param) { if(halt(alg, param)) { return true; } else { return false; } } void h_plus(input) { if (h(input, input)) { while(true) ; } else { return; } } i.e. h_plus() has a single input which it duplicates when it calls h().
@@TheCriticsAreRaving but what paramilitaries will the program have ? If h processes h+ which has different parameters than the h+ which is processing wouldn't that make it so that h+es are different thus they wouldn't do the same thing . so if it loops it isn't a contradiction anymore because it is processing different parameters
@@sababugs1125 no there is no problem here h_plus simply uses h as black box. h should work for all inputs including once tha have the first and second argument the same.
@@sababugs1125 i mean in his algorithm when you pass h_plus(h_plus) you get: h_plus(h_plus)=>h(p_plus,h_plus)=>h_plus(h_plus) => ... basically its an infinite loop, but tho you have no idea what h does, as h might "look into the future" without actually running h_plus on h_plus return some answer. but then no matter what h will say it is always wrong.
4:22 Here, the H+ machine has two objects as input. So when (H+, H+) is fed as an input to H+, the input first goes through the machine H. The machine H answers the question of "Does the machine H+, when given H+ as an input, ever halt?". My confusion is in this question itself. How can the machine H+ accept just one object as input? It's designed to accept two, right?
I have a question!! When I took Philosophy courses years ago, I was taught that adding self-assumed premises to the given question is not allowed. I have watched a few explanatory videos regarding Halting Problem on RUclips, and all of them involves adding extra logic gates or machine components on the original "machine H." Isn't this kind of like adding self-assumed premise to the original question, since the original questions is about whether Machine H will halt, not Machine H+?
This is because the proof is very simplified. The original proof (not going into details) was like: i have an algorithm h wich will decide whether an algorithm x will stop. Then we put ALL possible Algorithms combined with all possible input in a numbered map (each column/row has a unique number). You can now choose algorithms and inputs (e.g. algorithm number 4 with the input 10). We can some really crazy math with an alter every row, EVERY row from 0 to infinity is still unique, but now you have a new row with instructions not found in the table. You can define this row as the algorithm h+ (uses h) (actually the algorithm used is different from h+, but for a simple explanation you have to change it) and if you feed the algorithm with an input z (z is the number for the input), it will print out a different result that the algorithm in the row z for the input z. Since you have this cool table with every possible algorithm, you can find the algorithm h+ with a number x. But you proved that h+ will give you a different result than algorithm z for the input z and input x must exist. So h+ must print a different result for the input x than algorithm x (which is h+) for the input x? This is a contradiction! But this case MUST (this is the big point) exist if our assumption is true. the problem is that the proof is extremely fundamental and very, very important, but also very hard to explain or understand. I altered the proof heavily. To explain it in a simple way you have to make a sacrifice, and you spotted a consequence of one sacrifice.
LeanderK Your explanation makes much more sense than the video to me, thank you. However, in the video I can't quite grasp why the loop and halt extra boxes should be added to the outputs, because if that's the case wouldn't the h+ that is being used as an input not halt at all? And if loop is added when output is yes, then halt is added when output is no, then why bother feeding h+ into itself? Pretty much all machine as an input will get the contradiction because we set the h+ like so. I don't really understand philosophy and proper logic, so please enlighten me :D
Dennis Samuel "All algorithms" would by definition include a modified original algorithm. A modified (as described in the proof) algorithm is part of the set that includes all algorithms.
Gran Cero No because the problem is respect to ALL machines. adding stuff onto an existing machine only creates a new machine which also has to obey the assumption proposed.
For people in comment that want an example of a really simple algorithm yet very hard to tell if it will finish or not is Collatz conjecture. It goes like given an input x if it is odd triple it and add 1, and if it is even, half it. Keep doing it until you reach 1. Fun fact is that there is no way to tell how many steps it will take for any X without carrying out the algorithm. NOTE this has nothing to do with the halting problem. This is just a fun contrast to other common algorithms which we can easily tell if they would halt just by inspecting them.
Question H+ named 0 H+ named 1 H+ named 2 0 runs, checking whether 1 will halt or not halt if 1 is given 2. Wouldn't there be an error, since 1 is only being given one input, rather than two which it is designed to take, and 2 is not being given any inputs at all?
***** So H++ named 0 H++ named 1 Virtual H++ named 2 Virtual H++ named 3 Virtual H+ named 4 0 runs, taking 1. 4 takes 2 and 3 as inputs. 2 runs with 3 as input. 3 still lacks the one input it needs to run. Wouldn't there still be an error?
***** You're missing the point, because the paradox would still be encountered within your H+ machine. It doesn't matter at all what the inputs are - the paradox will still arise. Or do you actually think you've figured out something in a youtube comment that mathematicians have missed for the better part of a century?
No, I'm just confused. I don't think that the proof is wrong or that I'm particularly more intelligent than anyone else, quite the opposite, I don't understand the explanation, and am attempting to identify where my misunderstanding is coming from. Is it necessary to take such an aggressive stance?
Was actually responding to SBareSSomErMig and eir fairly flippant 'That's a little mistake in this video' comment. The video's fine, eir logic is faulty. You're good for asking questions. :) The system is designed so that the entire machine is fed back into itself as both inputs, not just one. So the system has the correct initial inputs, but will still result in a paradox as explained in the video.
I think this explanation is wrong because H+ with two H+' as imput is different from H+ with one or zero H+' as imput so the second one can halt while the first can loop and there wouldn't be any paradox. Correct me if I'm wrong.
Either I didn't get the Halting Problem in university or Mark describes it incorrectly. He says at 03:35 "...whether a given machine with a given input will halt or not." Shouldn't it be "any machine with any input", any as in an arbitrary? Because surely you can built a machine that can determine the Halting Problem for "some" machine with "some" input, but the point is you can't do it for every/any/arbitrary machine. Or maybe I just got lost in translation? (I'm not a native english speaker)
His description is ok because he doesn't claim you that this program is in some kind of set, he's saying "given program" which actually means that this program could be any program. The same goes with inputs
A minor problem, the description actually given won't create the paradox. H+ needs a front end as well as a back end. What you have in your example is that you are feeding H+(H+) to H and asking if it halts and finding that H+(H+(H+)) exhibits opposite behavior, which may be unusual bot not impossible.the fron end needs to do a small conversion so that x(y) is changed to x(y(y)). This is actually an important consideration. Languages which cannot expand their inputs are always decidable. But expanding the inputs allows the creation of self-denying statements.
I think it is a little confusing when you feed H+ to itself, H+ should be fed to H. H is the machine that you assumed will solve the problem. If you end up in a paradox on your assumption then the assumption will be falsified. By feeding H+ to H+ nothing will happen to the original assumption, because you basically are not touching H. If you feed H+ to H, then if H+ halts, H will say it doesn't and if H+ doesn't halt, H will say it does. Here is the contradiction so the assumption is incorrect.
The problem isn't really feeding H+ into H+, but there is a problem with the explanation. I don't know how exactly Turing wrote his proof since I didn't read his paper, but the way every single youtube channel is explaining it is simply wrong. The input to H+ is a tuple (P: Program, i: InputToProgramP). The whole thing is the input So when you feed H+ an input (P=H+, i=H+), you are basically asking "does program H+ halt when it receives input H+?". The problem is, the input to H+ is a pair (P, i). So you can't just feed it P, you are missing i. It's like you are feeding it (P=H+, i=). To fix that, you'd have to feed H+ an input (P=H+, i=(P=H+, i=H+)). But you end up with the same issue. So you'd change the input to be (P=H+, i=(P=H+, i=(P=H+, i=H+))) to try to fix it, and so on, forever. You can't ever feed it itself.
@@rafaelclpTHANK YOU, I WAS THINKING THE EXACT SAME. You formullated that pretty damn well and I fully agree with you. Im just wondering wether or not you can still prove it by induction, but i dont think there is even a base case, so not sure about that
Sorry if it's been asked/answered before but I'm confused. Why must a 'yes' answer result in a loop? Why doesn't it just stop? And why not permit the 'No' answer to loop?
I've always sort of understood this as a more general proof that any algorithm which analyzes algorithms can never be fully generalizable. If it could, then it could analyze itself and respond to the result by contradicting that result.
+Computerphile At 3:58, Mr. Jago says that the blackbox will output "Yes" if the program halts, but "No" if the program never halts (a.k.a loops forever). But how does the program know that it will loop forever, since with every iterating loop it has the potential to halt? - An Engineering Physics student, and Physics student in California
5:18 Aren't you just asking the wrong question? "Does the first iteration of H+ Halt?" would be a better one... Also, doesn't that mean the machine could be the human brain...so...we couldn't do this? Yet...we can? Also, how does that fact that putting H+ into H+ break means that H normal can't solve it?
I'm a little bit confused, Jago started by talking about a very vague premise-conclusion problem and he wound up only proving that a halting machine could not exist. What relation does this have to premises/conclusions?
Why is the transformation from h to h+ valid? Isn't h the one machine that solves the problem? What would happen if you give h+, h+ inputs to another h machine?
I'm not saying you cannot make h+. I'm asking why can you expect it to solve the same problem that h can. It just sort of feels like attaching a shredder to a printer and saying printers can't exist. I'm not really program-savvy but I'd like to understand and not just take somebody's word for it...
OK I see what you mean. You're completely right that H+ doesn't do the same thing as H. But it doesn't need to. The idea is, if H is valid, then H+ should also do *something* reasonable. It doesn't matter what that something is, but at the very least it shouldn't result in a living contradiction. With your printer analogy, imagine if you attached a shredder to a printer and got confetti that is both all black and all white at the same time. It's a contradiction, and you know your shredder can't be responsible. So something must be wrong with the printer.
'p' never changes in type, it's always some kind of program. However, 'i' the input, can change. eg you make a program p that multiplies a number you give it by 2, then you test it with the h machine, and you can check whether p will halt or not given input of type integer, then string, or even of input program or 'p' (feed it some Java or something eh?) you see what I'm getting at here?
I appreciate what you are saying but your answer doesn't solve the formal problem I am posing. If you want to feed H+ as the 'p' to H+ you need to formulate it correctly as a program/machine that takes an input. Now, H+ must be viewed as a machine that takes a pair (p, i) as input. So the final test would be with H+ and (p,i) fed into H+.
what's the difference between a formal problem and an informal one? ^_^ Anyway, when you approach this theoretical machine thinking like that, you quickly end up with infinite recursion, can you see how? besides it defeats the simplicity of the system to start worrying about data types, when you get onto larger programs, you expect this machine to be formatted to take all 1000 of the programs variables and inputs as the 'i'? if anything like this could ever be made, the team behind it would be smart enough to ensure it only ever needed two inputs, P and i, because there's zero upside to any other approach, wouldn't you agree?
Well formally, everything is just numbers. There is a 1:1 mapping between programs and numbers, for example by taking the program's code in binary and reading out the whole sequence as a single number. So it's perfectly valid to use the same number as both a program and as an input to a program.
I feel like I finally began to understand some of these issues after spending way too much time on it. Basically the idea is that whether the input type is valid or not the program still runs with that input. For example, if you built a rudimentary calculator and then you feed it a string input, if your program isn't able to handle that string input it can either throw and error and stop (halt) or it can loop infinitely due to invalid input (loop forever). So the input types don't necessarily matter because a program will still result one of those two actions, and when you're feeding a program/algorithm as the input itself to be analyzed by the program it will still do either of those two actions, regardless of whether it is a valid type.
What if the computer holds an oscillating program, giving equal times yes and no to our halting query in its N1th run and feed that answer back into the computer, hence modulating N+1th to the oscillating signal with the time needed from input to process to the output. Wouldn't then the modulating frequency in relation to the ever diminishing signal modulation and it's ratio be a solution solving the contradiction's to it, answering a halt state?
I thought I had addressed this before but I could find my response. The Halting problem paradox (at least as described here) is wrong. It's impossible for H+ to self reference since it requires 2 inputs (the 2nd being in input to the machine to test) but this requires infinite recursion to set up to self reference even if you fix H+ to take multiple required inputs as a series (or by any other method) into the 2nd slot.
burstofsanity late to the party, but fwiw you don’t need this problematic self-reference: the “computer” input I.e. the “top” input, is just a representation of the program, like its source code (or Gödel number), not its state with respect to a given input.
I'm not clear on how the behavior of H+ shows anything about the behavior of H. The two machines are not the same, so why would you expect the same (i.e. correct) output. By this logic I can ask whether it is possible to build a vehicle that can move down a road. Suppose there is such a vehicle, let's call it CAR. CAR can't possibly exist because I can attach a module called NOGAS that removes its motive force, so it can't go down the road. Since CAR+ can't go down the road, no such vehicle can exist. QED. If you're going to add parts that break things, why pretend that you're still dealing with the same program?
+Jason Patterson Yep there is no such vehicle CAR+, that can drive because CAR+ = CAR + NOGAS. There is no fuel powered car that can drive without fuel.
The missing part from your example is a contradiction. CAR+ can't go down the road while CAR can, and that's it. If you somehow reached a contradiction using CAR+, then indeed CAR could not exist. Both CAR and CAR+ can exist here fine. What happened in the proof in the video is that using H, he constructed H+, and showed that H+ is impossible to exist. So essentially we've arrived at two conclusions at the same time, H+ can exist using H, but at the same time H+ can't exist from the way he described in the video. That's a contradiction, so the assumption that H exists was wrong. Hope that made things clearer.
@@Kalernor Does not make sense "using H, he constructed H+, and showed that H+". Meaning it is possible to put anything as an addition to H, and then say:"look, just because I added some impossible things to H+ it means that H, my base, is also impossible.".
Pardon me for so saying, but it appears that: This entire presentation (and argument) is itself a general algorithm that in fact does decide a whether a program will always terminate or not. This presentation demonstrates an answer to the presented dilemma. Given the recursive, self-referential nature of the proof presented, I think it only fair to consider the proof itself as part of an algorithm that does in fact solve the issue at hand, thus this ONE CASE presented actually shows that there is an answer. After all, you've given the answer in the form of a proof, no less! If you consider your own thoughts as part of the algorithm inside the "machine" then you are the solution, since you can ALWAYS decide if a program will terminate (by recognizing an apparent paradox).
"The Halting Problem" is a problem specifically for Turing Machines, or any other equivalent formal system (first order logic, the lamda calculus, etc.). Once you step outside those systems, "The Halting Problem" is not defined.
I am at a loss as to how you can give an arbitrary function an arbitrary number of inputs of arbitrary class. Many programs run without taking input, so how does that work? E.g. int main(){ int x(5); return x; } What does it mean to give this program itself as input?
4:30 About feeding H+ into H+: Since H+ requires 2 inputs, this would require a recursively defined input, right? p = H+ and i = (p, i) Edit: Ok, many people commented this already, of course. :-D
is time the missing factor in the halting problem ? if it were to time out then the halting problem is solved ? maybe 555 timers were newer back then or it would be harder to limit the amount of operations per program.
I keep looking through proofs of this, but I am a little confused; it almost seems arbitrary that we say that if program P does halt on a given input of I, then we loop forever. Why would we assign "loop forever" to the output of yes ("it does halt")? If such a program could deduce that we halted, why would it then need to loop forever? Would it not just halt after producing the answer?
The following 3 lines will clear things up: def thisFunction ( ): if halts(thisFunction): loop_forever( ); Now, if halts says "thisFunction" will halt, then "thisFunction" will start looping forever, therefore the answer was wrong
But H+ is constructed using H. Maybe let me refine Kot_Robot's comment: Maybe there can be a Turing machine S that solves the halting problem for all programs except those that reference a Turing machine capable of solving the halting problem to the extend in which S itself is capable of solving the halting problem. I intuitively think self-reference is key to both the logical contradiction ( like the liar's paradox aka. "this statement is false" ) as well as to the way to solve it ( think through the Turing machine S I constructed up there ).
@@greencoder1594 Sorry to disappoint you, but that is not possible. This is a really simplified version of the proof and i understand that it may hold this implication if you aren´t invested in theoretical computer science (formally it´s usually prooven via diagonalization, which is much less intuitive). It actually turns out that even the BTHP is undecidable (blank tape halting problem -> given a turing machine M, does M halt on an empty input?).
Doesn't this proof just show that the transformation from H to H+ was a bad decision? I mean, theoretically I could use H to test H+ and see if it will halt or not. I don't necessarily have to use H+ to test H+, right? Can someone please explain this to me?
When proving something by contradiction, you start from an initial assumption (which you want to prove wrong) and then reason upon it until you arrive at a contradiction. Since all the reasoning steps between the assumption and the contradiction are legal (consistent), the only possible explanation for the contradiction is that the assumption was wrong - so the opposite must be true. The wrong assumption here is "there exists a machine H which solves the halting problem", and we use a "bad decision" (a legal transformation from H to H+ and a legal execution of H+ on itself) to end up with a contradiction. This proves that the opposite is true, so we conclude "there is no machine that solves the halting problem". Sure, running H on input H+ might not lead to a contradiction, but that simply means it's not useful as part of the proof. The goal is to make the "right" bad decisions in order to end up with a contradiction.
The strategy in the proof is to show that if such a working H machine exists, then we can build a machine H+ that contradicts its own existence. Since you can never build such an H+ machine in any way, then it must be impossible to build the H machine to begin with.
You've only disproved machines which are limited by the two inputs and one output as unable to solve the halthing problem. What if your halter determiner machine was able to take in more information than that? Such as, "Am I part of a larger machine?", or any other relevant information necessary to solve the problem?
The mistake in this video is that the box in the machine asks, does program p with input i halt? However you cannot feed in H+ to this machine because H+ takes 2 inputs instead of 1. You could fix this by adding a new component to the front of H+ that only takes 1 input and copies it into 2 for the inner machine. Now H+ takes only one input and the argument works just as explained.
Does it matter what input you give to H+? in the example you provide H+ with itself and itself again. But is it just as valid to provide H+ with itself and any other input?
Looking at this from a programmers perspective, if we add an additional parameter say T and T represents a given Time unit. What if we assign T to H and if T exceeds some Upper limit say 24 hours. We can say that this program is not computable, and if the program computes in a time Under T we can say that is computable. I understand in terms of Logic, this is not a True, because Time is conceptual and a program could theoretically run for longer than 24hours and yet we cannot determine if it will Halt. However in a real world solution, would this be valid. Thanks for any answer.
there's a minor mistake in the presentation: the definition of H+ was "take inputs a program P and a set of inputs I. if H(p,i) then loop forever, otherwise halt". This simply doesn't work, you can't apply H+ to H+ and H+, since you're implying that H+ both takes 2 inputs and 1 input. The correct definition for H+ is "take a set of inputs i. if H(H+,i) then loop forever, otherwise halt" This way, H+ is a one-argument function (just the i), and you can apply H+ to itself to get the required contradictions.
From the description of H+ it would appear to me that it doesn't have an output at all. If it loops forever then it clearly does't have an output, but if it halts, it halts. From the diagram of the machine Mark drew, it doesn't seem that H+ should give any output when it halts.
Just to clarify: the logic here is that if your conclusion is paradoxical, then the premises are necessarily incorrect? Is that always true? Or is it just true for stuff that we can or can't design?
This is not the correct proof, as in the described system it is invalid to give the pair (H+, H+) as input to H+. Why? Because the second element of this pair is not a valid input to the first element. There's probably an additional assumption that would make this work, but its missing from the video, which drives people mad in the comments.
+poliklosio when we give H+ to H, we actually give a blueprint of H+, that specifies how exactly H+ works. that is, essentially, a bunch of characters, so you can look at it as an input to another machine, regardless of what the characters actually mean
+poliklosio All programs can take all inputs. This is a fundamental requirement from a program. If the input is invalid, or it can't process the input, the program either halts or not. But which is it? That's the million dollar question.
+Aman Singh I disagree. A program is not necessarily well defined for all inputs. There is no reason for every program to accept any-length stream of arbitrary bytes. Author of a program is free to describe any preconditions about the inputs to the program. If input data doesn't follow the preconditions, it doesn't make sense to consider behavior of the program in such case. It's like considering what happens when you divide by 0. The answer is the question itself is incorrectly formulated because division is not defined for this case. The program doesn't even have to have means to accept the bytes. How do you feed stuff to "Hello world!" program? Assuming it has the means to accept your bytes, of course you can try feed incorrect values to it, but it is not really interesting what happens in such case, as you are deliberately breaking laws of mathematics. The program doesn't even have to check for input correctness in order to be correct itself (although sometimes it may be desirable to do so). I have to make it clear again that the model you describe IS used in the original proof about the halting problem, its just that the video doesn't say it.
poliklosio Well, this is a video on Theoretical computer science, so it should be assumed, along with many more assumptions. For example, infinite tape of the Turing machine. This is the reason size or format of the input doesn't matter. The state machine of the Turing machine will either halt sometime or not, regardless of the "format" (using multiple tapes for writing any "special character") or size of the input (obviously, infinite tape).
I get the idea here, but it seems to me, once you've added on extra workings to the halt detector, it is no longer the halt detector, and has become a different machine. The example seems a bit off too, pretend this machine works, now we change it, it doesn't work, thus proving something about the world. Logic is a great tool, just the use perhaps in this situation isn't making sense to me.
"Can you build a machine, that can tell you whether or not ANY given machine with ANY given input will eventually halt?" No you can't, because you can always create a machine, that will never halt. (Overly simplified.) The key here is the created paradoxon, that if the machine should halt it doesn't and if it doesn't halt, it does.
The idea here is that if such a general purpose halt-detector H exists, then from it we can build the impossible machine H+. Since H+ is impossible, then H cannot possibly exist. Given H, H+ is the machine that takes as input a set A, and does the following with it: "what is the result of H applied to inputs H+ and A? If yes, then loop forever, otherwise, halt" now, to show that H+ is indeed an impossible machine, feed H+ to itself (that is, substitute H+ for A in the above sentence) this gives us "what is the result of H applied to inputs H+ and H+? if yes, then loop forever, otherwise, halt". We'll call this H+(H+) now, H+(H+) either halts or not. If it does halt, then it didn't loop forever. This means that H applied to inputs H+ and H+ gives us a "no" answer. Wait a minute, from the definition of H, this means that H+(H+) does not halt. This is a contradiction, which means we cannot assume that H+(H+) does halt. okay, so that doesn't work, this must mean that H+(H+) does not halt, right? Well, in that case, since H always halts, then H+ must have gotten stuck in the "loop forever" part. But in that case, then H applied to H+ and H+ gives us a "yes" answer. From the definition of H, this means that H+(H+) does halt. We got ourselves a contradiction again. We exhausted all possibilities of H+(H+) halting or not, and none make any sense. This means that H+ is an impossible machine to begin with. Since the way we modified H to make H+ is completely valid, then H must be impossible.
Ricardo Amendoeira Ah okay, with the modifications, it seemed to me something was wrong, as the add on part would be constantly flip flopping itself, just to fool the H part. Does bring up some interesting thoughts though, for it to work, H would have to be lying... and thinking ahead.
There are 3 machines: H, G and H+ H is the halt detector. The point is to figure out whether it can exist. G is a machine that loops infinitely if given the input "yes", but not if given the input no. We know that such a machine can exist. H+ is what you get when you combine them. If both H and G exist, then H+ must exist as well. This is equivalent to saying that if H+ doesn't exist, then H and G can't both exist. The video shows that H+ doesn't exist, so, as I said, either H or G must be impossible as well. However, we know that G can exist, meaning H (the initial halt detector) can't exist.
dork I understand all of this more pristinely than most people who have a degree in physics. I barely use the language of math. Your opinion doesn't matter.
But where did these extra bits come from at 4:10 to make H+? Is it just some counter example? You just tacked on some "negation computor" out of no where. Why?
Am i missing something here? So we assume that H solves the halting problem, and we then proceed to show a contradiction by showing that H+ doesn't solve the halting problem when you feed H+ into itself. How does this contradict the assumption that H solves the halting problem. We only showed that a modified version of H, namely H+ doesn't work.
it's not that H+´doesn't solve the problem, H+ doesn't even try to it's that H, as PART of H+, fails to predict H´+'s result For any machine H that claims to solve the halting problem, you can create a machine H+ for which it gives the wrong result, thus showing that H doesn't work for any machine you can imagine H and H+ next to eachother, feed H+/H+ into H first, then into H+ No combinations of the two possible results of each machine give you a logically consistent result - thus there exists no H that can predict a H+
***** Upon further reflection it makes perfect sense to me now, there must have been something in his explanation that just didn't sit right with me at first.
Hey Mike LaValley I seem to be in your former position. I can't quite wrap my head around his explanation. H can tell whether any program P will halt or not on any argument I. H+ does the SAME, it just also does the opposite afterwards. So he says he’s feeding H+ into itself, why can’t H handle that?: H is to examine H+(1) and H+(1) figures out another H+(2) system will halt (because the H part of H+(2) said it wouldn’t halt), H+(1) won't halt (again because H+(2) did halt) and H will say no, which is correct. And vice versa.
but H+(1) and H+(2) are the same machines that get the same input.., if they get different results that means the machines don't work (which they don't, they can't, there's no such H that works for any machine)
I have a point of disagreement/confusion. In the final problem you presented that causes the contradiction, H+ takes as an input two instances of H+, but loops on forever iff H+ halts on a single input instance of H+, and halts iff H+ does not halt on a single input of H+. So what's actually happening is that H+ is running forever on two inputs H+ and H+ when H+ halts on a single input H+, and vice versa. No two opposite things are occurring at the same time, so no contradiction so far. Obviously this can easily be amended by changing H+ to take only a single input, and then feeding those two inputs into its built in machine H.
My peasant mind needs more or better explanation. Because to me it just sounds like the paradox problem has nothing to do with machine h but you just added the h+ onto it to force a paradox out of it breaking machine h
The point is that H+ is so easy to add, if you had H then you could instantly make H+, but if H+ cannot exist then there's no way H could exist, because if H exists then H+ can easily be made from it. Like if there were such thing as indestructible bread, I'd easily be able to make a indestructible sandwich by slapping 2 pieces of bread together, but if I can prove that indestructible sandwiches cannot exist, then either sandwiches are not made of two pieces of bread or there's no such thing as indestructible bread.
NoRotation I still don't quite get it. Let me explain: There are three parts to this: a detector H, a program to be tested P and an input i. We assume that H(P(i)) will give a meaningful result. We then build H+. H+(P(i)) will not necessarily give a meaningful result - when it terminates, you have an answer, and that's great, but before it does, you don't know if that's because it's takes a long time and isn't done yet or because it found the answer and is looping to show it to you. H+ is not a functioning detector - unless you have another detector H that can determine if it is "looping as output" or still evaluating input arguments. So what about H+(H+) (presumably with some other input just to get it started, so it's actually H+(H+(P(i))))? H+(P(i)) is the input, and that's fine. It may be a rubbish program, but there's no rule against that. But the "other" H+, the one that actually does the evaluation, is an unfit-for-purpose program, so it won't give us a useful answer. So what will H(H+(H+(P(i)))) say? It will not be undetermined, it will say "loop infinitely". It looks at the whole thing - and will detect that at least one part of it (either the inner or the outer H+) will loop. So to me, H+ seems not impossible, just not terribly useful. I can add perfectly valid code to almost any program that would ruin them beyond recognition (trust me), but that doesn't prove that they couldn't exist to begin with.
Snagabott You're not thinking in the ideal setting, this machine takes no time to run, it instantly returns an answer, so you know whether or not it's looping. Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration to show that an essentially functionally identical machine cannot exist.
NoRotation "Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration." It's not trivial at all. The output is radically altered. Output is ultimately what matters, not what happens inside - you can have the most beautifully complex and advanced bit of code in the world, but if you add another bit of code that intercepts and scrambles all output from it, it becomes worthless.
Snagabott Except this doesn't scramble it, it's still completely unambiguous what the output is. Furthermore the algorithm that is suppose to check the programs has not changed except for the output stage, however the alteration to the output demonstrates that the algorithm cannot possibly reach a valid output and therefore the algorithm has failed.
I don’t get how logical entailment is the same as halting problem. Isn’t entailment an NP-complete problem like SAT? Anyone to clarify what the speaker meant by that?
Consider the following: "This statement is false". "Does the set of all sets who do not contain themselves contain itself?" In both cases, you get paradoxes; if it's true then it must be false then it must be true and so on forever... And likewise, if it contains itself and only contains things that do not contain themselves then it should not contain itself which means it should contain itself and so on. My point is this; if ever you try and do logic on a statement or question whose answer depends on the result of said logic, it's easy to produce a paradox. That doesn't mean that your assumption that such a form of logic can exist is invalid- only that you can't apply it to itself in a particular way; it would be easy to produce a program who responds to "All cats have seven legs" with "That statement is false" or one who responds to being asked "Does the group of all groups whose name contains the letter 'e' contain itself?" with "Yes".
So I understand that feeding the machine into itself is one counterexample, i.e. you can't use the "halting problem calculator" machine to calculate its own halting ability. But: can it be used to calculate the halting ability everything (or almost everything) else?
It could calculate the halting ability of many problems correctly, but there's also an infinite number of inputs where it's wrong. So no, it cannot correctly calculate the halting ability of almost everything.
He's creating a contradiction. He originally started with the proposition that there is a program H that can solve the Halting problem. Using only valid transformations he created a new program H+ that if run on itself has a contradictory output like "If H+ halts then it doesn't halt. If H+ doesn't halt then it halts" (in both cases H+ both halts and doesn't halt at the same time). Such a program cannot exist. This means something we did must be wrong. Since the transformations are all correct the problem must be our original proposition that there is a program H then can solve the Halting problem. So the conclusion is that our proposition is false and there cannot exist such a program H that solves the Halting problem. This method is called proof by contradiction. To prove a statement you first propose the opposite. Then you try to construct a contradiction like "1=0" or "A and not A". If you are able to construct a contradiction with only valid transformations you have proven that your proposition is false. If your proposition is proven false then your original statement is proven true.
I understand why the output at the end is contradictory, but I don't understand why the transformations that he made in the beginning (i.e. turning H into H+) are considered vaild. I'd really appreciate it if anyone could try to explain this to me! I really want to understand what I'm missing in my understanding! Perhaps my inability to grasp the validity of the transformation made to turn H into H+ is due to my weak background in mathemtics; thanks for your help!
Basically anything you can construct is valid. Take a real world analogy. Imagine if you give me an engine "E" of some kind which you say runs fine. Then all I do is add a couple of gears and brakes without modifying what's inside E. It's "valid" in the sense that there's no logical reason why I shouldn't be able to do that. I call the whole thing "E+". However when I turn on E+, I get something that both runs and stops at the same time. The logic is, since I haven't done anything that could possibly be a contradiction (adding gears and brakes can't create contradictions), then something must be wrong with your E to start with.
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.
@@foreverseethe It takes the machine and the input that the machine would be given. It's possible for a machine to loop forever on one input but halt on another.
I don't understand. Don't you need to define the program and it's input to determine if the machine will halt? The inverse halt machine has been inserted into itself with no input. In my mind, this would contain an empty program, which would halt. This means the input would inverse, and therefore not halt if ran with this input. The top level machine would inverse this, and then halt. Im assuming I'm missing something?
Wouldn't this imply that it is impossible to fully simulate a universe? Because you have to use a computer to simulate a computer created in that universe, and then simulate if it will halt or not. So we are back where we began.
You don't need to simulate if it will halt or not. You just need to simulate the next step in accordance with the next step of the universe. It doesn't matter if it would never stop. You're running the program anyway.
Im not seeing it. Turing was supposed to have proved this in general (for any hypothetical machine). This example uses a partially specified machine. So how does the proof work in general and not just for machines specified in the manner of “+”?
Turing's 'decision problem' is related to Godel's problem of 'undecidable', in which an algorithm of finite axioms leads to undecidable conclusion, while an algorithm of infinite axioms leads to a decidable conclusion.
+Naimul Haq Don't forget that Turing spent time at Princeton. Although he worked with Church and Von Neumann, he knew Kurt Godel and if I recall Andrew Hodges bio they had some discussions and were well aware of each others work.
I'd like to suggest to everybody on this comment section the reading of "Goedel, Escher, Bach: An Eternal Golden Braid" by Douglas Hofstadter. Great book very funny and interesting.
Why @5:06 does an answer of yes make it loop forever? You seem to have your answer at that time. If the output you wanted is either yes or no, It dosent matter if it says yes numerous times or once.
We are all going a bit too mathematical here. We've just proved one case, where the machine won't work. Sure that's enough to prove that it (the machine) isn't a universal solution to the problem it was designed for, and hence it is mathematically non-existent. But for all practical purposes, there is possible that a machine can be constructed that could solve the halting problem for every case *but* this. In practical scenarios, you wouldn't wanna test the machine against itself anyways. So, for me atleast, a practical Halting machine is still not impossible. I know this is a proof by contradiction, and it works cool only when you need to be absolutely sure that each and every scenario is covered. It's like in physics, some formulas/theories work under some circumstances. The formula for gravitational potential energy (mgh) is only valid for height 'h'
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.
Many thanks!
Thanks. I finally understand it
Nicely put.
Why is it specific to halting? Can't one use the same trick on say return or output value? "Oracle said I'll return x. So I'll return x+1". What's so specially about "halting"?
thank you
Deepest V neck of all time.
And potentially the worst tupé ever :P
+CatnamedMittens “Michael Bialas”
limit x → ∞ : V neck = 11
Sgt Jupiter I don't know what this means.
+Sgt Jupiter true, but I think you were a bit off, V neck = 12, rounded up rather than down
+CatnamedMittens (Michael Bialas) wtf this isnt a thorin video
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.
Best explanation! yes, the whole point people, it to show that it cannot exist, since there is going to be at least one case where it does not work properly, meaning it's not perfect and cannot detect HALT. Which means no machine can exist that does it.
Thank you so much for explaining this! I couldn't figure out what the purpose of H+ was, but in that context it makes much more sense.
Turing's argument is bollocks and doesnt prove anything.
Nope because he creates a contradiction in the first place in order to prove something. What kind of proof is that?
But you see that the contradictory machine itself is bogus? You can't really determine the 2 outputs. Looping forever and stopping at some point in the future are not different. Because the stopping could take place in billions of years. If you fed the program into it, you would never be able to determine whether it loops or stops.
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.
Clever! Thank you for sharing!
Incredibly put!
Would it need to be "immediate"? What if it took 1 mllion years to run?
Nice! Yes for Goldbach's, but not for twin primes. You can't write a program that checks if integer has no twin primes after it without checking all primes bigger than it so it will loop forever whether twin prime conjecture is true or not.
@@rupen42 no this isn’t a machine you can actual use or build the same way you could a TM. In essence, oracle machines provide a way of comparing harder problems to each to see if they are in the same class. While this machine could “solve” the halting problem for Turing Machines, there now introduces a halting problem for Oracle Machines which is basically just as hard as the regular halting problem if not “harder”
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 if it simultaneously halts and doesn't halt until it is observed?
i see what you did there ...... but this is no quantum computer
Oh for Christ's sake Schrodinger, get off of youtube.
HumanRights4Everyone pilot wave interpretation FTW!
Schrodingers computer.
Then you train a semi-existent cat to go in and repair it.
I did a depth-first search on this page, it returned his V-neck.
H+ instead of H'. I'm concerned
*>furry weaboo*
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.
wow thank you
You just repeated what he said in the video.
@@kanekeylewer5704 because some people have problem understanding what proof by contradiction means
@@sayanghosh6996 gang gang you amazing
that's a great explanation, thanks!
What would happen if pinocchio said: My nose will grow
Gregory Reis yes
+wingsandstache It would not grow because he was telling the truth.
***** You got it right.
***** Then riddle me this, if a bat and a ball cost $1.10 and the bat is one dollar more than the ball, how much does the ball cost?
Right, then if 5 machines make 5 things in 5 min, how long would it take 100 machines to make 100 things?
I love how there's tea and cups behind him :D
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.
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.
I asked exactly the same thing, it would be great if someone addressed this issue.
I'm also not sure I really understand how we're proving anything either. The paradox described feels like it implies that that having this specific input ran through the machine would result in looping, but we can't know if that would even be the case? The question was never about whether H+ could exist but whether H could exist. Is it because H is a product of H+ that it implies failure? I don't think it is valid to say 'your machine with 100% success rate in deducing if carrots are peeled or not is foiled because I added extra machines at the end of it that peels the carrot if it is deemed peeled'.
That can easily be solved by turning the input of H and H+ into a single input that describes both the turing machine and its own input to be tested. That way everything is receiving the correct number of inputs and the paradox still happens.
@@Outwardpd You see, the problem is that your peeled-carrots-detector example does not create a paradox, so there's no problem. A proof by contradiction starts out assuming something that you don't know is true (or exists) is (or does). Then it shows that, if that is true, than something completly absurd and impossible would also be true, automatically. Therefore, what you assumed to be true cannot be, in any way, shape or form.
The halting problem assumes a turing machine that solves it exists. Then, using some simple steps, creates a set of inputs that makes it not work. Therefore it couldn't exist, at least not as described. There's no program that can determine if any problem halts, because we just showed how to create a program that wouldn't work, using itself. A contradiction. Contradictions cannot be true, so your assumption can't be either.
Basically if A, then B. If B then not A. Therefore, A can't be true.
@@eac-ox2ly Awesome. Thank you!
When someone asks whether h+ halts or not:
Well yes, but actually, no.
But also actually no.
nes? or yo?
The 3rd layer of H+ has no input so the programm cant run
Think of H+ as a program. It's a program that takes _any_ program as input, determines if that program halts, and then gives an output in the form of halting (if the input loops forever), or looping forever (if the input halts). In order for H+ to exist, then it must also be able to take H+ as an input, determine if H+ halts or not, and output accordingly. Remember we must assume that H+ is solvable, and therefore must output either by halting or looping forever. So let's say that H+ halts. If we give H+ as input to H+, the machine determines that it halts, and then loops forever. Vice versa applies too, so let's say H+ loops forever. If we give H+ as input to H+, the machine determines that it loops forever and then halts. This is the contradiction - the machine gives contradictory outputs for itself.
This contradiction means that the assumption was wrong, meaning that there _cannot_ possibly exist such a program that can take _any_ program as input and then determine whether or not it halts.
I cant seem to understand the part "If we give H+ ad input to H+, the machine determines that it halts, and then loops forever."
Why does it loop on forever after determining that it holds?
Why doesnt it just determine that it halts and then halts?
@@paulvorderegger1522 It loops forever because that's what H+ has been designed to do. If you feed it a program that halts, then it will loop forever. If it did anything else, then it wouldn't be H+. If you gave H+ an input program that halts, and H+ cannot loop forever, then this would also imply that H+ can't exist.
@@gordonfreeman5958 Ok I finally understood this after seeing the following pseudo code:
def thisFunction ( ):
if halts(thisFunction):
loop_forever( );
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
Same with sets
@MrBigbanan imagine you are trying to actually learn something and you ask a very hard question to your computer. If it "runs forever" you will never be sure that its a no, maybe its just slow and it will eventually say yes. And you cannot ask another computer to tell you if it will run forever...
there is not really any self referencing here, H+ is defined without H+, same for H. Imagine H+ is some actual .exe file that needs a file as an input, you are allowed in the real world to give the .exe file to your .exe program.
What makes the 'machine looping forever when reaching a yes' upgrade count as being relevant to the original question?
Is it because the machine is suppose to account for all programs in a form of universal sets, including the added upgrade?
+Roman
He's proved that the existence of H will lead to paradoxes, so therefore H can't exist.
He proves asking that type of question about anything is absurd. look up Proof By Contradiction. He says that if it WERE possible, something else would happen that we know to be false. and since the rest of his arguments are valid, the premise must be absurd.
fk u all
@@ximbabwe0228I understand that it doesn’t matter in the end, but this unexplained noise is so jarring. If it doesn’t matter if it halts or not, when the answer of the machine h was an “yes”, then it’ll be far nicer if he just said “this doesn’t matter in the end but let’s say it just doesn’t halt, just loops.” rather than just giving me the definition as if it’s logically meaningful role.
My wrong assumption was that the output supposed to try to give an answer to the original problem because the no leading to halt sounds like an intuitive upgrade to give an answer to the original problem.
@@IoriTatsuguchi thats the point of this paradox
in the final example we are feeding H+[1] the input "H+[2] evaluating input [H+3]", however, h+ needs both the program and it's input to determine if it's going to halt.
what is the input into H+[3]?
i watched 2 videos so far , inclusing this , still dont understand the halting problem because , why would you put and loop when it give a yes answer ? it it halts let it just halts and its done ? why forcing it loop ?
looping forever is the opposite of halting, meaning it doesn't halt
4:42 but doesnt H+ expect two inputs? the description of H+ is "given the following input, will this code half or not" so when we give H+ itself as the "input" input, we need to actually give it something else, because the H+ in the "code" input expects two inputs??
i hope this makes sense
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.
George Edwards His nose would not grow. Paradoxes are not lies.
***** if it would not grow then he must have said the truth. The sentence "This statement is a lie" must be true. But then if he said a lie his nose should have grown.
No, his nose only grows when he lies; you can say something that is neither a lie nor a truth. For example, I could say "Zerg is the best race" and, as it would be an opinion, it cannot be true or false.
***** I understand what you mean; please consider that I don't deal with coding or computer programming at all.
I see that the output (the nose growing) depends on the fact what is correct (true) or not. The problem comes when you use the statement as the argument of the statement itself. So when the statement is true, then "This statement is a lie" is true, which means actually the statement is a lie, but if he said a lie, then "This statement is a lie" is not a lie, which means he said the truth... You see? The process never ends.
+BroadcastBro Think I got it... I couldn't understand why they were reversing the output.
But could you possibly explain with the example of H+?
Because if you feed H+ into itself, well H+ cannot solve H+ right? Which makes it a No, which halts the machine.
So that stops it. Which means H inside H+ was right.
Can't remember the last time i was confused this much.But your explanation is better than the other guys so cheers!
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.
I can design a program to determine whether a closed loop program (I.e. one that doesn't have any inputs) repeats forever. It executes that program and examines the memory allocated to it, and as soon as it sees a repetition in the memory, it terminates that program and outputs yes, that program repeats forever. It avoids the halting problem because it requires an input, rendering it incompatible as an input.
After listening to this, my brain halted :P
I’d just like to say: The dramatic close-up when you say “it’s a paradox.”? Very Nice
It's the little details
Error: H+ cannot be converted to type Input for parameter 'i' at line 4:40.
H+ is a program, not a program and input pair, which is the input required for H+ p.
I saw a comment who fixed that error by letting H+ have a single input P and send to H and of course do the if halt loop and if loop halt at the end. When it is done like this, if you give H+ the single input H+ you'll find that if H+ halts on H+, H will have determined H+ shouldn't have halted in the process, and if H+ doesn't halt on H+, H will have determined H+ should halt on H+ during that process.
The comment didn't bring up this, but I realize that not all programs can accept themselves as inputs. I imagine we can also extend H such that no will be the answer if the input is not allowed (because it should halt with an error)
If you pass H+ to it self, what input does it get? Or would it just loop forever waiting for input?
*****:
1. Regarding the multiple simultaneous clips at the end, have you though of using a black 50% alpha mask to subdue the clips whose audio is muted? It might increase the visual appeal of those clips sections.
2. What are the applications that you use to create the phosphor green animations? I don't care so much about the color, of course, but the animations are quite well done and I'm curious about the tools.
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.
When feeding (H+, H+) into H, we get "Does H+ halt on input H+?" But H+ needs 2 inputs, not just 1, so what happens?
That confused me too, because the video glosses over technicalities. But I realised it looks like this:
bool h(alg, param) {
if(halt(alg, param)) {
return true;
} else {
return false;
}
}
void h_plus(input) {
if (h(input, input)) {
while(true) ;
} else {
return;
}
}
i.e. h_plus() has a single input which it duplicates when it calls h().
@@TheCriticsAreRaving but what paramilitaries will the program have ?
If h processes h+ which has different parameters than the h+ which is processing wouldn't that make it so that h+es are different thus they wouldn't do the same thing . so if it loops it isn't a contradiction anymore because it is processing different parameters
@@sababugs1125 no there is no problem here
h_plus simply uses h as black box.
h should work for all inputs including once tha have the first and second argument the same.
@@sababugs1125 i mean in his algorithm
when you pass h_plus(h_plus)
you get:
h_plus(h_plus)=>h(p_plus,h_plus)=>h_plus(h_plus) => ...
basically its an infinite loop, but tho you have no idea what h does,
as h might "look into the future"
without actually running h_plus on h_plus return some answer.
but then no matter what h will say it is always wrong.
4:22 Here, the H+ machine has two objects as input. So when (H+, H+) is fed as an input to H+, the input first goes through the machine H. The machine H answers the question of "Does the machine H+, when given H+ as an input, ever halt?". My confusion is in this question itself. How can the machine H+ accept just one object as input? It's designed to accept two, right?
I have a question!!
When I took Philosophy courses years ago, I was taught that adding self-assumed premises to the given question is not allowed. I have watched a few explanatory videos regarding Halting Problem on RUclips, and all of them involves adding extra logic gates or machine components on the original "machine H." Isn't this kind of like adding self-assumed premise to the original question, since the original questions is about whether Machine H will halt, not Machine H+?
This is because the proof is very simplified. The original proof (not going into details) was like: i have an algorithm h wich will decide whether an algorithm x will stop. Then we put ALL possible Algorithms combined with all possible input in a numbered map (each column/row has a unique number). You can now choose algorithms and inputs (e.g. algorithm number 4 with the input 10). We can some really crazy math with an alter every row, EVERY row from 0 to infinity is still unique, but now you have a new row with instructions not found in the table. You can define this row as the algorithm h+ (uses h) (actually the algorithm used is different from h+, but for a simple explanation you have to change it) and if you feed the algorithm with an input z (z is the number for the input), it will print out a different result that the algorithm in the row z for the input z. Since you have this cool table with every possible algorithm, you can find the algorithm h+ with a number x. But you proved that h+ will give you a different result than algorithm z for the input z and input x must exist. So h+ must print a different result for the input x than algorithm x (which is h+) for the input x? This is a contradiction! But this case MUST (this is the big point) exist if our assumption is true.
the problem is that the proof is extremely fundamental and very, very important, but also very hard to explain or understand. I altered the proof heavily. To explain it in a simple way you have to make a sacrifice, and you spotted a consequence of one sacrifice.
LeanderK Your explanation makes much more sense than the video to me, thank you.
However, in the video I can't quite grasp why the loop and halt extra boxes should be added to the outputs, because if that's the case wouldn't the h+ that is being used as an input not halt at all?
And if loop is added when output is yes, then halt is added when output is no, then why bother feeding h+ into itself? Pretty much all machine as an input will get the contradiction because we set the h+ like so.
I don't really understand philosophy and proper logic, so please enlighten me :D
Dennis Samuel "All algorithms" would by definition include a modified original algorithm. A modified (as described in the proof) algorithm is part of the set that includes all algorithms.
Gran Cero No because the problem is respect to ALL machines. adding stuff onto an existing machine only creates a new machine which also has to obey the assumption proposed.
Well, I didn't understood the proof for the same reason Gran said...
For people in comment that want an example of a really simple algorithm yet very hard to tell if it will finish or not is Collatz conjecture.
It goes like given an input x if it is odd triple it and add 1, and if it is even, half it. Keep doing it until you reach 1.
Fun fact is that there is no way to tell how many steps it will take for any X without carrying out the algorithm.
NOTE this has nothing to do with the halting problem. This is just a fun contrast to other common algorithms which we can easily tell if they would halt just by inspecting them.
I like the idea of a machine with a billion binary inputs and tons of layers hidden inside and a single binary output.
I had to watch this video twice trying to understand it. Great one!
Question
H+ named 0
H+ named 1
H+ named 2
0 runs, checking whether 1 will halt or not halt if 1 is given 2.
Wouldn't there be an error, since 1 is only being given one input, rather than two which it is designed to take, and 2 is not being given any inputs at all?
***** So
H++ named 0
H++ named 1
Virtual H++ named 2
Virtual H++ named 3
Virtual H+ named 4
0 runs, taking 1. 4 takes 2 and 3 as inputs. 2 runs with 3 as input. 3 still lacks the one input it needs to run. Wouldn't there still be an error?
I'm still confused. What alternative is there to thinking of them as something besides different machines?
*****
You're missing the point, because the paradox would still be encountered within your H+ machine. It doesn't matter at all what the inputs are - the paradox will still arise.
Or do you actually think you've figured out something in a youtube comment that mathematicians have missed for the better part of a century?
No, I'm just confused. I don't think that the proof is wrong or that I'm particularly more intelligent than anyone else, quite the opposite, I don't understand the explanation, and am attempting to identify where my misunderstanding is coming from.
Is it necessary to take such an aggressive stance?
Was actually responding to SBareSSomErMig and eir fairly flippant 'That's a little mistake in this video' comment. The video's fine, eir logic is faulty. You're good for asking questions. :) The system is designed so that the entire machine is fed back into itself as both inputs, not just one. So the system has the correct initial inputs, but will still result in a paradox as explained in the video.
I think this explanation is wrong because H+ with two H+' as imput is different from H+ with one or zero H+' as imput so the second one can halt while the first can loop and there wouldn't be any paradox. Correct me if I'm wrong.
Either I didn't get the Halting Problem in university or Mark describes it incorrectly. He says at 03:35 "...whether a given machine with a given input will halt or not." Shouldn't it be "any machine with any input", any as in an arbitrary? Because surely you can built a machine that can determine the Halting Problem for "some" machine with "some" input, but the point is you can't do it for every/any/arbitrary machine. Or maybe I just got lost in translation? (I'm not a native english speaker)
His description is ok because he doesn't claim you that this program is in some kind of set, he's saying "given program" which actually means that this program could be any program. The same goes with inputs
A minor problem, the description actually given won't create the paradox. H+ needs a front end as well as a back end. What you have in your example is that you are feeding H+(H+) to H and asking if it halts and finding that H+(H+(H+)) exhibits opposite behavior, which may be unusual bot not impossible.the fron end needs to do a small conversion so that x(y) is changed to x(y(y)). This is actually an important consideration. Languages which cannot expand their inputs are always decidable. But expanding the inputs allows the creation of self-denying statements.
I think it is a little confusing when you feed H+ to itself, H+ should be fed to H.
H is the machine that you assumed will solve the problem. If you end up in a paradox on your assumption then the assumption will be falsified.
By feeding H+ to H+ nothing will happen to the original assumption, because you basically are not touching H.
If you feed H+ to H, then if H+ halts, H will say it doesn't and if H+ doesn't halt, H will say it does. Here is the contradiction so the assumption is incorrect.
H is part of H+
It’s the same thing you are feeding it into yourself
The problem isn't really feeding H+ into H+, but there is a problem with the explanation. I don't know how exactly Turing wrote his proof since I didn't read his paper, but the way every single youtube channel is explaining it is simply wrong.
The input to H+ is a tuple (P: Program, i: InputToProgramP). The whole thing is the input
So when you feed H+ an input (P=H+, i=H+), you are basically asking "does program H+ halt when it receives input H+?". The problem is, the input to H+ is a pair (P, i). So you can't just feed it P, you are missing i. It's like you are feeding it (P=H+, i=).
To fix that, you'd have to feed H+ an input (P=H+, i=(P=H+, i=H+)). But you end up with the same issue. So you'd change the input to be (P=H+, i=(P=H+, i=(P=H+, i=H+))) to try to fix it, and so on, forever. You can't ever feed it itself.
@@rafaelclpTHANK YOU, I WAS THINKING THE EXACT SAME.
You formullated that pretty damn well and I fully agree with you.
Im just wondering wether or not you can still prove it by induction, but i dont think there is even a base case, so not sure about that
Sorry if it's been asked/answered before but I'm confused. Why must a 'yes' answer result in a loop? Why doesn't it just stop? And why not permit the 'No' answer to loop?
I've always sort of understood this as a more general proof that any algorithm which analyzes algorithms can never be fully generalizable. If it could, then it could analyze itself and respond to the result by contradicting that result.
+Computerphile At 3:58, Mr. Jago says that the blackbox will output "Yes" if the program halts, but "No" if the program never halts (a.k.a loops forever). But how does the program know that it will loop forever, since with every iterating loop it has the potential to halt?
- An Engineering Physics student, and Physics student in California
It doesn't even matter how such a machine works because it cannot exist. He even says "Don't worry about how it works, just assume it does."
5:18 Aren't you just asking the wrong question?
"Does the first iteration of H+ Halt?" would be a better one...
Also, doesn't that mean the machine could be the human brain...so...we couldn't do this? Yet...we can?
Also, how does that fact that putting H+ into H+ break means that H normal can't solve it?
actually a human couldn't solve the halting problem because humans are at most turing complete
+lolzomgz1337 I could have sworn I hade a reply to this comment. And I got anotification when +Jahaal Mordeth posted. But my comment isn't here :(
Simon Lindgren
Damn. :(
+lolzomgz1337 This is a vulgarization of a problem that is actually harder to prove than this so you have to give some leeway.
Philippe Carphin Okay, fair enough.
I'm a little bit confused, Jago started by talking about a very vague premise-conclusion problem and he wound up only proving that a halting machine could not exist. What relation does this have to premises/conclusions?
Why is the transformation from h to h+ valid? Isn't h the one machine that solves the problem?
What would happen if you give h+, h+ inputs to another h machine?
I'm not saying you cannot make h+. I'm asking why can you expect it to solve the same problem that h can. It just sort of feels like attaching a shredder to a printer and saying printers can't exist.
I'm not really program-savvy but I'd like to understand and not just take somebody's word for it...
OK I see what you mean. You're completely right that H+ doesn't do the same thing as H. But it doesn't need to. The idea is, if H is valid, then H+ should also do *something* reasonable. It doesn't matter what that something is, but at the very least it shouldn't result in a living contradiction.
With your printer analogy, imagine if you attached a shredder to a printer and got confetti that is both all black and all white at the same time. It's a contradiction, and you know your shredder can't be responsible. So something must be wrong with the printer.
Ahh that makes more sense to me now. Thank you
if i'm not misunderstanding it, is one example of a halting feature a bit of software that checks for bugs when developing software?
wait, from the introduction it looked like P and I are different in nature, like different data types, but then you feed H+ on both? not clear
'p' never changes in type, it's always some kind of program. However, 'i' the input, can change. eg you make a program p that multiplies a number you give it by 2, then you test it with the h machine, and you can check whether p will halt or not given input of type integer, then string, or even of input program or 'p' (feed it some Java or something eh?) you see what I'm getting at here?
I appreciate what you are saying but your answer doesn't solve the formal problem I am posing. If you want to feed H+ as the 'p' to H+ you need to formulate it correctly as a program/machine that takes an input. Now, H+ must be viewed as a machine that takes a pair (p, i) as input. So the final test would be with H+ and (p,i) fed into H+.
what's the difference between a formal problem and an informal one? ^_^ Anyway, when you approach this theoretical machine thinking like that, you quickly end up with infinite recursion, can you see how? besides it defeats the simplicity of the system to start worrying about data types, when you get onto larger programs, you expect this machine to be formatted to take all 1000 of the programs variables and inputs as the 'i'? if anything like this could ever be made, the team behind it would be smart enough to ensure it only ever needed two inputs, P and i, because there's zero upside to any other approach, wouldn't you agree?
Well formally, everything is just numbers. There is a 1:1 mapping between programs and numbers, for example by taking the program's code in binary and reading out the whole sequence as a single number. So it's perfectly valid to use the same number as both a program and as an input to a program.
I feel like I finally began to understand some of these issues after spending way too much time on it. Basically the idea is that whether the input type is valid or not the program still runs with that input. For example, if you built a rudimentary calculator and then you feed it a string input, if your program isn't able to handle that string input it can either throw and error and stop (halt) or it can loop infinitely due to invalid input (loop forever). So the input types don't necessarily matter because a program will still result one of those two actions, and when you're feeding a program/algorithm as the input itself to be analyzed by the program it will still do either of those two actions, regardless of whether it is a valid type.
What if the computer holds an oscillating program, giving equal times yes and no to our halting query in its N1th run and feed that answer back into the computer, hence modulating N+1th to the oscillating signal with the time needed from input to process to the output. Wouldn't then the modulating frequency in relation to the ever diminishing signal modulation and it's ratio be a solution solving the contradiction's to it, answering a halt state?
I thought I had addressed this before but I could find my response. The Halting problem paradox (at least as described here) is wrong.
It's impossible for H+ to self reference since it requires 2 inputs (the 2nd being in input to the machine to test) but this requires infinite recursion to set up to self reference even if you fix H+ to take multiple required inputs as a series (or by any other method) into the 2nd slot.
burstofsanity late to the party, but fwiw you don’t need this problematic self-reference: the “computer” input I.e. the “top” input, is just a representation of the program, like its source code (or Gödel number), not its state with respect to a given input.
What do you mean by the input h+? H+ can be fed as a program but how does one feed h+ as an input?
I was lost already at 1:14 when he said: "can we automatically test whether the premises entail conclusion"
This was a brilliant explanation of the halting problem! Thanks!
I'm not clear on how the behavior of H+ shows anything about the behavior of H. The two machines are not the same, so why would you expect the same (i.e. correct) output. By this logic I can ask whether it is possible to build a vehicle that can move down a road. Suppose there is such a vehicle, let's call it CAR. CAR can't possibly exist because I can attach a module called NOGAS that removes its motive force, so it can't go down the road. Since CAR+ can't go down the road, no such vehicle can exist. QED.
If you're going to add parts that break things, why pretend that you're still dealing with the same program?
+Jason Patterson Yep there is no such vehicle CAR+, that can drive because CAR+ = CAR + NOGAS. There is no fuel powered car that can drive without fuel.
The missing part from your example is a contradiction. CAR+ can't go down the road while CAR can, and that's it. If you somehow reached a contradiction using CAR+, then indeed CAR could not exist. Both CAR and CAR+ can exist here fine.
What happened in the proof in the video is that using H, he constructed H+, and showed that H+ is impossible to exist. So essentially we've arrived at two conclusions at the same time, H+ can exist using H, but at the same time H+ can't exist from the way he described in the video. That's a contradiction, so the assumption that H exists was wrong. Hope that made things clearer.
@@Kalernor Does not make sense "using H, he constructed H+, and showed that H+". Meaning it is possible to put anything as an addition to H, and then say:"look, just because I added some impossible things to H+ it means that H, my base, is also impossible.".
why does the background of binary digits during the title contain two letter f's(or at least, I see two)?
***** I know, but if it were supposed to be a hexadecimal background, it would have more than one, zero, and f
Pardon me for so saying, but it appears that: This entire presentation (and argument) is itself a general algorithm that in fact does decide a whether a program will always terminate or not. This presentation demonstrates an answer to the presented dilemma. Given the recursive, self-referential nature of the proof presented, I think it only fair to consider the proof itself as part of an algorithm that does in fact solve the issue at hand, thus this ONE CASE presented actually shows that there is an answer. After all, you've given the answer in the form of a proof, no less!
If you consider your own thoughts as part of the algorithm inside the "machine" then you are the solution, since you can ALWAYS decide if a program will terminate (by recognizing an apparent paradox).
Thoughts on this?
@@ZandarKoad I agree, and cannot find a proper example/explanation anywhere.
"The Halting Problem" is a problem specifically for Turing Machines, or any other equivalent formal system (first order logic, the lamda calculus, etc.). Once you step outside those systems, "The Halting Problem" is not defined.
I am at a loss as to how you can give an arbitrary function an arbitrary number of inputs of arbitrary class.
Many programs run without taking input, so how does that work?
E.g.
int main(){
int x(5);
return x;
}
What does it mean to give this program itself as input?
4:30 About feeding H+ into H+: Since H+ requires 2 inputs, this would require a recursively defined input, right? p = H+ and i = (p, i) Edit: Ok, many people commented this already, of course. :-D
Is there an answer?
is time the missing factor in the halting problem ? if it were to time out then the halting problem is solved ? maybe 555 timers were newer back then or it would be harder to limit the amount of operations per program.
***** FYI: This almost 1 year old video misses links to promised videos at the end.
Florian H. thanks for the spot - fixed now >Sean
+Computerphile You fixed the halting problem, add links !
Wouldn't that just be a superposition of halting and non halting? so your answer is both?
I keep looking through proofs of this, but I am a little confused; it almost seems arbitrary that we say that if program P does halt on a given input of I, then we loop forever. Why would we assign "loop forever" to the output of yes ("it does halt")? If such a program could deduce that we halted, why would it then need to loop forever? Would it not just halt after producing the answer?
The following 3 lines will clear things up:
def thisFunction ( ):
if halts(thisFunction):
loop_forever( );
Now, if halts says "thisFunction" will halt, then "thisFunction" will start looping forever, therefore the answer was wrong
but maybe there can be a program that solves the halting problem for all programs except itself !
It's not for itself, h solves the halting problem not h+.
But H+ is constructed using H. Maybe let me refine Kot_Robot's comment:
Maybe there can be a Turing machine S that solves the halting problem for all programs except those that reference a Turing machine capable of solving the halting problem to the extend in which S itself is capable of solving the halting problem.
I intuitively think self-reference is key to both the logical contradiction ( like the liar's paradox aka. "this statement is false" ) as well as to the way to solve it ( think through the Turing machine S I constructed up there ).
@@greencoder1594 Sorry to disappoint you, but that is not possible. This is a really simplified version of the proof and i understand that it may hold this implication if you aren´t invested in theoretical computer science (formally it´s usually prooven via diagonalization, which is much less intuitive). It actually turns out that even the BTHP is undecidable (blank tape halting problem -> given a turing machine M, does M halt on an empty input?).
I don't get why he feeds h+ back into the h+. Is there a reason why, or can there be other inputs as well?
Doesn't this proof just show that the transformation from H to H+ was a bad decision? I mean, theoretically I could use H to test H+ and see if it will halt or not. I don't necessarily have to use H+ to test H+, right?
Can someone please explain this to me?
When proving something by contradiction, you start from an initial assumption (which you want to prove wrong) and then reason upon it until you arrive at a contradiction. Since all the reasoning steps between the assumption and the contradiction are legal (consistent), the only possible explanation for the contradiction is that the assumption was wrong - so the opposite must be true.
The wrong assumption here is "there exists a machine H which solves the halting problem", and we use a "bad decision" (a legal transformation from H to H+ and a legal execution of H+ on itself) to end up with a contradiction. This proves that the opposite is true, so we conclude "there is no machine that solves the halting problem". Sure, running H on input H+ might not lead to a contradiction, but that simply means it's not useful as part of the proof. The goal is to make the "right" bad decisions in order to end up with a contradiction.
If you feed H+ as the program and H+ as that program's input to the normal H machine it will give the wrong answer.
The strategy in the proof is to show that if such a working H machine exists, then we can build a machine H+ that contradicts its own existence. Since you can never build such an H+ machine in any way, then it must be impossible to build the H machine to begin with.
You've only disproved machines which are limited by the two inputs and one output as unable to solve the halthing problem. What if your halter determiner machine was able to take in more information than that? Such as, "Am I part of a larger machine?", or any other relevant information necessary to solve the problem?
The mistake in this video is that the box in the machine asks, does program p with input i halt? However you cannot feed in H+ to this machine because H+ takes 2 inputs instead of 1.
You could fix this by adding a new component to the front of H+ that only takes 1 input and copies it into 2 for the inner machine. Now H+ takes only one input and the argument works just as explained.
Does it matter what input you give to H+? in the example you provide H+ with itself and itself again. But is it just as valid to provide H+ with itself and any other input?
It reminds me of the book "Goedel, Escher, Bach".
Looking at this from a programmers perspective, if we add an additional parameter say T and T represents a given Time unit. What if we assign T to H and if T exceeds some Upper limit say 24 hours. We can say that this program is not computable, and if the program computes in a time Under T we can say that is computable.
I understand in terms of Logic, this is not a True, because Time is conceptual and a program could theoretically run for longer than 24hours and yet we cannot determine if it will Halt.
However in a real world solution, would this be valid.
Thanks for any answer.
there's a minor mistake in the presentation: the definition of H+ was "take inputs a program P and a set of inputs I. if H(p,i) then loop forever, otherwise halt". This simply doesn't work, you can't apply H+ to H+ and H+, since you're implying that H+ both takes 2 inputs and 1 input.
The correct definition for H+ is
"take a set of inputs i. if H(H+,i) then loop forever, otherwise halt"
This way, H+ is a one-argument function (just the i), and you can apply H+ to itself to get the required contradictions.
Thank you. It makes perfect sense now. I couldn't understand how H+ could take an input of just itself.
From the description of H+ it would appear to me that it doesn't have an output at all. If it loops forever then it clearly does't have an output, but if it halts, it halts. From the diagram of the machine Mark drew, it doesn't seem that H+ should give any output when it halts.
4:59 h+ will not give an answer because of infinite recursion (Will h+ halt given will h+ halt given...) thus the paradox never exists.
Just to clarify: the logic here is that if your conclusion is paradoxical, then the premises are necessarily incorrect? Is that always true? Or is it just true for stuff that we can or can't design?
This is not the correct proof, as in the described system it is invalid to give the pair (H+, H+) as input to H+.
Why? Because the second element of this pair is not a valid input to the first element.
There's probably an additional assumption that would make this work, but its missing from the video, which drives people mad in the comments.
+poliklosio
when we give H+ to H, we actually give a blueprint of H+, that specifies how exactly H+ works.
that is, essentially, a bunch of characters, so you can look at it as an input to another machine, regardless of what the characters actually mean
+inon star Yeah, I know that, just not from this video.
+poliklosio All programs can take all inputs. This is a fundamental requirement from a program. If the input is invalid, or it can't process the input, the program either halts or not. But which is it? That's the million dollar question.
+Aman Singh I disagree. A program is not necessarily well defined for all inputs. There is no reason for every program to accept any-length stream of arbitrary bytes. Author of a program is free to describe any preconditions about the inputs to the program. If input data doesn't follow the preconditions, it doesn't make sense to consider behavior of the program in such case.
It's like considering what happens when you divide by 0. The answer is the question itself is incorrectly formulated because division is not defined for this case.
The program doesn't even have to have means to accept the bytes. How do you feed stuff to "Hello world!" program? Assuming it has the means to accept your bytes, of course you can try feed incorrect values to it, but it is not really interesting what happens in such case, as you are deliberately breaking laws of mathematics. The program doesn't even have to check for input correctness in order to be correct itself (although sometimes it may be desirable to do so).
I have to make it clear again that the model you describe IS used in the original proof about the halting problem, its just that the video doesn't say it.
poliklosio Well, this is a video on Theoretical computer science, so it should be assumed, along with many more assumptions. For example, infinite tape of the Turing machine. This is the reason size or format of the input doesn't matter. The state machine of the Turing machine will either halt sometime or not, regardless of the "format" (using multiple tapes for writing any "special character") or size of the input (obviously, infinite tape).
Thanks, big help! I was confused about this topic for my discrete math class, you saved me.
I get the idea here, but it seems to me, once you've added on extra workings to the halt detector, it is no longer the halt detector, and has become a different machine. The example seems a bit off too, pretend this machine works, now we change it, it doesn't work, thus proving something about the world. Logic is a great tool, just the use perhaps in this situation isn't making sense to me.
"Can you build a machine, that can tell you whether or not ANY given machine with ANY given input will eventually halt?"
No you can't, because you can always create a machine, that will never halt. (Overly simplified.)
The key here is the created paradoxon, that if the machine should halt it doesn't and if it doesn't halt, it does.
He tried to simplify the solution, you can actually prove the same thing with no modifications to the H machine.
The idea here is that if such a general purpose halt-detector H exists, then from it we can build the impossible machine H+. Since H+ is impossible, then H cannot possibly exist.
Given H, H+ is the machine that takes as input a set A, and does the following with it: "what is the result of H applied to inputs H+ and A? If yes, then loop forever, otherwise, halt"
now, to show that H+ is indeed an impossible machine, feed H+ to itself (that is, substitute H+ for A in the above sentence)
this gives us "what is the result of H applied to inputs H+ and H+? if yes, then loop forever, otherwise, halt". We'll call this H+(H+)
now, H+(H+) either halts or not. If it does halt, then it didn't loop forever. This means that H applied to inputs H+ and H+ gives us a "no" answer. Wait a minute, from the definition of H, this means that H+(H+) does not halt. This is a contradiction, which means we cannot assume that H+(H+) does halt.
okay, so that doesn't work, this must mean that H+(H+) does not halt, right?
Well, in that case, since H always halts, then H+ must have gotten stuck in the "loop forever" part. But in that case, then H applied to H+ and H+ gives us a "yes" answer. From the definition of H, this means that H+(H+) does halt. We got ourselves a contradiction again.
We exhausted all possibilities of H+(H+) halting or not, and none make any sense. This means that H+ is an impossible machine to begin with. Since the way we modified H to make H+ is completely valid, then H must be impossible.
Ricardo Amendoeira Ah okay, with the modifications, it seemed to me something was wrong, as the add on part would be constantly flip flopping itself, just to fool the H part. Does bring up some interesting thoughts though, for it to work, H would have to be lying... and thinking ahead.
There are 3 machines: H, G and H+
H is the halt detector. The point is to figure out whether it can exist.
G is a machine that loops infinitely if given the input "yes", but not if given the input no. We know that such a machine can exist.
H+ is what you get when you combine them.
If both H and G exist, then H+ must exist as well. This is equivalent to saying that if H+ doesn't exist, then H and G can't both exist. The video shows that H+ doesn't exist, so, as I said, either H or G must be impossible as well. However, we know that G can exist, meaning H (the initial halt detector) can't exist.
I just saw that there is a new breakthrough related to this problem but I don't know what it is.
This comment section needs to take more math classes.
dork I understand all of this more pristinely than most people who have a degree in physics. I barely use the language of math.
Your opinion doesn't matter.
+dork "More" is a comparative term. More than zero? More than one? Five? Ten? Twenty?
@@Agent1W he meant "more meth"..
@@DrBrainTickler Living example of the dunning-kruger effect.
What does it have to do with math?
But where did these extra bits come from at 4:10 to make H+? Is it just some counter example? You just tacked on some "negation computor" out of no where. Why?
Am i missing something here? So we assume that H solves the halting problem, and we then proceed to show a contradiction by showing that H+ doesn't solve the halting problem when you feed H+ into itself. How does this contradict the assumption that H solves the halting problem. We only showed that a modified version of H, namely H+ doesn't work.
it's not that H+´doesn't solve the problem, H+ doesn't even try to
it's that H, as PART of H+, fails to predict H´+'s result
For any machine H that claims to solve the halting problem, you can create a machine H+ for which it gives the wrong result, thus showing that H doesn't work for any machine
you can imagine H and H+ next to eachother, feed H+/H+ into H first, then into H+
No combinations of the two possible results of each machine give you a logically consistent result - thus there exists no H that can predict a H+
***** Upon further reflection it makes perfect sense to me now, there must have been something in his explanation that just didn't sit right with me at first.
Hey Mike LaValley
I seem to be in your former position. I can't quite wrap my head around his explanation.
H can tell whether any program P will halt or not on any argument I.
H+ does the SAME, it just also does the opposite afterwards.
So he says he’s feeding H+ into itself, why can’t H handle that?:
H is to examine H+(1) and H+(1) figures out another H+(2) system will halt (because the H part of H+(2) said it wouldn’t halt), H+(1) won't halt (again because H+(2) did halt) and H will say no, which is correct.
And vice versa.
but H+(1) and H+(2) are the same machines that get the same input.., if they get different results that means the machines don't work
(which they don't, they can't, there's no such H that works for any machine)
H+ get's the wrong answer because they are faulty, but H isn't.
I have a point of disagreement/confusion. In the final problem you presented that causes the contradiction, H+ takes as an input two instances of H+, but loops on forever iff H+ halts on a single input instance of H+, and halts iff H+ does not halt on a single input of H+. So what's actually happening is that H+ is running forever on two inputs H+ and H+ when H+ halts on a single input H+, and vice versa. No two opposite things are occurring at the same time, so no contradiction so far.
Obviously this can easily be amended by changing H+ to take only a single input, and then feeding those two inputs into its built in machine H.
My peasant mind needs more or better explanation. Because to me it just sounds like the paradox problem has nothing to do with machine h but you just added the h+ onto it to force a paradox out of it breaking machine h
The point is that H+ is so easy to add, if you had H then you could instantly make H+, but if H+ cannot exist then there's no way H could exist, because if H exists then H+ can easily be made from it.
Like if there were such thing as indestructible bread, I'd easily be able to make a indestructible sandwich by slapping 2 pieces of bread together, but if I can prove that indestructible sandwiches cannot exist, then either sandwiches are not made of two pieces of bread or there's no such thing as indestructible bread.
NoRotation
I still don't quite get it.
Let me explain: There are three parts to this: a detector H, a program to be tested P and an input i.
We assume that H(P(i)) will give a meaningful result.
We then build H+. H+(P(i)) will not necessarily give a meaningful result - when it terminates, you have an answer, and that's great, but before it does, you don't know if that's because it's takes a long time and isn't done yet or because it found the answer and is looping to show it to you. H+ is not a functioning detector - unless you have another detector H that can determine if it is "looping as output" or still evaluating input arguments.
So what about H+(H+) (presumably with some other input just to get it started, so it's actually H+(H+(P(i))))?
H+(P(i)) is the input, and that's fine. It may be a rubbish program, but there's no rule against that. But the "other" H+, the one that actually does the evaluation, is an unfit-for-purpose program, so it won't give us a useful answer.
So what will H(H+(H+(P(i)))) say? It will not be undetermined, it will say "loop infinitely". It looks at the whole thing - and will detect that at least one part of it (either the inner or the outer H+) will loop.
So to me, H+ seems not impossible, just not terribly useful. I can add perfectly valid code to almost any program that would ruin them beyond recognition (trust me), but that doesn't prove that they couldn't exist to begin with.
Snagabott You're not thinking in the ideal setting, this machine takes no time to run, it instantly returns an answer, so you know whether or not it's looping. Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration to show that an essentially functionally identical machine cannot exist.
NoRotation
"Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration."
It's not trivial at all. The output is radically altered. Output is ultimately what matters, not what happens inside - you can have the most beautifully complex and advanced bit of code in the world, but if you add another bit of code that intercepts and scrambles all output from it, it becomes worthless.
Snagabott Except this doesn't scramble it, it's still completely unambiguous what the output is. Furthermore the algorithm that is suppose to check the programs has not changed except for the output stage, however the alteration to the output demonstrates that the algorithm cannot possibly reach a valid output and therefore the algorithm has failed.
I don’t get how logical entailment is the same as halting problem.
Isn’t entailment an NP-complete problem like SAT? Anyone to clarify what the speaker meant by that?
Consider the following:
"This statement is false".
"Does the set of all sets who do not contain themselves contain itself?"
In both cases, you get paradoxes; if it's true then it must be false then it must be true and so on forever... And likewise, if it contains itself and only contains things that do not contain themselves then it should not contain itself which means it should contain itself and so on.
My point is this; if ever you try and do logic on a statement or question whose answer depends on the result of said logic, it's easy to produce a paradox. That doesn't mean that your assumption that such a form of logic can exist is invalid- only that you can't apply it to itself in a particular way; it would be easy to produce a program who responds to "All cats have seven legs" with "That statement is false" or one who responds to being asked "Does the group of all groups whose name contains the letter 'e' contain itself?" with "Yes".
So I understand that feeding the machine into itself is one counterexample, i.e. you can't use the "halting problem calculator" machine to calculate its own halting ability. But: can it be used to calculate the halting ability everything (or almost everything) else?
It could calculate the halting ability of many problems correctly, but there's also an infinite number of inputs where it's wrong. So no, it cannot correctly calculate the halting ability of almost everything.
ruclips.net/video/macM_MtS_w4/видео.html
Here, why is he making the machine loop forever if answer is yes?
He's creating a contradiction. He originally started with the proposition that there is a program H that can solve the Halting problem. Using only valid transformations he created a new program H+ that if run on itself has a contradictory output like "If H+ halts then it doesn't halt. If H+ doesn't halt then it halts" (in both cases H+ both halts and doesn't halt at the same time). Such a program cannot exist. This means something we did must be wrong. Since the transformations are all correct the problem must be our original proposition that there is a program H then can solve the Halting problem. So the conclusion is that our proposition is false and there cannot exist such a program H that solves the Halting problem.
This method is called proof by contradiction. To prove a statement you first propose the opposite. Then you try to construct a contradiction like "1=0" or "A and not A". If you are able to construct a contradiction with only valid transformations you have proven that your proposition is false. If your proposition is proven false then your original statement is proven true.
I understand why the output at the end is contradictory, but I don't understand why the transformations that he made in the beginning (i.e. turning H into H+) are considered vaild. I'd really appreciate it if anyone could try to explain this to me! I really want to understand what I'm missing in my understanding! Perhaps my inability to grasp the validity of the transformation made to turn H into H+ is due to my weak background in mathemtics; thanks for your help!
Basically anything you can construct is valid. Take a real world analogy. Imagine if you give me an engine "E" of some kind which you say runs fine. Then all I do is add a couple of gears and brakes without modifying what's inside E. It's "valid" in the sense that there's no logical reason why I shouldn't be able to do that. I call the whole thing "E+". However when I turn on E+, I get something that both runs and stops at the same time. The logic is, since I haven't done anything that could possibly be a contradiction (adding gears and brakes can't create contradictions), then something must be wrong with your E to start with.
3:55 halting problem start
4:42 feeding H+ in itself; Does H+ halt given input H+?
you should feed h+ to h not h+ to h+ because h+ is a modified machine to reverse the output real meaning.
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.
Hmm the idea comes into a bit better focus like that. But why do these machines need two inputs?
@@foreverseethe It takes the machine and the input that the machine would be given. It's possible for a machine to loop forever on one input but halt on another.
I don't understand. Don't you need to define the program and it's input to determine if the machine will halt?
The inverse halt machine has been inserted into itself with no input.
In my mind, this would contain an empty program, which would halt.
This means the input would inverse, and therefore not halt if ran with this input. The top level machine would inverse this, and then halt.
Im assuming I'm missing something?
Wouldn't this imply that it is impossible to fully simulate a universe? Because you have to use a computer to simulate a computer created in that universe, and then simulate if it will halt or not. So we are back where we began.
It's not necessary to simulate it in real time.
You don't need to simulate if it will halt or not. You just need to simulate the next step in accordance with the next step of the universe. It doesn't matter if it would never stop. You're running the program anyway.
You dont have to simulate if it will halt or not because the simulation will NEVER have an infinite amount of time.
Input of that hypothetical machine is program and input then how can we feed it with a yes/no ans(that of H+)?
could he be more abstract ?!
Star billions of programs all doing different things based on the same logic. abstract is the only way to learn the wide view instead of per program.
Im not seeing it. Turing was supposed to have proved this in general (for any hypothetical machine). This example uses a partially specified machine. So how does the proof work in general and not just for machines specified in the manner of “+”?
Star Trek would still make a device like a "halting compensator" or something to sort this mess out.
Turing's 'decision problem' is related to Godel's problem of 'undecidable', in which an algorithm of finite axioms leads to undecidable conclusion, while an algorithm of infinite axioms leads to a decidable conclusion.
+Naimul Haq Don't forget that Turing spent time at Princeton. Although he worked with Church and Von Neumann, he knew Kurt Godel and if I recall Andrew Hodges bio they had some discussions and were well aware of each others work.
Peter Walker
I am sure they were. Einstein took great interest in Godel's work.
I'd like to suggest to everybody on this comment section the reading of "Goedel, Escher, Bach: An Eternal Golden Braid" by Douglas Hofstadter. Great book very funny and interesting.
Why @5:06 does an answer of yes make it loop forever? You seem to have your answer at that time. If the output you wanted is either yes or no, It dosent matter if it says yes numerous times or once.
We are all going a bit too mathematical here. We've just proved one case, where the machine won't work. Sure that's enough to prove that it (the machine) isn't a universal solution to the problem it was designed for, and hence it is mathematically non-existent. But for all practical purposes, there is possible that a machine can be constructed that could solve the halting problem for every case *but* this. In practical scenarios, you wouldn't wanna test the machine against itself anyways. So, for me atleast, a practical Halting machine is still not impossible.
I know this is a proof by contradiction, and it works cool only when you need to be absolutely sure that each and every scenario is covered. It's like in physics, some formulas/theories work under some circumstances. The formula for gravitational potential energy (mgh) is only valid for height 'h'
I enjoyed this video. I appreciated the deliberate pacing of your explanation.