I wonder if it's your channel being recommended to people recently that inspired you to continue making more videos or something else. Either way I am glad that you do it, keep up the good work!
Note: that we might make a program that can IN SOME CASES predict whether an algorithm stops or runs indefinitely. In all cases-no, it’s proven. But in some cases-possible.
Here's one of my favorite anecdotes when it comes to the halting problem. Consider the following program: X = 1 Do Until X = 0 X = X / 2 Loop One of the stipulations of an "H-solver" is that the Turing machine you're running the programs on is perfect at what it does (meaning, it has no bounds or constraints, and has infinite memory space). On a perfect Turing machine, that which we're writing the H-solver for, this program would never halt, as there exist infinite numbers between 1 and 0. However, if we were to run this program on any computer which actually exists in the real world, this program would halt, as the value of X would eventually round down to 0 due to the constraints of the data type. Thus, if a perfect h-solver did exist, it wouldn't give us any meaningful real-world information about this program! It is self-evident that a perfect Turing machine cannot exist, and it follows that an H-solver for a perfect Turing machine also cannot exist. But the question remains: Can there exist a "practical" H-solver which works for any system with well-defined boundaries? If so, which boundaries are necessary to know in order for any given algorithm to be H-solvable?
Watching this dude's content I feel like he deserves a play button specifically for college professors and tech school instructors using the video without giving credit/compensation because it's better than anything they could do.
Yes, the proof is only applicable *in general*. For some cases the problem is trivially easy to decide, and for many more cases with good enough accuracy. It seems this video cared more about theoretical proof than practical application.
@@nisonatic That's still what I would call a general approach. For specific pieces of software, the halting problem does not exist. Think about trivial examples like hello world. We don't run general software on general hardware but specific software on specific hardware, so the problem exists in theory, but not so much in practice. Code analysis can help, adding 'max attempts' breakout conditions to otherwise infinite loops for example.
Correct. The Alan programming language is a perfect example of this: it prohibits runtime-bounded loops and recursion from even compiling, which prevents the creation of infinite loops in the first place. With these restrictions in place, the Alan compiler gains the power to statically reason about the behavior and performance of its programs just by looking at the code itself.
@@StephanTrubedoesnt this contradiction proof, only prove that there are atleast one circumstance where the halt program will fail. (I see it as halt will either go into a infinite loop, trying to get the resulting condition or it will recognize that it will go into an infinite loop and therefore say that the program would go on indefinitly. The opposite program is just a way of reversing the answer, so we shouldnt take its false result as wrong, because if it indeed does the opposite the result should come out wrong if everything is working correctly!?). Because this is a computer working with instructions it would need to follow the ordinary path of the input with that program to determine where such an error would occur, in doing this it would get stuck in the infinite loop. Its just like if we created a program that determined how many rows of code that would be run with a specific input, the opposite program would break that too regardless of how we designed it.
@@Wonders_of_RealityBecause that's not the point. The Halting Problem is meant to prove that there are problems which computers cannot solve. It is not about whether a fairly accurate halt-predictor can be created or not.
@@MrDifsh That’s actually what matters. We care about what’s possible. Psychologically, just for encouragement, it makes sense to stress that computer scientists can create an algorithm that will, in some cases, determine, whether a program will halt or not. Hey! Maybe it’s even possible to write a program that can evaluate the probability of halting! Mathematicians should cheer up a bit.
Great video! I do have one question that seems to always enter my mind whenever watching these sorts of videos on The Halting Problem though: As states at around 5:55, it’s not possible to construct a program that detects halts IN GENERAL. May I ask if there are some “practical constraints” that do allow us to construct such programs? What “meta constraints” must he met in order to choose some system of constraints? (i.e., (A and B or not C) or (not A and not B)) I never seem to find an answer to these questions and don’t really know where to look. I would appreciate any support!
All loop detection is customised to the nature of the program. You have to track some things that your program does, called metrics, and decide what kind of behaviour in those metrics would demonstrate a loop. Then you have to constantly check those metrics against the rules you write, and tell it to break the program if loop-like behaviour is detected. The problem is that you're only going to spot the loop if you've set rules and metrics that catch the loop. There is no exhaustive list of rules that would catch every loop, or the Halting Problem would be solved. And if you add too many rules to check, then you're going to waste a lot of computing power checking for behaviour that doesn't exist in your program. A general catch rule, like never run a program for more than a week without breaking automatically, has good value in terms of catching loops without breaking slow not-looping code too often. But having to wait a week to find out the answer is not practical in many debugging scenarios.
I have personally had the idea to have the "halting function" perform a state-based analysis which checks to see if there is a condition where the input program would end up in an identical execution state to one previously seen. I don't know how the IntelliJ function works but I would hazard a guess as this is likely the solution. If it finds a path that results in an execution state that was seen before, you know the program will not halt because it has made a full loop with no possible condition for avoiding another iteration of that loop. The trick would be figuring out how to handle external inputs during runtime (things like user input like stdin, hardware information, sensor/signal information etc). The program would likely need to analyze how the external input affects the runtime-state of the program and if there isn't a possible input that breaks the runtime out of a state cycle then it reports a "no". This hypothetical software would then also need a ternary output to include something like "I can't answer this"/"This is a contradiction" for self-reference cases.
1:49 wdym? Never reach negative 1 64 bit limit when you get passed that it will flip back to negative number and eventually reach negative 1 well.. you can't do that with python also depends on architecture
Comments like these are what remind me why so many people still can't understand this incredibly simple proof. Why are you assuming that the counter will overflow? Why do you assume it's even able to? This is a theoretical proof that's applicable to any computational model, not just the computers we've developed.
But is it possible to make an algorithm that can determine whether a program will run forever in all cases EXCEPT when evaluating a program which contains itself? That seems essentially equally practically useful
@@WolfiiDog13 Like, if too many operations happen and no frames are showing? Also, it's 100% stuck if the program pointer and memory are the same at some points in time, and a stuck program will ALWAYS do that if it doesn't have infinite memory (or program?) which means that this machine... can... uhh... Yeah I got confused a little when watching the video, but that's probably my fault.
That's exactly what I thought. It seems to me that altering the Halt algorithm so that it refuses to evaluate a program that refers to itself would be enough to solve that contradiction used to prove the assumption is false.
Yes of course it’s possible. These programs are what we call modern operating systems. And they work most of the time ….. except when they get it wrong and the system hangs. The point here is it isn’t impossible to handle computers about to hang. It’s impossible to solve the issue with 100% certainty.
we are giving the holt program a *program and input(number) and the *program start loop until x=input but in 3:18 we gave holte program the *program as input. what should happen in this situation?
The more I think about this, the less it feels like a solid proof. What you've proved here is more that OPPOSITE can't exist and will error out, not that HALT itself can't. Like I can determine if something is true or false, but I can't say "This statement is false." Being self-referential can lead to paradoxes, but that doesn't make other uses impossible.
Imagine HALT can always answer a yes/no question correctly. Imagine OPPOSITE is the paradox: "This statement is false". OPPOSITE can exist, as you can reference it as a statement. "Running" it, like giving someone the statement, they will say that it's a paradox. But since HALT can only say yes or no, it will always be wrong. This means HALT cannot always answer a yes/no question correctly. Contradicting the first statement. However, there are many other programs that can detect infinite loops, etc. But this video focuses on the halting problem only.
You are always allowed to create an opposite program if a halt program exists. Like how you can always add 1 to a number to get another number. We know the rules that we are adding is allowed. The fact that you can say paradoxes like "this statement is false" is exactly the crux of the proof that the halting problem can't be solved. Solving the halting problem involves creating a program that can describe itself, and all programs that depend on it. But a contradiction happens when you realize that a program can't describe a program that is designed to do the exact opposite of that the original program would say.
Yeah, it was just a matter of me looking at it from the perspective that some form can exist while it seemed like this example was meant to disprove that, but that isn't really the point. I can make a program that determines halting of other programs, but, what I can't do, and no one could ever do, is make a perfect program that always determines halting of other programs. So, while a particular use case can be fulfilled, the general "halting problem" cannot be solved.
The thing is, you are correct, AND THAT IS WHY THIS PROOF EXISTS. The halting problem is proof that a system without contradictions CANNOT EXIST. You cannot make a system of logic that does not, in some specific way, contradict itself. The Turing proof is answer to the Decideability Problem, and the answer being: No, you cannot have a system in which every problem is decideably false or true.
While I understand that there can be important technical applications of this, what always gets me is that we (humans) are actually pretty good at figuring out whether a program will terminate. We can read the code and think critically and conclude whether a program will halt or not. Can we solve ever possibly version of the halting problem, of course not. But we are pretty darn good at it.
Can you do so for the following program? n = 0 while (1){ n += 1 seen = [ ] x = n while (x != 1){ if ( (x % 2) == 0 ){ x = x/2 } else { x = 3*x + 1 } if ( seen contains x ){ HALT() } seen.add(x) } }
It doesn't though. It's the input, it's not running. Having a program stored on your hard drive doesn't require it having an input, so why would using it as an input require that?
I feel like there would be three options: a) the program halts -> HALT() returns true, b) the program loops forever -> HALT() returns false, c) there is a contradiction -> HALT() crashes because it can't decide Also, at 4:50 you pass the OPPOSITE() code to HALT() with OPPOSITE() as an argument, but the result would be indeterminate not because it's a contradiction, but because the OPPOSITE you passed along is missing an input! (since you're only passing the code)
@@jpalz no, the proof proves that it is not possible to write a halt program. a "non-perfect" halt program is just not a halt program, it is a different program.
@@maskangel It's similar to the "universal set" paradox. A set of all sets must contain itself, but that can't be possible. But a set of all sets "except itself" is possible. A program which perfectly determines whether a program will halt is impossible, _ONLY_ because it may fail when self-reference is involved. Of course that is correct, it just seems like a cheeky answer. By that logic, a lot of programs are impossible to write. Just about every program will have some potential flaw when you apply a rigorous enough scenario. Consider a program which reads the exact color of an image to 1-bit accuracy. This is also Impossible, because there might be situations where the camera fails, or the lighting is off a little bit, etc. So would we say "It is impossible to write a program which can read colors"? No. It would be reasonable to say "It is impossible to write a program which can PERFECTLY and unfailingly read colors", but what's the point of that statement? So, "It is impossible to write a program which can determine with perfect accuracy whether a given program will halt" is a true statement. But it feels like an academically manufactured dead-end, and I hate it.
"Can you write a program which will perfectly add two integers without error?" "Nah." "What? Why not?" "Well, if you feed the input a string then it will give an error, so it's impossible." "So just check that the inputs are bother integers before adding them" "But then it won't perfectly add two integers without error.." Does that sound silly?
while true, it is important to know that while the halting program cannot tell in some cases if the program will halt, it can in other cases determine if the program will halt. Which is why your code editor sometimes will tell you that your code has an infinite loop in it.
I know it is not quite the same thing, but in 6 minutes this pretty much explains the core of the closely related goedel's incompleteness theorem - something that "Goedel, Escher, Bach" took about 2 months of reading to explain.
I'm not following, if we input Opposite into Opposite, doesn't the first Opposite simply lack an input, and therefore wouldn't run? Or am I missing something?
you're right, the proof isn't formal enough. here's a version that avoids this issue: imagine a program H that given a program M and input w can determine whether M halts on w. create a program G that takes a program M and runs H(M, M) now create O which takes input M, runs G on M, and does the opposite of its output. now run O on O. G will run H on O, O so H will run O on O. if it halts, H and G will say halts, so O will run forever on input O, so H was wrong. if it runs forever, H and G will say runs forever, so O will halt on input O, so H was wrong.
No? Opposite is a file and a program. When you put a program like 'minecraft' as an input into a program like 'winzip', to turn minecraft into a zip file, you don't need to run minecraft at any point in the process. The same applies here. Opposite is a program that can accept other programs as inputs, just like winzip. You can also put winzip into winzip and encounter no issues. Not the same copy of winzip, since windows prevents running files from being modified to avoid any issues, but this isn't an issue with the 'opposite' program. Just have two copies of 'opposite', and feed one into the other. No issues.
Really nice animations! It was nice to visually track the explanation. I would like to add that this proof is in the same realm of absurdity as an O(1) algorithm that takes 13 billion years to run, Godel's unverifiable systems and many other paradoxes. Fun head-scratchers, but practically useless.
@@naturegirl1999 Me too. Afaik it doesn't exist though. There are a lot of these "Proofs by contradiction" in math that use self-reference to make some concept blow up in your face and while I get the mathematical rigor and all it just feels like a cop out. It's similar to the set of all sets that do not contain themselves. A set of all sets, by definition contains itself as it is a set, then adding on the stipulation that it doesn't contain itself seems to me about as useful as asking for an orange that isn't an orange. I understand the reason is to show incompleteness in a rigorous mathematical system but it seems manufactured to contradict itself and draw a conclusion that doesn't really help us solve anything. How does it benefit us to know that math is incomplete because a few fringe cases that aren't even useful anyway don't work? Isn't it enough to know that math works for most cases, and the ones that don't will show a clear contradiction? Does it matter that math is incomplete? Back to the halting problem, does it matter that it can't handle self reference? Couldn't we propose a ternary output "does it halt" function that says yes, no, or this is a contradiction that actually works?
@@nightfox6738 oh yeah, adding a “This contains a contradiction that works” seems like it would fix the issue. Although I’m not a mathematician nor am I a good programmer. When I say “fix the issue” I mean makes a program that is useful even in the case of contradiction, if a program were to contradict and halt, then a “Yes”, would be sufficient, if a program contradicts itself and still runs, that sounds like useful info, so that contradiction removal while keeping it functional doesn’t mess up other programs that use results from the first program. Am I making sense? If not, clarifying questions are welcome and encouraged. Like Google Bard and ChatGPT, I like ensuring people understand me.
This is your first video I found confusing. I’ll come back later and edit this and see if it was just not a good day or me or if it’s still confusing. Edit a year later: Yeah 3:18 is a bit rough, but paying attention / slowing down, it's not complicated. I probably had a rough day
Hi, I had the same doubt. The key point is the assumption that exists a program/algorithm that ALWAYS works with ANY input. Since it's demonstrated that by passing the program itself as input creates a paradox, such a program cannot exist, and sometimes computers are stuck in an endless loop.
solution i thought up: it runs forever during the HALT() function, since every time HALT() comes up with a solution it will use that solution to compute more
There isn't a solution, this isn't a puzzle to solve. It's a proven fact. The video is explaining this fact to you, not challenging you to disprove it.
You almost got it right! Your explanation of the (Alan Turing's) solution is excellent! However the problem is poorly defined (can a program determine halting for ANY program). Further more, your conclusion is also wrong. This does not mean that halting cannot ever be determined by a computer. Kudos on the great explanation of the solution though.
So, to avoid contradiction you just need a third possible output for halt program - "maybe". And it still could be useful for most cases when it can reach definite conclusion.
“Maybe” state wouldn’t solve it because the “maybe” state itself can be used to create a contradiction. What if I defined the OPPOSITE program to halt with absolute certainty (let’s say I call exit()) if HALT(x, x) is “maybe”? Well, if HALT(OPPOSITE, OPPOSITE) is “maybe”, then OPPOSITE will halt with 100% certainty as I just defined as above. This implies that HALT(OPPOSITE, OPPOSITE) is also YES, which itself is a contradiction.
When a program is executed, it either halts(HALT return "yes") or loops forever(HALT return "no"). OPPOSITE(OPPOSITE) halts if HALT(OPPOSITE, OPPOSITE) returns "maybe", so the HALT conclusion is wrong and should return "yes".
Weird thing is, if you restrict the program size, like "for a program with less than 500 characters, decide if it halts" then the problem IS solvable, at least on paper: You just make a lookup table for every possible program and the answer Yes/No. The unsolvability is because we're trying to make a program that solves halting for any sized program.
While a predictive program might not be possible for any program, a detection program could be written. If a program reaches state X, then it must perform the action associated with X. Every time it reaches state X it performs the same action, bringing it to the same next state Y. If the detection program detects that the program is in state X again, and no user input or random chance has been used since the last time it was in state X, then it must perform the same series of steps and eventually arrive at X again. That would be an infinite loop and the detection program would notice that the program is stuck. Whenever random generation or user input is called for by the program, the detection program can use the state immediately following that as the new “state X” if we get back to that point without user input or randomness then we’re stuck. The detection program could detect the loop and either alter the state to try breaking the loop or just force the program to end.
Except this would not work for cases where the program does never reach the same state twice. Like the program example program in this video - it increments counter at infinitum - the state does not repeat. And even if it did, the memory needed to record all encountered states even in fairly mundane programs is untenable.
@@KohuGaly What counter is incrementing? Also you only ned to remember the state immediately after user/random input or at the beginnining of a recursive function. If the computer is in a loop, it only takes one state to notice. Any point during that loop will suffice, so all we need to do is guaruntee that when we take a snapshot will be during the loop, and the previous snapshot can be discarded. If we take it too often we might be taking multiple states within the long singular loop and never notice, but if we wait to long to take a snapshot then we could get stuck in the loop early on and not know until significant time has passed. We can also ignore any cases where user input or random chance are taken because that would be a way to break the loop and therefore it isn't infinitely looping. We can check recursive functions and for/while loops before runtime, things like while(true) without a break condition or a recursive function calling itself without a countdown or end state check. Many code editors have features like that, which will notify you if a section of code will never execute, usually because it falls after a written infinite loop. Essentially, there are trivial loops that can be detected by the compiler and false loops that are "supposed" to happen because rng or the user want them to happen. Think of it like how a graphics engine calls a draw command every frame, it has to loop that but isn't actually stuck in a loop because it uses user input. Just because the user chooses to sit on the menu screen for hours doesn't mean we're stuck. So after each call of a loop like for or while, or after a recursive function call, and we can take the state immediately after user input or rng, because a loop that includes user input isn't a problem. We also don't need to memorize every past state, we already narrowed down timings of when notable states are, but if we find reason to take a new state we can forget the previous states. We take a state when we suspect we might be in a loop, whatever the previous state was, either it isn't part of the loop and we don't care or it is part of the loop but we're about to know from our newer state regardless. Essentially, the first time we call any of these potentially looping lines of code, we take a snapshot and every cycle we just compare the snapshhot with the current state. Only one state needs to be saved, and a single boolean comparison between the two takes minimal resources even with the high frequency of checks. If some sort of counter is incrementing between iterations of the loop, it's just a much larger loop. Eventually that counter will overflow and wrap around to 0 again and then we've found a match to our snapshot. That's assuming the counter isn't being used for a breakout condition.
@@anthonycannet1305 Not all counters can overflow. It's pretty trivial to create a counter that can increment forever (a Sting in most languages can do it). This is not some fringe example either. It's fairly common for programs to record a log, which is also a part of the state, and the log never reaches the same state twice, because it only appends. That's actually a big part of why halting problem is unsolvable. It's possible to create programs which never enter the same state twice, because they have unbounded amount of memory to store states. The "unbounded" part is a reasonable approximation of a real modern computer, when you take into account stuff like external storage. Loop that includes user input is still a problem. It is not guaranteed that the user input can break the loop, or has any effect on the loop whatsoever.
I mean, cant you make an imperfect one that would throw an error for a contradiction (Maybe run it 3 times or something and if it changes then throw an error) but would check if: 1: The program has a loop that is conditional on something that is changed in the loop 2: The program has a loop that its conditional statement that changes in an increment that will eventually reach the condition Meaning "while true do end" would fall under 1, making it an infinite loop, or "while x ~= 0 do x = x + 2" and x starts at an odd number.
Technically, if the input is -1, the program will eventually halt. This is because once you reach max integer size, it will revert to min integer size and eventually increase to -1.
Its pretty abstract programming we are talking about, so I am not sure there will be any "maximum possible integer", it can really easy run to whatever integer
Technically you cannot tell because you don't know what architecture this is and how the instructions are interpreted. Some types don't overflow (such as IEEE 754 floating point values). You can also build such an architecture or run the program in such an environment that doesn't have integer size limits.
Also, signed integer overflow is undefined behavior in some low-level languages. For example, a C++ compiler is allowed to optimize for (int i = 0; i != -1; ++i) into an infinite loop, because the optimizer is allowed to assume that signed integer overflow never happens.
Ok so if so far loops we can create an halt program it's easy for that but than there will be bug of just you describe but other than that it would work as intended
If you made a plate called 'the indestructible plate', and I proved it wasn't indestructible by dropping it on the ground, would you saying "it's indestructible as long as you don't drop it on the ground" suddenly make it indestructible again? So, too, is the machine not possible. Just turning your head and looking away from the mistake existing doesn't suddenly mean it can't make mistakes.
I always hated how it needs OPPOSITE to negate the return value. Always felt artificially manipulated to be more complicated and almost begging to contradict itself. I'd lose track of thought and got angry. I didn't believe in it. The diagonaliztion argument as in Gödel or Cantor or Russel however always made sense to me. If you struggle with it like I did, imagine this: OPPOSITE doesn't negate but returns the same as HALT, then there are two cases: 1: It returns yes, original algorithm eventually halts 2: It returns no, it won't halt So just an extra layer to HALT itself. But it doesn't have any meaning. HALT itself is not proven to be correct. It is just assumed to exist and the proof is build upon this supposition. The further you try to "decompose" this proof and and observe it and try to catch where the essence lies, the weirder it becomes. It is like casting your fishing line and "waiting to see what could be landed" . Only to afterwards realize, it was impossible to go fishing here in the first place. Humans, I think (or me at least) have a hard time grasping that last "backwards" step in causality, the existence of something would lead to a contradiction somewhere else. This contradiction was provoked by behaving completely normal but under the circumstance that this certain something exists, suddenly the world would fall apart. Ergo this something cannot exist. This is the crunch point for me, which feels unsatisfying sometimes, but this is where it lies.
I’m not a computer person but for the most part computers only allow acceptable values. If a computer asks for an input and you put -1 or q or something that it doesn’t accept, it won’t run will it?
The legend has it - that green bot has been walking ever since, from the moment of big bang until the end of the very existence. A true oblivion program known to our mankind. The end! 😂
What if you forbid the Halt program analysing itself or the Opposite? It's not a useful analysing program if you intentionally ask it to output the opposite of what's it'd say normally.
theoretically, you could end up giving it a unique but functionally identical version of the halt program, so it would be read as if it were a different program, but outputs the same values also, you could end up accidentally programming an Opposite function (thinking of the many times I've misused != unintentionally) which means the halt program wouldn't be able to analyze a legitimate but poorly written program that just so happens to output the opposite of the input
The issue is not the halt program per say, but the fact that a computer can simulate another computer (including itself). This is not some fringe case either - it's actually very common. The browser you're watching this on probably has Javascript interpreter embedded in it.
Then Halt can get looped forever in some other situation. Unless we analyze it with itself we can't be sure that it won't run forever given some other input.
Every implementation of a Turing machine runs on a non-Turing machine (that is, a system with limitations), since there is no such thing as an infinitely nested Turing machine. While it is not possible to write an H-solver for Turing code, it is possible to write an H-solver for any system which implements a Turing machine. Better yet, all computer code ultimately comes down to a real-world physics simulation, which is very theoretically solvable. I never understood why people obsess over the abstract H-solver. I get that generally in math, if you write an abstract equation for a problem, it can solve any and all individual instances of that problem. But this is not the case with the H-solver or the abstract Turing machine. For instance, consider a program which repeatedly divides a number by 2 and halts when it reaches 0. If we had an H-solver for a theoretical perfect Turing machine, it would say that this program never halts. And yet, this program would definitely halt when run on ANY real-world system when the number gets so small that the platform rounds it to 0. You might try to resolve this discrepancy by saying that the H-solver needs to understand not only the code, but the code's IMPLEMENTATION, in order to do its job. But the moment you say that code needs to bring its own implementation with it, the whole idea of a Turing device breaks down and becomes irrelevant. Code A no longer equals Code A.
Fascinating. I ! = expert, and I'm curious if any practical work arounds have integrated a halt detector with an AI model that's trained to estimate how humans would likely respond to or prefer to resolve an ambiguous halting situation. It seems like AI could be tasked to mitigate this intractable problem in ways that could be more flexible and intuitive than setting arbitrary limits. Again, not my field at all, so I won't be surprised if I'm talking nonsense.
I have an issue with this argument. The program Opposite (the analyzer) analyzes Opposite (the analyzed), however the analyzer has a different input than the analyzed, thus it is not contradictory that they yield different answers. If the analyzed has the same input as the analyzer, then by recursion the input must be infinite in size which could be the actual source of the problem
no, they have the same input. Opposite takes a single program as an input. The halt function inside it takes two inputs - the program and its input. In this particular case, it is given the opposite program and is asked whether it halts when it's given opposite program as an input.
Can't you put a if steps is 0 < Input then start? Also if it is the oppisite of oppisite, then that means if halt says halt, it halts do to it being oppisite of oppisite meaning it is just regular.
Let me know if I'm wrong. To me, this provement sounds like "we cannot divide a number by 0, so a general division doesn't exist". The `Opposite` program is so specifically constructed that the `Halt` has to predict it's own result in order to give a result. If we define `Halt` to be a program that can predict halting giving any program, AS LONG AS ITSELF IS NOT INVOLVED, what would be the answer?
That isn't really the focus of the video. The video just explains the proof against a perfect solution to the halting problem. Asking "but what if there was an imperfect proof?" is something tons of people have already asked, and isn't the focus of the video.
@@godlyvex5543I understand. But just like my analogy, calling a solution imperfect only because it has one singularity neither makes any sense nor has valuable applications. This video starts with a real life scenario and ends up with a conclusion that doesn’t necessarily have something to do with it. I feel like I watched a video that starts with a question “why finding prime factors of a big number is complicated” and ends with a conclusion “we can’t divide numbers by zero therefore division operation doesn’t exist but finding prime factors requires such a non-existing operation.”
@@cjrsacred What? This comment is nonsense. You described a completely different situation with no similarities and said "this situation is like that one." No, it isn't all all like that. Establishing that a general solution to always figure out whether a problem will halt or not, being proven impossible, is a fairly useful thing to know, unlike the situation you described. And what do you mean I'm calling a solution imperfect because it has "one singularity"? Do you know what a singularity is? I'm calling it imperfect because a perfect solution DOES NOT EXIST. That's the whole thing the video set out to explain. If your solution works for most things but not every last one, then it is by definition imperfect, or could also be called a partial solver.
I've always wondered about this proof because we could construct a very similar situation using simple language. Let's assume we were playing Mad Libs. The blanks of the phrases are just parameters to a function, and in many cases, the blanks need very specific types of inputs for the phrase to make any sense. Let's assume we have a phrase, "_______ is a false statement", but this blank can ONLY contain statements which actually ARE false. If the statement isn't false, then you cant see the resolution of the mad lib just like you cant see the resolution of the OPPOSITE function. So, if we create a scenario in which our resulting mad lib would read "'_______ is a false statement' is a false statement", no matter whether the innermost statement is true or false, the entire statement CANNOT compile because we have declared that it will only do so if a false statement is in the blank. But now let's recreate our HALT function as a mad lib template, "Inserting ______ into the template ______ will create a valid mad lib", where the first blank accepts ANY input, and the second blank requires you to input ANY mad lib template, then the statement will either be true or false determined by whether your desired input followed the rules of your desired mad lib template. Now we nest some statements and try to answer it: 'Inserting "Inserting _______ into the template '_______ is a false statement.' (Only accepts false statement) will create a valid mad lib." into the template "_______ is a false statement." (Only accepts false statement) will create a valid mad lib.' The important thing to notice is that you can't evaluate the outer parts first. You HAVE to evaluate if the innermost statement is true or false before you can continue. The other thing that is important to notice here is the HALT template ALWAYS containing the OPPOSITE template WITHOUT directly inserting the parameter INTO the template. So for example, if we input 1+1=2 into the innermost parameter, we are NOT directly evaluating "'1+1=2' is a false statement", as this would not compile. Instead we are placing the OPPOSITE template and the parameter for it INTO the HALT template. This means, EVEN IF the OPPOSITE template wouldn't compile with that parameter inserted, the HALT template WILL still compile, as no uncompiled statement was ever actually made, we simply asked if it WOULD or not. The same thing happens when we try to insert the result of THAT into the OPPOSITE template AGAIN using the HALT template so it must compile. Now we simply work our way up the chain. Does "1+1=2" compile in OPPOSITE? No. Does "'1+1=2' compile in OPPOSITE" compile in OPPOSITE? Well, if the previous part was no, that means HALT was false, and so HALT in OPPOSITE must be true. Remember; the goal of HALT is NOT to actually evaluate a function. It ONLY determines whether it halts or not, so if you are assuming that HALT(OPPOSITE, OPPOSITE) doesn't halt, then it is because you are actually trying to EVALUATE the result of OPPOSITE(OPPOSITE(?)), which defeats the purpose of having used HALT to begin with. Maybe some other proof exists for why the Halting Problem can't be true, but I don't see this as a sufficient explanation when it is clearly derived on a critical misunderstanding of the purpose and functionality of HALT.
What does it mean to give a program itself, or another program, as input? In the context of the video, the input to a program is supposed to be a number; what number corresponds to a program?
On a basic level, any input (wether numbers or text, audio or image, ...) will be encoded as bits, 1s and 0s. And any program code is stored in the same way. So you can say that every possible input and every possible program are both just numbers, in a loose sense.
I know that it is not possible to determine if it will halt for ALL program. But is there a category of program where it can be known ? Then the HALT code will response YES/NO/UNKNOWN instead of YES/NO, which will allow to break to paradox by answering UNKNOWN regarding the OPPOSITE program.
when input is defined using a well founded relation and the program is guaranteed to reduce the input at every step, there is a termination guarantee in fact some programming languages don't allow other recursion by default like Lean
Even if we can imagine a particular scenario where the halting program can be "fooled" by a specially written program, doesn't that mean that we could write a halting program that would solve for most cases? In other words, we could write a program that while it could never be totally sure it was correct could still determine whether the program would halt with a high degree of certainty - a "good enough" solution? It follows that if we could write such a program, our computers should be able to tell us most of the time whether our programs will eventually halt or not - simply by calculting the delta between the halt condition of a loop and the progress that the program is making towards that condition, instead of the os always blindly saying that it isn't sure.
I love how the green robot is still running when the video ends 😂
We may need to force stop him 🤖
He's fine, one day he'll overflow and reach -1
The robot was red
@@pafnutiytheartist That's what I was thinking...
wtf@@Thekingmaker
I wonder if it's your channel being recommended to people recently that inspired you to continue making more videos or something else. Either way I am glad that you do it, keep up the good work!
You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!
Note: that we might make a program that can IN SOME CASES predict whether an algorithm stops or runs indefinitely. In all cases-no, it’s proven. But in some cases-possible.
Here's one of my favorite anecdotes when it comes to the halting problem. Consider the following program:
X = 1
Do Until X = 0
X = X / 2
Loop
One of the stipulations of an "H-solver" is that the Turing machine you're running the programs on is perfect at what it does (meaning, it has no bounds or constraints, and has infinite memory space). On a perfect Turing machine, that which we're writing the H-solver for, this program would never halt, as there exist infinite numbers between 1 and 0. However, if we were to run this program on any computer which actually exists in the real world, this program would halt, as the value of X would eventually round down to 0 due to the constraints of the data type. Thus, if a perfect h-solver did exist, it wouldn't give us any meaningful real-world information about this program!
It is self-evident that a perfect Turing machine cannot exist, and it follows that an H-solver for a perfect Turing machine also cannot exist. But the question remains: Can there exist a "practical" H-solver which works for any system with well-defined boundaries? If so, which boundaries are necessary to know in order for any given algorithm to be H-solvable?
@@Strakesterrounding is not necesarilly the actual result. In python you get an out of memory
Watching this dude's content I feel like he deserves a play button specifically for college professors and tech school instructors using the video without giving credit/compensation because it's better than anything they could do.
So glad you are making more videos, I discussed this exact problem with my buddy over spring break
Glad to see you back dude! :)
It would be great if you went further into NP and NP hard problems, and their classes. Cheers! :)
It feels like we should still be able to make programs that solve the haunting problems in certain, restricted scenarios.
Yes, the proof is only applicable *in general*.
For some cases the problem is trivially easy to decide, and for many more cases with good enough accuracy.
It seems this video cared more about theoretical proof than practical application.
@@nisonatic That's still what I would call a general approach. For specific pieces of software, the halting problem does not exist. Think about trivial examples like hello world.
We don't run general software on general hardware but specific software on specific hardware, so the problem exists in theory, but not so much in practice.
Code analysis can help, adding 'max attempts' breakout conditions to otherwise infinite loops for example.
Correct. The Alan programming language is a perfect example of this: it prohibits runtime-bounded loops and recursion from even compiling, which prevents the creation of infinite loops in the first place. With these restrictions in place, the Alan compiler gains the power to statically reason about the behavior and performance of its programs just by looking at the code itself.
I don't think arming an AI with an unlicensed nuclear accelerator would be a good idea.
@@StephanTrubedoesnt this contradiction proof, only prove that there are atleast one circumstance where the halt program will fail. (I see it as halt will either go into a infinite loop, trying to get the resulting condition or it will recognize that it will go into an infinite loop and therefore say that the program would go on indefinitly. The opposite program is just a way of reversing the answer, so we shouldnt take its false result as wrong, because if it indeed does the opposite the result should come out wrong if everything is working correctly!?).
Because this is a computer working with instructions it would need to follow the ordinary path of the input with that program to determine where such an error would occur, in doing this it would get stuck in the infinite loop. Its just like if we created a program that determined how many rows of code that would be run with a specific input, the opposite program would break that too regardless of how we designed it.
Finally, a math problem that can be solved with a sledgehammer.
this video came at just the right time. my algorithm analysis final is in a week
2:44 Contadiction
never stop this channel please
I never understood these thing for many years ! this dude is a rockstar!
The best video on TH-cam. I mean, yes.
This channel is like water and air to the human being!
Thanks
Brian, thank you so much for these and CS50w videos. Your explanations are amazing
Luckily we can easily write a halting program for any specific program, just not for every program.
Exactly! Many teachers omit this optimistic thought.
@@Wonders_of_RealityBecause that's not the point. The Halting Problem is meant to prove that there are problems which computers cannot solve. It is not about whether a fairly accurate halt-predictor can be created or not.
@@MrDifsh That’s actually what matters. We care about what’s possible. Psychologically, just for encouragement, it makes sense to stress that computer scientists can create an algorithm that will, in some cases, determine, whether a program will halt or not. Hey! Maybe it’s even possible to write a program that can evaluate the probability of halting! Mathematicians should cheer up a bit.
Great video!
I do have one question that seems to always enter my mind whenever watching these sorts of videos on The Halting Problem though:
As states at around 5:55, it’s not possible to construct a program that detects halts IN GENERAL. May I ask if there are some “practical constraints” that do allow us to construct such programs? What “meta constraints” must he met in order to choose some system of constraints? (i.e., (A and B or not C) or (not A and not B))
I never seem to find an answer to these questions and don’t really know where to look. I would appreciate any support!
Sure, e.g. IntelliJ IDEA detects many silly infinite loops where the loop body does not influence the loop condition at all.
@@fredoverflow Thank you! I’ll investigate this. I am curious as to what the theoretical limits are though :)
All loop detection is customised to the nature of the program. You have to track some things that your program does, called metrics, and decide what kind of behaviour in those metrics would demonstrate a loop. Then you have to constantly check those metrics against the rules you write, and tell it to break the program if loop-like behaviour is detected.
The problem is that you're only going to spot the loop if you've set rules and metrics that catch the loop. There is no exhaustive list of rules that would catch every loop, or the Halting Problem would be solved. And if you add too many rules to check, then you're going to waste a lot of computing power checking for behaviour that doesn't exist in your program.
A general catch rule, like never run a program for more than a week without breaking automatically, has good value in terms of catching loops without breaking slow not-looping code too often. But having to wait a week to find out the answer is not practical in many debugging scenarios.
I have personally had the idea to have the "halting function" perform a state-based analysis which checks to see if there is a condition where the input program would end up in an identical execution state to one previously seen. I don't know how the IntelliJ function works but I would hazard a guess as this is likely the solution. If it finds a path that results in an execution state that was seen before, you know the program will not halt because it has made a full loop with no possible condition for avoiding another iteration of that loop. The trick would be figuring out how to handle external inputs during runtime (things like user input like stdin, hardware information, sensor/signal information etc). The program would likely need to analyze how the external input affects the runtime-state of the program and if there isn't a possible input that breaks the runtime out of a state cycle then it reports a "no". This hypothetical software would then also need a ternary output to include something like "I can't answer this"/"This is a contradiction" for self-reference cases.
@@nightfox6738 Your idea is known as "symbolic execution" in the mainstream.
I got so excited when I saw a notification that you've posted a new video. Keep us the good work
again one of those videos. Thank you sir for your efforts.
I've been watching your channel and it's been great.
Please do encryption algorithms, sorting algorithms, and history of computing.
1:49 wdym? Never reach negative 1
64 bit limit when you get passed that it will flip back to negative number and eventually reach negative 1 well.. you can't do that with python also depends on architecture
Comments like these are what remind me why so many people still can't understand this incredibly simple proof. Why are you assuming that the counter will overflow? Why do you assume it's even able to? This is a theoretical proof that's applicable to any computational model, not just the computers we've developed.
Great video! At 2:44 there is a typo on contradiction.
But is it possible to make an algorithm that can determine whether a program will run forever in all cases EXCEPT when evaluating a program which contains itself? That seems essentially equally practically useful
Well, most OSs have some way of telling if an application is stuck or not, but it's never 100% certain
@@WolfiiDog13 Like, if too many operations happen and no frames are showing? Also, it's 100% stuck if the program pointer and memory are the same at some points in time, and a stuck program will ALWAYS do that if it doesn't have infinite memory (or program?) which means that this machine... can... uhh... Yeah I got confused a little when watching the video, but that's probably my fault.
That's exactly what I thought. It seems to me that altering the Halt algorithm so that it refuses to evaluate a program that refers to itself would be enough to solve that contradiction used to prove the assumption is false.
Yes of course it’s possible. These programs are what we call modern operating systems. And they work most of the time ….. except when they get it wrong and the system hangs. The point here is it isn’t impossible to handle computers about to hang. It’s impossible to solve the issue with 100% certainty.
Unfortunately, determining whether a program "refers to itself" is equivalent to the Halting Problem.
this is the third video that I watched...finally, I understand the proof!
really really awesome easy wayto understand.
Simply amazing kindly upload more videos, and thank you.
This video is truly an asset! 💙
we are giving the holt program a *program and input(number) and the *program start loop until x=input but in 3:18 we gave holte program the *program as input.
what should happen in this situation?
Small error at 2:55, where on the whiteboard, it says Proof by Contadiction, where it should say contradiction. Other than that, love these videos.
shhh new proof just drop
@@swapbriarASMR holy hell!!
The more I think about this, the less it feels like a solid proof. What you've proved here is more that OPPOSITE can't exist and will error out, not that HALT itself can't. Like I can determine if something is true or false, but I can't say "This statement is false." Being self-referential can lead to paradoxes, but that doesn't make other uses impossible.
Imagine HALT can always answer a yes/no question correctly.
Imagine OPPOSITE is the paradox: "This statement is false".
OPPOSITE can exist, as you can reference it as a statement. "Running" it, like giving someone the statement, they will say that it's a paradox. But since HALT can only say yes or no, it will always be wrong. This means HALT cannot always answer a yes/no question correctly. Contradicting the first statement. However, there are many other programs that can detect infinite loops, etc. But this video focuses on the halting problem only.
HALT cannot exist because if HALT existed , then OPPOSITE exist too , which means that HALT is actually not halt
You are always allowed to create an opposite program if a halt program exists. Like how you can always add 1 to a number to get another number. We know the rules that we are adding is allowed.
The fact that you can say paradoxes like "this statement is false" is exactly the crux of the proof that the halting problem can't be solved. Solving the halting problem involves creating a program that can describe itself, and all programs that depend on it. But a contradiction happens when you realize that a program can't describe a program that is designed to do the exact opposite of that the original program would say.
Yeah, it was just a matter of me looking at it from the perspective that some form can exist while it seemed like this example was meant to disprove that, but that isn't really the point. I can make a program that determines halting of other programs, but, what I can't do, and no one could ever do, is make a perfect program that always determines halting of other programs. So, while a particular use case can be fulfilled, the general "halting problem" cannot be solved.
The thing is, you are correct, AND THAT IS WHY THIS PROOF EXISTS. The halting problem is proof that a system without contradictions CANNOT EXIST. You cannot make a system of logic that does not, in some specific way, contradict itself. The Turing proof is answer to the Decideability Problem, and the answer being: No, you cannot have a system in which every problem is decideably false or true.
thanks for clearing this concept to me
I always thought about why we have to wait for the programme to respond just tell if its going to work
Thank you Brian Yu!
From Harvard?
@@ytoh6408 Yup!
Great video. Also, the robots are absolutely adorable.
Love your videos!
At 2:55, you misspelled 'Contradiction' 'Contadiction' in the title.
While I understand that there can be important technical applications of this, what always gets me is that we (humans) are actually pretty good at figuring out whether a program will terminate. We can read the code and think critically and conclude whether a program will halt or not. Can we solve ever possibly version of the halting problem, of course not. But we are pretty darn good at it.
Can you do so for the following program?
n = 0
while (1){
n += 1
seen = [ ]
x = n
while (x != 1){
if ( (x % 2) == 0 ){
x = x/2
} else {
x = 3*x + 1
}
if ( seen contains x ){ HALT() }
seen.add(x)
}
}
@@CoolRubiksCube what is "seen"
@@akam9919 A list, defined by ```seen = []```
@@CoolRubiksCube Ah! Okay, thanks! I don't know how I didn't see it before.
We are using OPPOSITE as a program, and also as an input; but the "OPPOSITE as an input" needs an input, and none is supplied to it in this scenario.
It doesn't though. It's the input, it's not running. Having a program stored on your hard drive doesn't require it having an input, so why would using it as an input require that?
I feel like there would be three options: a) the program halts -> HALT() returns true, b) the program loops forever -> HALT() returns false, c) there is a contradiction -> HALT() crashes because it can't decide
Also, at 4:50 you pass the OPPOSITE() code to HALT() with OPPOSITE() as an argument, but the result would be indeterminate not because it's a contradiction, but because the OPPOSITE you passed along is missing an input! (since you're only passing the code)
You're third option doesn't work as we have assumed that there is a perfect halt program that is always right, therefore it can't crash.
@@Unreql So the "proof" doesn't prove that it's impossible to write a Halt program, only impossible to write a perfect Halt program.
@@jpalz no, the proof proves that it is not possible to write a halt program. a "non-perfect" halt program is just not a halt program, it is a different program.
@@maskangel It's similar to the "universal set" paradox. A set of all sets must contain itself, but that can't be possible. But a set of all sets "except itself" is possible.
A program which perfectly determines whether a program will halt is impossible, _ONLY_ because it may fail when self-reference is involved. Of course that is correct, it just seems like a cheeky answer.
By that logic, a lot of programs are impossible to write. Just about every program will have some potential flaw when you apply a rigorous enough scenario.
Consider a program which reads the exact color of an image to 1-bit accuracy. This is also Impossible, because there might be situations where the camera fails, or the lighting is off a little bit, etc.
So would we say "It is impossible to write a program which can read colors"? No. It would be reasonable to say "It is impossible to write a program which can PERFECTLY and unfailingly read colors", but what's the point of that statement?
So, "It is impossible to write a program which can determine with perfect accuracy whether a given program will halt" is a true statement. But it feels like an academically manufactured dead-end, and I hate it.
"Can you write a program which will perfectly add two integers without error?"
"Nah."
"What? Why not?"
"Well, if you feed the input a string then it will give an error, so it's impossible."
"So just check that the inputs are bother integers before adding them"
"But then it won't perfectly add two integers without error.."
Does that sound silly?
Awesome content Spanning Tree
I like this channel, please cover more algorithms
while true, it is important to know that while the halting program cannot tell in some cases if the program will halt, it can in other cases determine if the program will halt. Which is why your code editor sometimes will tell you that your code has an infinite loop in it.
This is mind blowing
🤯
Cute robots! Your explanation videos are the best in the market according to my experiences!
I know it is not quite the same thing, but in 6 minutes this pretty much explains the core of the closely related goedel's incompleteness theorem - something that "Goedel, Escher, Bach" took about 2 months of reading to explain.
This videos is soooo good.
Great work, thanks !
I'm not following, if we input Opposite into Opposite, doesn't the first Opposite simply lack an input, and therefore wouldn't run? Or am I missing something?
my thoughts exactly
you're right, the proof isn't formal enough.
here's a version that avoids this issue:
imagine a program H that given a program M and input w can determine whether M halts on w.
create a program G that takes a program M and runs H(M, M)
now create O which takes input M, runs G on M, and does the opposite of its output.
now run O on O.
G will run H on O, O
so H will run O on O.
if it halts, H and G will say halts, so O will run forever on input O, so H was wrong.
if it runs forever, H and G will say runs forever, so O will halt on input O, so H was wrong.
No? Opposite is a file and a program. When you put a program like 'minecraft' as an input into a program like 'winzip', to turn minecraft into a zip file, you don't need to run minecraft at any point in the process. The same applies here. Opposite is a program that can accept other programs as inputs, just like winzip. You can also put winzip into winzip and encounter no issues. Not the same copy of winzip, since windows prevents running files from being modified to avoid any issues, but this isn't an issue with the 'opposite' program. Just have two copies of 'opposite', and feed one into the other. No issues.
Hi, I love your videos! May I ask which program you use to make the animations? Is it Unity?
Really nice animations! It was nice to visually track the explanation.
I would like to add that this proof is in the same realm of absurdity as an O(1) algorithm that takes 13 billion years to run, Godel's unverifiable systems and many other paradoxes. Fun head-scratchers, but practically useless.
The little computer buddies are so cute!
Is there any proof that does not use self reference?
I’m also curious about this
@@naturegirl1999 Me too. Afaik it doesn't exist though. There are a lot of these "Proofs by contradiction" in math that use self-reference to make some concept blow up in your face and while I get the mathematical rigor and all it just feels like a cop out. It's similar to the set of all sets that do not contain themselves. A set of all sets, by definition contains itself as it is a set, then adding on the stipulation that it doesn't contain itself seems to me about as useful as asking for an orange that isn't an orange. I understand the reason is to show incompleteness in a rigorous mathematical system but it seems manufactured to contradict itself and draw a conclusion that doesn't really help us solve anything. How does it benefit us to know that math is incomplete because a few fringe cases that aren't even useful anyway don't work? Isn't it enough to know that math works for most cases, and the ones that don't will show a clear contradiction? Does it matter that math is incomplete? Back to the halting problem, does it matter that it can't handle self reference? Couldn't we propose a ternary output "does it halt" function that says yes, no, or this is a contradiction that actually works?
@@nightfox6738 oh yeah, adding a “This contains a contradiction that works” seems like it would fix the issue. Although I’m not a mathematician nor am I a good programmer. When I say “fix the issue” I mean makes a program that is useful even in the case of contradiction, if a program were to contradict and halt, then a “Yes”, would be sufficient, if a program contradicts itself and still runs, that sounds like useful info, so that contradiction removal while keeping it functional doesn’t mess up other programs that use results from the first program. Am I making sense? If not, clarifying questions are welcome and encouraged. Like Google Bard and ChatGPT, I like ensuring people understand me.
This is your first video I found confusing. I’ll come back later and edit this and see if it was just not a good day or me or if it’s still confusing.
Edit a year later: Yeah 3:18 is a bit rough, but paying attention / slowing down, it's not complicated. I probably had a rough day
Still confusing?
@@CoolRubiksCube I'm gonna watch this soon and find out
@@CoolRubiksCube 3:18 is where is starts losing me a bit if I don't slow down and pay attention. But I understand it better now. Prolly a bad day
why are we giving a program itself as an input to the halt function in the opposite program? can someone please explain..
Hi, I had the same doubt. The key point is the assumption that exists a program/algorithm that ALWAYS works with ANY input. Since it's demonstrated that by passing the program itself as input creates a paradox, such a program cannot exist, and sometimes computers are stuck in an endless loop.
Great video. Reminds me of udiprod's video in which they show the same proof.
solution i thought up: it runs forever during the HALT() function, since every time HALT() comes up with a solution it will use that solution to compute more
There isn't a solution, this isn't a puzzle to solve. It's a proven fact. The video is explaining this fact to you, not challenging you to disprove it.
You almost got it right!
Your explanation of the (Alan Turing's) solution is excellent! However the problem is poorly defined (can a program determine halting for ANY program).
Further more, your conclusion is also wrong. This does not mean that halting cannot ever be determined by a computer.
Kudos on the great explanation of the solution though.
Can we write an program wchich tests if the halting problem can be solved on a given program?
Yes, it is only unsolvable in general. For specific programs, solutions exist.
So, to avoid contradiction you just need a third possible output for halt program - "maybe". And it still could be useful for most cases when it can reach definite conclusion.
“Maybe” state wouldn’t solve it because the “maybe” state itself can be used to create a contradiction.
What if I defined the OPPOSITE program to halt with absolute certainty (let’s say I call exit()) if HALT(x, x) is “maybe”? Well, if HALT(OPPOSITE, OPPOSITE) is “maybe”, then OPPOSITE will halt with 100% certainty as I just defined as above. This implies that HALT(OPPOSITE, OPPOSITE) is also YES, which itself is a contradiction.
When a program is executed, it either halts(HALT return "yes") or loops forever(HALT return "no").
OPPOSITE(OPPOSITE) halts if HALT(OPPOSITE, OPPOSITE) returns "maybe", so the HALT conclusion is wrong and should return "yes".
This can work. A trivial example is a program that returns MAYBE for all input. It'll always be correct.
@@jweipjklawe4766 it won't predict if any machine will halt or not
So its not the halting machine
@@olixx1213 Maybe it is the halting machine, maybe it's not
Some says the green robot still runs to this day..
Weird thing is, if you restrict the program size, like "for a program with less than 500 characters, decide if it halts" then the problem IS solvable, at least on paper: You just make a lookup table for every possible program and the answer Yes/No. The unsolvability is because we're trying to make a program that solves halting for any sized program.
While a predictive program might not be possible for any program, a detection program could be written. If a program reaches state X, then it must perform the action associated with X. Every time it reaches state X it performs the same action, bringing it to the same next state Y. If the detection program detects that the program is in state X again, and no user input or random chance has been used since the last time it was in state X, then it must perform the same series of steps and eventually arrive at X again. That would be an infinite loop and the detection program would notice that the program is stuck. Whenever random generation or user input is called for by the program, the detection program can use the state immediately following that as the new “state X” if we get back to that point without user input or randomness then we’re stuck. The detection program could detect the loop and either alter the state to try breaking the loop or just force the program to end.
Except this would not work for cases where the program does never reach the same state twice. Like the program example program in this video - it increments counter at infinitum - the state does not repeat. And even if it did, the memory needed to record all encountered states even in fairly mundane programs is untenable.
@@KohuGaly What counter is incrementing? Also you only ned to remember the state immediately after user/random input or at the beginnining of a recursive function. If the computer is in a loop, it only takes one state to notice. Any point during that loop will suffice, so all we need to do is guaruntee that when we take a snapshot will be during the loop, and the previous snapshot can be discarded. If we take it too often we might be taking multiple states within the long singular loop and never notice, but if we wait to long to take a snapshot then we could get stuck in the loop early on and not know until significant time has passed.
We can also ignore any cases where user input or random chance are taken because that would be a way to break the loop and therefore it isn't infinitely looping. We can check recursive functions and for/while loops before runtime, things like while(true) without a break condition or a recursive function calling itself without a countdown or end state check. Many code editors have features like that, which will notify you if a section of code will never execute, usually because it falls after a written infinite loop.
Essentially, there are trivial loops that can be detected by the compiler and false loops that are "supposed" to happen because rng or the user want them to happen. Think of it like how a graphics engine calls a draw command every frame, it has to loop that but isn't actually stuck in a loop because it uses user input. Just because the user chooses to sit on the menu screen for hours doesn't mean we're stuck. So after each call of a loop like for or while, or after a recursive function call, and we can take the state immediately after user input or rng, because a loop that includes user input isn't a problem.
We also don't need to memorize every past state, we already narrowed down timings of when notable states are, but if we find reason to take a new state we can forget the previous states. We take a state when we suspect we might be in a loop, whatever the previous state was, either it isn't part of the loop and we don't care or it is part of the loop but we're about to know from our newer state regardless. Essentially, the first time we call any of these potentially looping lines of code, we take a snapshot and every cycle we just compare the snapshhot with the current state. Only one state needs to be saved, and a single boolean comparison between the two takes minimal resources even with the high frequency of checks. If some sort of counter is incrementing between iterations of the loop, it's just a much larger loop. Eventually that counter will overflow and wrap around to 0 again and then we've found a match to our snapshot. That's assuming the counter isn't being used for a breakout condition.
@@anthonycannet1305 Not all counters can overflow. It's pretty trivial to create a counter that can increment forever (a Sting in most languages can do it).
This is not some fringe example either. It's fairly common for programs to record a log, which is also a part of the state, and the log never reaches the same state twice, because it only appends.
That's actually a big part of why halting problem is unsolvable. It's possible to create programs which never enter the same state twice, because they have unbounded amount of memory to store states.
The "unbounded" part is a reasonable approximation of a real modern computer, when you take into account stuff like external storage.
Loop that includes user input is still a problem. It is not guaranteed that the user input can break the loop, or has any effect on the loop whatsoever.
The Halting Problem is what "Watchdog Timers" were created for.
Brian ❤❤❤❤❤
I mean, cant you make an imperfect one that would throw an error for a contradiction (Maybe run it 3 times or something and if it changes then throw an error) but would check if:
1: The program has a loop that is conditional on something that is changed in the loop
2: The program has a loop that its conditional statement that changes in an increment that will eventually reach the condition
Meaning "while true do end" would fall under 1, making it an infinite loop, or "while x ~= 0 do x = x + 2" and x starts at an odd number.
Why was it re-uploaded?
The first video did not halt
misspelled contradiction at 2:40?
Technically, if the input is -1, the program will eventually halt. This is because once you reach max integer size, it will revert to min integer size and eventually increase to -1.
You can easily solve this bug by inputting 0.5
Hope this helps! :D
Its pretty abstract programming we are talking about, so I am not sure there will be any "maximum possible integer", it can really easy run to whatever integer
Technically you cannot tell because you don't know what architecture this is and how the instructions are interpreted. Some types don't overflow (such as IEEE 754 floating point values). You can also build such an architecture or run the program in such an environment that doesn't have integer size limits.
Also, signed integer overflow is undefined behavior in some low-level languages. For example, a C++ compiler is allowed to optimize
for (int i = 0; i != -1; ++i)
into an infinite loop, because the optimizer is allowed to assume that signed integer overflow never happens.
@@krajsyboys 0.5 is not an integer though so the program wouldnt accept it
Ok so if so far loops we can create an halt program it's easy for that but than there will be bug of just you describe but other than that it would work as intended
There was a mistake at 2:40 with the proof by contradiction
have we tried just not using the opposite function as an input to the halt function?
If you made a plate called 'the indestructible plate', and I proved it wasn't indestructible by dropping it on the ground, would you saying "it's indestructible as long as you don't drop it on the ground" suddenly make it indestructible again? So, too, is the machine not possible. Just turning your head and looking away from the mistake existing doesn't suddenly mean it can't make mistakes.
@@godlyvex5543 if you had a plate that was indestructible except by dropping it on the ground that would be a hell of a plate
I always hated how it needs OPPOSITE to negate the return value. Always felt artificially manipulated to be more complicated and almost begging to contradict itself. I'd lose track of thought and got angry. I didn't believe in it.
The diagonaliztion argument as in Gödel or Cantor or Russel however always made sense to me.
If you struggle with it like I did, imagine this: OPPOSITE doesn't negate but returns the same as HALT, then there are two cases:
1: It returns yes, original algorithm eventually halts
2: It returns no, it won't halt
So just an extra layer to HALT itself.
But it doesn't have any meaning. HALT itself is not proven to be correct. It is just assumed to exist and the proof is build upon this supposition.
The further you try to "decompose" this proof and and observe it and try to catch where the essence lies, the weirder it becomes.
It is like casting your fishing line and "waiting to see what could be landed" . Only to afterwards realize, it was impossible to go fishing here in the first place.
Humans, I think (or me at least) have a hard time grasping that last "backwards" step in causality, the existence of something would lead to a contradiction somewhere else. This contradiction was provoked by behaving completely normal but under the circumstance that this certain something exists, suddenly the world would fall apart. Ergo this something cannot exist.
This is the crunch point for me, which feels unsatisfying sometimes, but this is where it lies.
I’m not a computer person but for the most part computers only allow acceptable values. If a computer asks for an input and you put -1 or q or something that it doesn’t accept, it won’t run will it?
The legend has it - that green bot has been walking ever since, from the moment of big bang until the end of the very existence. A true oblivion program known to our mankind.
The end! 😂
So its halted eventually? 😂
What if you forbid the Halt program analysing itself or the Opposite? It's not a useful analysing program if you intentionally ask it to output the opposite of what's it'd say normally.
theoretically, you could end up giving it a unique but functionally identical version of the halt program, so it would be read as if it were a different program, but outputs the same values
also, you could end up accidentally programming an Opposite function (thinking of the many times I've misused != unintentionally) which means the halt program wouldn't be able to analyze a legitimate but poorly written program that just so happens to output the opposite of the input
The issue is not the halt program per say, but the fact that a computer can simulate another computer (including itself). This is not some fringe case either - it's actually very common. The browser you're watching this on probably has Javascript interpreter embedded in it.
Then Halt can get looped forever in some other situation. Unless we analyze it with itself we can't be sure that it won't run forever given some other input.
Every implementation of a Turing machine runs on a non-Turing machine (that is, a system with limitations), since there is no such thing as an infinitely nested Turing machine. While it is not possible to write an H-solver for Turing code, it is possible to write an H-solver for any system which implements a Turing machine. Better yet, all computer code ultimately comes down to a real-world physics simulation, which is very theoretically solvable.
I never understood why people obsess over the abstract H-solver. I get that generally in math, if you write an abstract equation for a problem, it can solve any and all individual instances of that problem. But this is not the case with the H-solver or the abstract Turing machine. For instance, consider a program which repeatedly divides a number by 2 and halts when it reaches 0. If we had an H-solver for a theoretical perfect Turing machine, it would say that this program never halts. And yet, this program would definitely halt when run on ANY real-world system when the number gets so small that the platform rounds it to 0. You might try to resolve this discrepancy by saying that the H-solver needs to understand not only the code, but the code's IMPLEMENTATION, in order to do its job. But the moment you say that code needs to bring its own implementation with it, the whole idea of a Turing device breaks down and becomes irrelevant. Code A no longer equals Code A.
Fascinating. I ! = expert, and I'm curious if any practical work arounds have integrated a halt detector with an AI model that's trained to estimate how humans would likely respond to or prefer to resolve an ambiguous halting situation. It seems like AI could be tasked to mitigate this intractable problem in ways that could be more flexible and intuitive than setting arbitrary limits.
Again, not my field at all, so I won't be surprised if I'm talking nonsense.
I have an issue with this argument. The program Opposite (the analyzer) analyzes Opposite (the analyzed), however the analyzer has a different input than the analyzed, thus it is not contradictory that they yield different answers. If the analyzed has the same input as the analyzer, then by recursion the input must be infinite in size which could be the actual source of the problem
no, they have the same input. Opposite takes a single program as an input. The halt function inside it takes two inputs - the program and its input. In this particular case, it is given the opposite program and is asked whether it halts when it's given opposite program as an input.
Can't you put a if steps is 0 < Input then start? Also if it is the oppisite of oppisite, then that means if halt says halt, it halts do to it being oppisite of oppisite meaning it is just regular.
Let me know if I'm wrong. To me, this provement sounds like "we cannot divide a number by 0, so a general division doesn't exist". The `Opposite` program is so specifically constructed that the `Halt` has to predict it's own result in order to give a result. If we define `Halt` to be a program that can predict halting giving any program, AS LONG AS ITSELF IS NOT INVOLVED, what would be the answer?
That isn't really the focus of the video. The video just explains the proof against a perfect solution to the halting problem. Asking "but what if there was an imperfect proof?" is something tons of people have already asked, and isn't the focus of the video.
@@godlyvex5543I understand. But just like my analogy, calling a solution imperfect only because it has one singularity neither makes any sense nor has valuable applications. This video starts with a real life scenario and ends up with a conclusion that doesn’t necessarily have something to do with it. I feel like I watched a video that starts with a question “why finding prime factors of a big number is complicated” and ends with a conclusion “we can’t divide numbers by zero therefore division operation doesn’t exist but finding prime factors requires such a non-existing operation.”
@@cjrsacred What? This comment is nonsense. You described a completely different situation with no similarities and said "this situation is like that one." No, it isn't all all like that. Establishing that a general solution to always figure out whether a problem will halt or not, being proven impossible, is a fairly useful thing to know, unlike the situation you described. And what do you mean I'm calling a solution imperfect because it has "one singularity"? Do you know what a singularity is? I'm calling it imperfect because a perfect solution DOES NOT EXIST. That's the whole thing the video set out to explain. If your solution works for most things but not every last one, then it is by definition imperfect, or could also be called a partial solver.
I've always wondered about this proof because we could construct a very similar situation using simple language. Let's assume we were playing Mad Libs. The blanks of the phrases are just parameters to a function, and in many cases, the blanks need very specific types of inputs for the phrase to make any sense. Let's assume we have a phrase, "_______ is a false statement", but this blank can ONLY contain statements which actually ARE false. If the statement isn't false, then you cant see the resolution of the mad lib just like you cant see the resolution of the OPPOSITE function. So, if we create a scenario in which our resulting mad lib would read "'_______ is a false statement' is a false statement", no matter whether the innermost statement is true or false, the entire statement CANNOT compile because we have declared that it will only do so if a false statement is in the blank.
But now let's recreate our HALT function as a mad lib template, "Inserting ______ into the template ______ will create a valid mad lib", where the first blank accepts ANY input, and the second blank requires you to input ANY mad lib template, then the statement will either be true or false determined by whether your desired input followed the rules of your desired mad lib template.
Now we nest some statements and try to answer it:
'Inserting "Inserting _______ into the template '_______ is a false statement.' (Only accepts false statement) will create a valid mad lib." into the template "_______ is a false statement." (Only accepts false statement) will create a valid mad lib.'
The important thing to notice is that you can't evaluate the outer parts first. You HAVE to evaluate if the innermost statement is true or false before you can continue. The other thing that is important to notice here is the HALT template ALWAYS containing the OPPOSITE template WITHOUT directly inserting the parameter INTO the template. So for example, if we input 1+1=2 into the innermost parameter, we are NOT directly evaluating "'1+1=2' is a false statement", as this would not compile. Instead we are placing the OPPOSITE template and the parameter for it INTO the HALT template. This means, EVEN IF the OPPOSITE template wouldn't compile with that parameter inserted, the HALT template WILL still compile, as no uncompiled statement was ever actually made, we simply asked if it WOULD or not. The same thing happens when we try to insert the result of THAT into the OPPOSITE template AGAIN using the HALT template so it must compile.
Now we simply work our way up the chain.
Does "1+1=2" compile in OPPOSITE? No.
Does "'1+1=2' compile in OPPOSITE" compile in OPPOSITE? Well, if the previous part was no, that means HALT was false, and so HALT in OPPOSITE must be true.
Remember; the goal of HALT is NOT to actually evaluate a function. It ONLY determines whether it halts or not, so if you are assuming that HALT(OPPOSITE, OPPOSITE) doesn't halt, then it is because you are actually trying to EVALUATE the result of OPPOSITE(OPPOSITE(?)), which defeats the purpose of having used HALT to begin with.
Maybe some other proof exists for why the Halting Problem can't be true, but I don't see this as a sufficient explanation when it is clearly derived on a critical misunderstanding of the purpose and functionality of HALT.
I was wondering how you prove this.
What does it mean to give a program itself, or another program, as input? In the context of the video, the input to a program is supposed to be a number; what number corresponds to a program?
It doesn't have to be a number. It can be a string of symbols. Or you could concatenate all the bytes and treat them as a number.
On a basic level, any input (wether numbers or text, audio or image, ...) will be encoded as bits, 1s and 0s. And any program code is stored in the same way.
So you can say that every possible input and every possible program are both just numbers, in a loose sense.
Whenever an article title contains a question, the answer is no.
russell's paradox in naive set theory
I know that it is not possible to determine if it will halt for ALL program. But is there a category of program where it can be known ?
Then the HALT code will response YES/NO/UNKNOWN instead of YES/NO, which will allow to break to paradox by answering UNKNOWN regarding the OPPOSITE program.
a trivial such HALT program would be one who always outputs UNKNOWN
@@the_cheese_cultist yes obviously. But the aim would be to have as high a percentage of yes/no as possible.
@@wonay you will always have an infinite number of programs you can't determine for. so percentages don't really work for this.
It's always self references giving trouble, Russell be dammed
respect
I read it as "the hating problem" and rushed in thinking maybe we'll be working towards world peace 😭
why does this sound like the cs50 TA Brian
Breathtaking knowledge. It's like God shared a piece of his secret.
the green robot still walking
when input is defined using a well founded relation and the program is guaranteed to reduce the input at every step, there is a termination guarantee
in fact some programming languages don't allow other recursion by default like Lean
And that is not Turing complete. The ability to have infinite loops in the code is a fundemental requirement in order to be Turing complete
Typo at 2:44 you wrote Contadiction instead of Contradiction
please make one vid on 'n clique problem'
Could it work if a condition is you can’t use the output to decide if something is going to loop
This comment makes literally no sense whatsoever. Please rewatch the video.
@@paulblart7378 what do you mean I’m just asking if it’s answer can’t affect the output will there still be a paradox
@@malekabdoh8639 Your question is way too generic. There might be, there might not be. But either way, that's completely irrelevant to the proof.
@@paulblart7378 I was asking under that circumstance would there be a new paradox
What if we add a Null state? Which means it's impossible to tell.
The halting problem isn't a problem if you set how many times you want the loop to run before backing out to check on its state. Right?
if you limit the length of loops you can determine halting, but you also become not turing complete.
Even if we can imagine a particular scenario where the halting program can be "fooled" by a specially written program, doesn't that mean that we could write a halting program that would solve for most cases? In other words, we could write a program that while it could never be totally sure it was correct could still determine whether the program would halt with a high degree of certainty - a "good enough" solution? It follows that if we could write such a program, our computers should be able to tell us most of the time whether our programs will eventually halt or not - simply by calculting the delta between the halt condition of a loop and the progress that the program is making towards that condition, instead of the os always blindly saying that it isn't sure.