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?
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.
We absolutely can solve a restricted version, though, we'll wind up with a technically correct but completely impractical solution. We imagine a register machine but with finite memory. Our machine also has no I/O commands, it can only move data between registers and memory (LOAD and STORE), do arithmetic, and adjust the program counter (JUMP, etc.) The machine has a HALT instruction, and we can also make it halt if an error is detected, e.g. division by zero. (Exactly how errors are handled don't really matter, though, it could ignore them and try the next instruction.) This is all equivalent to a Turing machine _except_ that it has finite memory. That's our restriction. We'll further define the "state" of our machine to be the registers and memory of our machine. (Think of the registers as a few extra words of memory.) We'll define state 0 as the program and input loaded into memory, the program counter (PC) pointing at the start of the program, and other registers zeroed out. We'll define state n+1 as state n modified by the result of reading and executing the instruction at PC. If state n+1 is that the machine has halted, we can declare that the program halts. If state n+1 is identical to any prior state, we have discovered an infinite cycle, and can declare that the program hangs. Great, halting problem solved! The obvious problem is all those states have to be stored. You might think you can compress this, but let's consider the worst possible case: It disregards its input. It will zero out all memory not containing code. It then adds 1 to the first bit, and carries it through all memory. Thus, with M bits of memory, it will count to 2^M, consuming that many states. It continues this until all memory has been filled with 1s, at which point we can add a HALT instruction or let it continue looping. So we will eventually know if it halts or not, it's just utterly impractical.
@@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.
@@StephanTrube I think what you're getting at is a forward-progress requirement, that, at any point, it must be provable that the algorithm isn't stuck in a cycle. That mostly affects infinite loops and recursive function calls: some kind of analysis needs to show that they really do end, e.g. an error will eventually be raised to exit a loop, or that a recursive call eventually leads to a terminal state. I considered this for a project, but a bit of research found others had tried it, and people complained that either the analysis seemed flaky or the rules are too strict and simple algorithms require ugly workarounds. And it doesn't seem to buy you much as code can still be unperformant enough that it seems to hang randomly.
@@StephanTrube But probably the best example of it really being done is probably Excel. I think the constraints they put on a spreadsheet formula do make it possible to detect cycles quite effectively. (Assuming, of course, you're not using VB macros...) As a domain specific language, it seems to be quite successful.
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.
@@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.
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.
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.
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.
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
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? If you do, you might get $1 million :) 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) } }
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.
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
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
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".
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.
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.
@@daniellewilson8527 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.
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?
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.
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.
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.
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.
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.
Most of my problems occur after the operationg system updates and changes setting, shortcut links, or tells you that this app has not been upgraded. Hesittation and freezing can occur when one is being hacked, too, I suspect? Endless loops are usually caused by progrmmers' syntax errors. a misplaced comma can wreak havoc in programs (the old word for app, fyi) Who programs the AI, these days, I wonder.
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
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.
The only practical problem I see with this is, there's actually quite straightforward "imperfect" implementation of the HALT program: simulate the given program on given input and after each step check if the memory state has already been reached. Either we simulate the program to the end, or we find out that it reached certain memory state twice, in which case it is looping. It is imperfect in the sense that it "only" works on programs that use finite amount of memory, but that's what every practical computer in the universe does. So what happens when we use this HALT program, create appropriate OPPOSITE program, and then run it on itself? It will attempt to do infinite recursion and will eventually crash after exhausting all of the computer memory. Which kind of confirms the statement that there's no program that can answer the halting problem, except we got our answer anyway.
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.
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.
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?
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?
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.
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'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?
I thought the same, but if you think of the programs not as separate files, but instead as functions in the same file, I feel it makes more sense intuitively. The "input" is not from a user typing it in, but it's an argument to the function. Thus, when "Opposite" takes in itself running itself running itself... as an argument, it can be iteratively passed in.
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! 😂
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.
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.
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
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.
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.
Tho by this definition i can in theory make a program that can correctly find if a program halts or loops forever almost always (as in a very small procent it fails, and says the opposite).
@CoolRubiksCube 0 seconds ago Really? If so, can you do so for the following program? If you do, you might get $1 million :) 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) } }
Wouldn't you also have an infinite loop of halt simulating oposite (to see if it would halt) which (simulated oposite) then asks halt to simulate oposite which asks halt to... You get the idea. And wouldn't then opposite never come to the execution of the if statement, because halt would be running forever itself...
How do you know that halt “simulates” opposite? Halt is defined to be a black box (we can’t see what’s inside it), so we can only observe what its inputs and outputs are. On the contrary, halt doesn’t actually “simulate” opposite, because it’s technically defined as an oracle machine. This is a computer that’s assumed to have the ability to give the correct answer for a specific question. It’s comparable to an omniscient oracle who uses supernatural knowledge to give the correct answer; it doesn’t need to simulate anything, because it already *knows* what the answer is.
Oh true, if it "just knows" instead of having some sort of process (even if the time for the process is 0, infinite loops would have undefined total run time), then it doesnt matter. Idk I just assumed it was like a code that made and tested the input code and saw what happened XD
I hope you can help me with my problem: I never understood this proof, because (from my point of view) when you put opposite into opposite, the input isn't really valid. For opposite to work, it needs an input of a program that either halts or loops, but the outcome would depend on the input of the other program. If we decide an input for the most inner program, the output of all programs exists, if we don't give any "real" input, no program ever starts to analyse anything, so we can either count this as halting or as undefined. I am sure this proof is correct since many people way smarter than me have used it, but I just don't get why there seems to always be a input-reliant program without input involved.
I see your confusion, the video is abstracting how the programs interpret what you give them. The 'input' for a program would always just be a number. HALT takes this input, interprets it as a code for a program (according to some encoding scheme, like how a program in a real computer is stored in memory as a set of 1s and 0s), and a code for some input to that program (maybe it reads the odd numbered bits for the program, and the even ones for the input, the exact method used doesn't affect the argument, so the video doesn't mention it), then tells you if that program halts for that input (perhaps saying 'no' if the first code doesn't make sense as a program). OPPOSITE takes its input (just a number) and interprets it as a program, then works out what HALT does when given this number for both the program and the input for that program, then does the opposite of that. So OPPOSITE(OPPOSITE) halts if and only if HALT says it won't. In slightly more formal terms, we define HALT(m,n) to be 1 if the program with code m halts on input n, and 0 otherwise. And OPPOSITE(m)=NOT(HALT(n,n)) where NOT(0) halts immediately and NOT(1) just dives straight into an infinite loop ( we can also define NOT(2),NOT(3,) etc. to also loop, just to make sure NOT is always defined, but it never gets fed anything but 0 or 1 so it doesn't really matter). We then try to work out OPPOSITE(m) where m is the code for OPPOSITE. Effectively we're asking the infallible yes or no question answering machine "If I built a machine that always does the opposite of whatever you say it does and fed it this input, what would it do?". Hope this helps.
@@mudkip_074 Thanks for breaking it down, but you lose me at interpreting the code for a program as an input. Sure, it's all zeros and ones, but if we interpret this using some kind of code language, there still exist errors (like using a string variable to answer a bool question), and that would be what happens when you use unrefined code as some kind of input, at least in my head. So how can we use a program that lacks the ability to be run (error: input missing) as a valid input for said program?
@@the.amarok It's not the program itself that's being used as input, but the code for it. A bit like if you clicked on the word.exe executable file and selected 'open with mspaint, paint would try to read the code that's supposed to be the code for microsoft word as though it were an image. Either paint would realise that this sequence of data doesn't make any sense as an image (formatted wrong, ie, paint is expecting 1s in certain places but word.exe has zeroes, because it isn't an image file) and halt and give an error message, or it would try to open it anyway and give an image file (would probably just be a jumbled mess of pixels). Errors like answering a bool question with a string don't occur because what type of data something is is something the program does. Whether the sequence 11010 is interpreted as the sting '11010', the int 26, or the float 26.0 depends on whether the program is expecting a string, or an int Modern coding languages (like python, C, Java etc.) store extra data with a variable that says what type of variable it is, to make them easier to use. But there's no reason you can't have a program store the string 'hello' and then interpret that set of 1s and 0s as though it were an int . So when we say what is OPPOSITE(OPPOSITE) we don't really mean feed the program OPPOSITE into OPPOSITE, we mean feed the source code for OPPOSITE into OPPOSITE. Like if you try to open word.exe in word, (which a modern operating system probably wouldn't let you do, but only because it's programmed not to, there's no reason that it can't). It helps me to think of the codes for programs more like serial numbers, so HALT(m,n) is "does the program whose code is m (serial number m) halt on input n?" The code for a program specifies everything the program does, but it isn't the program itself. There's a video about the halting problem by the channel udiprod which gives the same argument, but makes the distinction between a program and the code for a program and the input a program receives a bit clearer.
@@the.amarok"the program halts" doesn't mean that it has to work or give a "correct" result or anything like that. "Halts" means "does not run forever". In particular, if the program "crashes" on any particular input then it halts on that input (a crashed program doesn't keep running forever, so it's considered to have halted). An invalid program will also "halt" on all inputs. You can think of such a program just as a special case of "crashing" where you crash immediately on the very first step of execution. So, for example HALTS(garbage_data, 123) == yes, because trying to run garbage_data(123) will just immediately crash (assuming "garbage_data" is not a valid program).
It is crazy to me that people for years people have been dumbfounded at the fact doing the opposite, of doing the opposite, is no longer doing the opposite; but eliminates the contradiction. Futile man-made problem.
What if we add another state called "Opposite"? So now your halting program says: Yes it halts, no it doesn't halt, and it'll do opposite of what said. When it comes to detecting if -1 will be halted or not, the computer can just take a look as a human would do and say what's going on. If a human can solve it, a computer can also solve it. Issue is that most programs aren't as easy to determine, maybe a program is not halting because it's waiting for user input? In that case the program is spending time mostly sleeping. But if a process is consuming a long time, like creating large arrays or such, the computer has to now take a look at what instruction it's executing and what's it's going to do. It sounds simple, and it's simple for one program, but if you go beyond just one program, you need to make it think like a human. Probably possible with AI. Although my suggested approach takes a look at a program and says if it can be halted or not, but it doesn't actually solve the halting problem.
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.
It actually the very reason why it leads to contradiction. In the proof's setup Halt will run forever, thus no surprise that assumption that it will resolve any way turns out false. It shows that Halt can run forever, meaning that it can be unable to deliver any verdict.
Wouldn’t this be dependent on the program having some dependence on the halt program? It’s like a circular definition, the fact that one definition for an object/concept is circular doesn’t mean the object/concept can’t be defined. Idk Jack shit about programming, but if all programs dependent on the halt program are just restricted to being extremely simple, wouldn’t that mean that we don’t run into this specific halting problem?
i don't know nothing about computing science but Why the Halt program instead of having outputs with just "yes" and "no", would have "yes, unless the program is opposite which means no" and "no, unless the program is opposite which means yes" ?
Congratulations, you figured it out, kind of. If this scenario were real, the HALT program itself would enter an infinite loop and will not be able to provide an answer for OPPOSITE.
Imagine that you asked me to write a program that adds 2 numbers. I write that program and give it to you. You plug in 1+1 and the program just keeps running without giving you an answer. In fact, you look inside the program and it turns out that it's in an infinite loop (so it'll never halt). Would you say that the program that I gave you solves the "add 2 numbers" problem? The answer is NO. When we say that "this program solves problem X" it is implied that it does so in a finite amount of time (the amount of time may be very large or it may depend on the inputs, but it should never get stuck looping forever). If we don't include this restriction, then a simple "while (True) { }" program is suddenly the solution to every possible problem, which is clearly nonsense. So if your Halt program just loops forever after you give it Opposite, then it wasn't actually a valid solution to the Halting probablem.
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!
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?
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.
We absolutely can solve a restricted version, though, we'll wind up with a technically correct but completely impractical solution.
We imagine a register machine but with finite memory. Our machine also has no I/O commands, it can only move data between registers and memory (LOAD and STORE), do arithmetic, and adjust the program counter (JUMP, etc.) The machine has a HALT instruction, and we can also make it halt if an error is detected, e.g. division by zero. (Exactly how errors are handled don't really matter, though, it could ignore them and try the next instruction.)
This is all equivalent to a Turing machine _except_ that it has finite memory. That's our restriction.
We'll further define the "state" of our machine to be the registers and memory of our machine. (Think of the registers as a few extra words of memory.) We'll define state 0 as the program and input loaded into memory, the program counter (PC) pointing at the start of the program, and other registers zeroed out.
We'll define state n+1 as state n modified by the result of reading and executing the instruction at PC.
If state n+1 is that the machine has halted, we can declare that the program halts. If state n+1 is identical to any prior state, we have discovered an infinite cycle, and can declare that the program hangs.
Great, halting problem solved! The obvious problem is all those states have to be stored. You might think you can compress this, but let's consider the worst possible case:
It disregards its input. It will zero out all memory not containing code. It then adds 1 to the first bit, and carries it through all memory. Thus, with M bits of memory, it will count to 2^M, consuming that many states. It continues this until all memory has been filled with 1s, at which point we can add a HALT instruction or let it continue looping.
So we will eventually know if it halts or not, it's just utterly impractical.
@@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.
@@StephanTrube I think what you're getting at is a forward-progress requirement, that, at any point, it must be provable that the algorithm isn't stuck in a cycle.
That mostly affects infinite loops and recursive function calls: some kind of analysis needs to show that they really do end, e.g. an error will eventually be raised to exit a loop, or that a recursive call eventually leads to a terminal state.
I considered this for a project, but a bit of research found others had tried it, and people complained that either the analysis seemed flaky or the rules are too strict and simple algorithms require ugly workarounds. And it doesn't seem to buy you much as code can still be unperformant enough that it seems to hang randomly.
@@StephanTrube But probably the best example of it really being done is probably Excel. I think the constraints they put on a spreadsheet formula do make it possible to detect cycles quite effectively. (Assuming, of course, you're not using VB macros...) As a domain specific language, it seems to be quite successful.
You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!
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.
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.
2:44 Contadiction
The best video on UA-cam. I mean, yes.
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! :)
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.
I got so excited when I saw a notification that you've posted a new video. Keep us the good work
Brian, thank you so much for these and CS50w videos. Your explanations are amazing
Finally, a math problem that can be solved with a sledgehammer.
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
I've been watching your channel and it's been great.
Please do encryption algorithms, sorting algorithms, and history of computing.
again one of those videos. Thank you sir for your efforts.
Simply amazing kindly upload more videos, and thank you.
never stop this channel please
I never understood these thing for many years ! this dude is a rockstar!
Great work, thanks !
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.
this video came at just the right time. my algorithm analysis final is in a week
really really awesome easy wayto understand.
This video is truly an asset! 💙
This is amazing!! Thank you!!
Awesome content Spanning Tree
Thank you Brian Yu!
From Harvard?
@@ytoh6408 Yup!
Love your videos!
This channel is like water and air to the human being!
Hi, I love your videos! May I ask which program you use to make the animations? Is it Unity?
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.
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.
I like this channel, please cover more algorithms
Great video! At 2:44 there is a typo on contradiction.
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
Thanks
Great video. Reminds me of udiprod's video in which they show the same proof.
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? If you do, you might get $1 million :)
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)
}
}
this is the third video that I watched...finally, I understand the proof!
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
@@serenalaurence1492 holy hell!!
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.
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
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
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
Cute robots! Your explanation videos are the best in the market according to my experiences!
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.
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.
Is there any proof that does not use self reference?
I’m also curious about this
@@daniellewilson8527 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.
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?
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.
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.
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
Brian ❤❤❤❤❤
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.
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.
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.
Most of my problems occur after the operationg system updates and changes setting, shortcut links, or tells you that this app has not been upgraded. Hesittation and freezing can occur when one is being hacked, too, I suspect?
Endless loops are usually caused by progrmmers' syntax errors. a misplaced comma can wreak havoc in programs (the old word for app, fyi) Who programs the AI, these days, I wonder.
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
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.
The only practical problem I see with this is, there's actually quite straightforward "imperfect" implementation of the HALT program: simulate the given program on given input and after each step check if the memory state has already been reached. Either we simulate the program to the end, or we find out that it reached certain memory state twice, in which case it is looping. It is imperfect in the sense that it "only" works on programs that use finite amount of memory, but that's what every practical computer in the universe does.
So what happens when we use this HALT program, create appropriate OPPOSITE program, and then run it on itself? It will attempt to do infinite recursion and will eventually crash after exhausting all of the computer memory. Which kind of confirms the statement that there's no program that can answer the halting problem, except we got our answer anyway.
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.
have we tried just not using the opposite function as an input to the halt function?
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.
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?
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?
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.
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'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
I thought the same, but if you think of the programs not as separate files, but instead as functions in the same file, I feel it makes more sense intuitively. The "input" is not from a user typing it in, but it's an argument to the function. Thus, when "Opposite" takes in itself running itself running itself... as an argument, it can be iteratively passed in.
solvable same as network heartbeat, can miss eg 1 case its in a long loop, but miss 2 and force quit
Why was it re-uploaded?
The first version of the video had the audio set for the left speaker only.
The first video did not halt
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? 😂
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.
At 2:55, you misspelled 'Contradiction' 'Contadiction' in the title.
The Halting Problem is what "Watchdog Timers" were created for.
The little computer buddies are so cute!
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.
please make one vid on 'n clique problem'
I was wondering how you prove this.
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
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.
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.
Tho by this definition i can in theory make a program that can correctly find if a program halts or loops forever almost always (as in a very small procent it fails, and says the opposite).
@CoolRubiksCube
0 seconds ago
Really? If so, can you do so for the following program? If you do, you might get $1 million :)
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)
}
}
Some says the green robot still runs to this day..
Wouldn't you also have an infinite loop of halt simulating oposite (to see if it would halt) which (simulated oposite) then asks halt to simulate oposite which asks halt to...
You get the idea.
And wouldn't then opposite never come to the execution of the if statement, because halt would be running forever itself...
How do you know that halt “simulates” opposite? Halt is defined to be a black box (we can’t see what’s inside it), so we can only observe what its inputs and outputs are.
On the contrary, halt doesn’t actually “simulate” opposite, because it’s technically defined as an oracle machine. This is a computer that’s assumed to have the ability to give the correct answer for a specific question. It’s comparable to an omniscient oracle who uses supernatural knowledge to give the correct answer; it doesn’t need to simulate anything, because it already *knows* what the answer is.
Oh true, if it "just knows" instead of having some sort of process (even if the time for the process is 0, infinite loops would have undefined total run time), then it doesnt matter.
Idk I just assumed it was like a code that made and tested the input code and saw what happened XD
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?
Whenever an article title contains a question, the answer is no.
What if we add a Null state? Which means it's impossible to tell.
I hope you can help me with my problem: I never understood this proof, because (from my point of view) when you put opposite into opposite, the input isn't really valid. For opposite to work, it needs an input of a program that either halts or loops, but the outcome would depend on the input of the other program. If we decide an input for the most inner program, the output of all programs exists, if we don't give any "real" input, no program ever starts to analyse anything, so we can either count this as halting or as undefined.
I am sure this proof is correct since many people way smarter than me have used it, but I just don't get why there seems to always be a input-reliant program without input involved.
I see your confusion, the video is abstracting how the programs interpret what you give them. The 'input' for a program would always just be a number. HALT takes this input, interprets it as a code for a program (according to some encoding scheme, like how a program in a real computer is stored in memory as a set of 1s and 0s), and a code for some input to that program (maybe it reads the odd numbered bits for the program, and the even ones for the input, the exact method used doesn't affect the argument, so the video doesn't mention it), then tells you if that program halts for that input (perhaps saying 'no' if the first code doesn't make sense as a program). OPPOSITE takes its input (just a number) and interprets it as a program, then works out what HALT does when given this number for both the program and the input for that program, then does the opposite of that. So OPPOSITE(OPPOSITE) halts if and only if HALT says it won't. In slightly more formal terms, we define HALT(m,n) to be 1 if the program with code m halts on input n, and 0 otherwise. And OPPOSITE(m)=NOT(HALT(n,n)) where NOT(0) halts immediately and NOT(1) just dives straight into an infinite loop ( we can also define NOT(2),NOT(3,) etc. to also loop, just to make sure NOT is always defined, but it never gets fed anything but 0 or 1 so it doesn't really matter). We then try to work out OPPOSITE(m) where m is the code for OPPOSITE. Effectively we're asking the infallible yes or no question answering machine "If I built a machine that always does the opposite of whatever you say it does and fed it this input, what would it do?". Hope this helps.
@@mudkip_074 Thanks for breaking it down, but you lose me at interpreting the code for a program as an input. Sure, it's all zeros and ones, but if we interpret this using some kind of code language, there still exist errors (like using a string variable to answer a bool question), and that would be what happens when you use unrefined code as some kind of input, at least in my head. So how can we use a program that lacks the ability to be run (error: input missing) as a valid input for said program?
@@the.amarok It's not the program itself that's being used as input, but the code for it. A bit like if you clicked on the word.exe executable file and selected 'open with mspaint, paint would try to read the code that's supposed to be the code for microsoft word as though it were an image. Either paint would realise that this sequence of data doesn't make any sense as an image (formatted wrong, ie, paint is expecting 1s in certain places but word.exe has zeroes, because it isn't an image file) and halt and give an error message, or it would try to open it anyway and give an image file (would probably just be a jumbled mess of pixels). Errors like answering a bool question with a string don't occur because what type of data something is is something the program does. Whether the sequence 11010 is interpreted as the sting '11010', the int 26, or the float 26.0 depends on whether the program is expecting a string, or an int Modern coding languages (like python, C, Java etc.) store extra data with a variable that says what type of variable it is, to make them easier to use. But there's no reason you can't have a program store the string 'hello' and then interpret that set of 1s and 0s as though it were an int . So when we say what is OPPOSITE(OPPOSITE) we don't really mean feed the program OPPOSITE into OPPOSITE, we mean feed the source code for OPPOSITE into OPPOSITE. Like if you try to open word.exe in word, (which a modern operating system probably wouldn't let you do, but only because it's programmed not to, there's no reason that it can't). It helps me to think of the codes for programs more like serial numbers, so HALT(m,n) is "does the program whose code is m (serial number m) halt on input n?" The code for a program specifies everything the program does, but it isn't the program itself. There's a video about the halting problem by the channel udiprod which gives the same argument, but makes the distinction between a program and the code for a program and the input a program receives a bit clearer.
@@the.amarok"the program halts" doesn't mean that it has to work or give a "correct" result or anything like that. "Halts" means "does not run forever".
In particular, if the program "crashes" on any particular input then it halts on that input (a crashed program doesn't keep running forever, so it's considered to have halted).
An invalid program will also "halt" on all inputs. You can think of such a program just as a special case of "crashing" where you crash immediately on the very first step of execution.
So, for example HALTS(garbage_data, 123) == yes, because trying to run garbage_data(123) will just immediately crash (assuming "garbage_data" is not a valid program).
It is crazy to me that people for years people have been dumbfounded at the fact doing the opposite, of doing the opposite, is no longer doing the opposite; but eliminates the contradiction. Futile man-made problem.
I read it as "the hating problem" and rushed in thinking maybe we'll be working towards world peace 😭
misspelled contradiction at 2:40?
What if we add another state called "Opposite"? So now your halting program says: Yes it halts, no it doesn't halt, and it'll do opposite of what said.
When it comes to detecting if -1 will be halted or not, the computer can just take a look as a human would do and say what's going on.
If a human can solve it, a computer can also solve it.
Issue is that most programs aren't as easy to determine, maybe a program is not halting because it's waiting for user input? In that case the program is spending time mostly sleeping. But if a process is consuming a long time, like creating large arrays or such, the computer has to now take a look at what instruction it's executing and what's it's going to do. It sounds simple, and it's simple for one program, but if you go beyond just one program, you need to make it think like a human. Probably possible with AI.
Although my suggested approach takes a look at a program and says if it can be halted or not, but it doesn't actually solve the halting problem.
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 happens if "HALT" itself doesn't halt in this case?
The same thing that happens in geometry when your triangle has 4 sides.
It actually the very reason why it leads to contradiction. In the proof's setup Halt will run forever, thus no surprise that assumption that it will resolve any way turns out false. It shows that Halt can run forever, meaning that it can be unable to deliver any verdict.
It's always self references giving trouble, Russell be dammed
Wouldn’t this be dependent on the program having some dependence on the halt program? It’s like a circular definition, the fact that one definition for an object/concept is circular doesn’t mean the object/concept can’t be defined.
Idk Jack shit about programming, but if all programs dependent on the halt program are just restricted to being extremely simple, wouldn’t that mean that we don’t run into this specific halting problem?
i don't know nothing about computing science but Why the Halt program instead of having outputs with just "yes" and "no", would have "yes, unless the program is opposite which means no" and "no, unless the program is opposite which means yes" ?
But what if when you give Opposite to Halt then Halt never halts and just loops forever? Wouldn't that solve the contradiction?
Congratulations, you figured it out, kind of. If this scenario were real, the HALT program itself would enter an infinite loop and will not be able to provide an answer for OPPOSITE.
Imagine that you asked me to write a program that adds 2 numbers. I write that program and give it to you. You plug in 1+1 and the program just keeps running without giving you an answer. In fact, you look inside the program and it turns out that it's in an infinite loop (so it'll never halt).
Would you say that the program that I gave you solves the "add 2 numbers" problem? The answer is NO.
When we say that "this program solves problem X" it is implied that it does so in a finite amount of time (the amount of time may be very large or it may depend on the inputs, but it should never get stuck looping forever). If we don't include this restriction, then a simple "while (True) { }" program is suddenly the solution to every possible problem, which is clearly nonsense.
So if your Halt program just loops forever after you give it Opposite, then it wasn't actually a valid solution to the Halting probablem.
No
Because that wouldn't be halt