Understanding the Halting Problem
Vložit
- čas přidán 6. 05. 2023
- The halting problem is an important problem in computer science that asks whether we can construct an algorithm to determine whether a computer program will run forever. It turns out that the halting problem can't be solved, and in this video, we look at the proof to understand why.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
![Eminem - Houdini [Official Music Video]](http://i.ytimg.com/vi/22tVWwmTie8/mqdefault.jpg)
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!
It feels like we should still be able to make programs that solve the haunting problems in certain, restricted scenarios.
Yes, the proof is only applicable *in general*.
For some cases the problem is trivially easy to decide, and for many more cases with good enough accuracy.
It seems this video cared more about theoretical proof than practical application.
@@nisonatic That's still what I would call a general approach. For specific pieces of software, the halting problem does not exist. Think about trivial examples like hello world.
We don't run general software on general hardware but specific software on specific hardware, so the problem exists in theory, but not so much in practice.
Code analysis can help, adding 'max attempts' breakout conditions to otherwise infinite loops for example.
Correct. The Alan programming language is a perfect example of this: it prohibits runtime-bounded loops and recursion from even compiling, which prevents the creation of infinite loops in the first place. With these restrictions in place, the Alan compiler gains the power to statically reason about the behavior and performance of its programs just by looking at the code itself.
I don't think arming an AI with an unlicensed nuclear accelerator would be a good idea.
@@StephanTrubedoesnt this contradiction proof, only prove that there are atleast one circumstance where the halt program will fail. (I see it as halt will either go into a infinite loop, trying to get the resulting condition or it will recognize that it will go into an infinite loop and therefore say that the program would go on indefinitly. The opposite program is just a way of reversing the answer, so we shouldnt take its false result as wrong, because if it indeed does the opposite the result should come out wrong if everything is working correctly!?).
Because this is a computer working with instructions it would need to follow the ordinary path of the input with that program to determine where such an error would occur, in doing this it would get stuck in the infinite loop. Its just like if we created a program that determined how many rows of code that would be run with a specific input, the opposite program would break that too regardless of how we designed it.
You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!
Note: that we might make a program that can IN SOME CASES predict whether an algorithm stops or runs indefinitely. In all cases-no, it’s proven. But in some cases-possible.
Here's one of my favorite anecdotes when it comes to the halting problem. Consider the following program:
X = 1
Do Until X = 0
X = X / 2
Loop
One of the stipulations of an "H-solver" is that the Turing machine you're running the programs on is perfect at what it does (meaning, it has no bounds or constraints, and has infinite memory space). On a perfect Turing machine, that which we're writing the H-solver for, this program would never halt, as there exist infinite numbers between 1 and 0. However, if we were to run this program on any computer which actually exists in the real world, this program would halt, as the value of X would eventually round down to 0 due to the constraints of the data type. Thus, if a perfect h-solver did exist, it wouldn't give us any meaningful real-world information about this program!
It is self-evident that a perfect Turing machine cannot exist, and it follows that an H-solver for a perfect Turing machine also cannot exist. But the question remains: Can there exist a "practical" H-solver which works for any system with well-defined boundaries? If so, which boundaries are necessary to know in order for any given algorithm to be H-solvable?
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.
The best video on CZcams. I mean, yes.
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.
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! :)
Finally, a math problem that can be solved with a sledgehammer.
Brian, thank you so much for these and CS50w videos. Your explanations are amazing
I got so excited when I saw a notification that you've posted a new video. Keep us the good work
2:44 Contadiction
never stop this channel please
again one of those videos. Thank you sir for your efforts.
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
Great work, thanks !
Love your videos!
Simply amazing kindly upload more videos, and thank you.
I've been watching your channel and it's been great.
Please do encryption algorithms, sorting algorithms, and history of computing.
This video is truly an asset! 💙
I never understood these thing for many years ! this dude is a rockstar!
really really awesome easy wayto understand.
this video came at just the right time. my algorithm analysis final is in a week
This is amazing!! Thank you!!
Thank you Brian Yu!
From Harvard?
@@ytoh6408 Yup!
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.
Awesome content Spanning Tree
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.
Great video. Also, the robots are absolutely adorable.
This channel is like water and air to the human being!
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.
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)
}
}
Hi, I love your videos! May I ask which program you use to make the animations? Is it Unity?
this is the third video that I watched...finally, I understand the proof!
The more I think about this, the less it feels like a solid proof. What you've proved here is more that OPPOSITE can't exist and will error out, not that HALT itself can't. Like I can determine if something is true or false, but I can't say "This statement is false." Being self-referential can lead to paradoxes, but that doesn't make other uses impossible.
Imagine HALT can always answer a yes/no question correctly.
Imagine OPPOSITE is the paradox: "This statement is false".
OPPOSITE can exist, as you can reference it as a statement. "Running" it, like giving someone the statement, they will say that it's a paradox. But since HALT can only say yes or no, it will always be wrong. This means HALT cannot always answer a yes/no question correctly. Contradicting the first statement. However, there are many other programs that can detect infinite loops, etc. But this video focuses on the halting problem only.
HALT cannot exist because if HALT existed , then OPPOSITE exist too , which means that HALT is actually not halt
You are always allowed to create an opposite program if a halt program exists. Like how you can always add 1 to a number to get another number. We know the rules that we are adding is allowed.
The fact that you can say paradoxes like "this statement is false" is exactly the crux of the proof that the halting problem can't be solved. Solving the halting problem involves creating a program that can describe itself, and all programs that depend on it. But a contradiction happens when you realize that a program can't describe a program that is designed to do the exact opposite of that the original program would say.
Yeah, it was just a matter of me looking at it from the perspective that some form can exist while it seemed like this example was meant to disprove that, but that isn't really the point. I can make a program that determines halting of other programs, but, what I can't do, and no one could ever do, is make a perfect program that always determines halting of other programs. So, while a particular use case can be fulfilled, the general "halting problem" cannot be solved.
The thing is, you are correct, AND THAT IS WHY THIS PROOF EXISTS. The halting problem is proof that a system without contradictions CANNOT EXIST. You cannot make a system of logic that does not, in some specific way, contradict itself. The Turing proof is answer to the Decideability Problem, and the answer being: No, you cannot have a system in which every problem is decideably false or true.
I like this channel, please cover more algorithms
Great video! At 2:44 there is a typo on contradiction.
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!!
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.
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
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
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
Great video. Reminds me of udiprod's video in which they show the same proof.
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!
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?
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
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.
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.
Brian ❤❤❤❤❤
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 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.
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.
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
The Halting Problem is what "Watchdog Timers" were created for.
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 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.
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.
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.
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.
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.
The little computer buddies are so cute!
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?
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?
have we tried just not using the opposite function as an input to the halt function?
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.
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
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.
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.
Asside from the issue of how much memory this would use, can you prove that there is not a program that will loop without ever repeating itself? There's plenty of programs I could write. A program that simulates the diagonalization proof for why the reals are larger than the rationals, for instance, would loop forever without repeating itself.
solvable same as network heartbeat, can miss eg 1 case its in a long loop, but miss 2 and force quit
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.
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.
At 2:55, you misspelled 'Contradiction' 'Contadiction' in the title.
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? 😂
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.
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
I was wondering how you prove this.
please make one vid on 'n clique problem'
So in many cases it can decide if a program is going to halt or loop forever, but not for every program in general.
Some says the green robot still runs to this day..
Whenever an article title contains a question, the answer is no.
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.
Counterpoint: in that situation, opposite would not halt. Not because HALT said it would halt, but because HALT would not halt.
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?
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.
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)
}
}
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.
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'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 if we add a Null state? Which means it's impossible to tell.
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?
It's always self references giving trouble, Russell be dammed
I read it as "the hating problem" and rushed in thinking maybe we'll be working towards world peace 😭
I knew of this proof, but to me it is very easy a computer can not so this. I can make a program waiting for a specific key being pressed. How would the computer know that key is available for being pressed? That would surpass the hardware boundaries!
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
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.