Understanding the Halting Problem
ฝัง
- เผยแพร่เมื่อ 6 พ.ค. 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.
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
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.
I wonder if it's your channel being recommended to people recently that inspired you to continue making more videos or something else. Either way I am glad that you do it, keep up the good work!
You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!
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.
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?
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! :)
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.
I got so excited when I saw a notification that you've posted a new video. Keep us the good work
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.
never stop this channel please
again one of those videos. Thank you sir for your efforts.
Brian, thank you so much for these and CS50w videos. Your explanations are amazing
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.
Simply amazing kindly upload more videos, and thank you.
this video came at just the right time. my algorithm analysis final is in a week
I never understood these thing for many years ! this dude is a rockstar!
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.
The best video on TH-cam. I mean, yes.
This video is truly an asset! 💙
Finally, a math problem that can be solved with a sledgehammer.
This is amazing!! Thank you!!
2:44 Contadiction
Great work, thanks !
Thank you Brian Yu!
From Harvard?
@@ytoh6408 Yup!
really really awesome easy wayto understand.
Awesome content Spanning Tree
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.
Hi, I love your videos! May I ask which program you use to make the animations? Is it Unity?
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! At 2:44 there is a typo on contradiction.
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.
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)
}
}
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 like this channel, please cover more algorithms
this is the third video that I watched...finally, I understand the proof!
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
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
Love your videos!
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.
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.
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
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
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.
Great video. Reminds me of udiprod's video in which they show the same proof.
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?
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.
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.
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.
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.
Cute robots! Your explanation videos are the best in the market according to my experiences!
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
I always hated how it needs OPPOSITE to negate the return value. Always felt artificially manipulated to be more complicated and almost begging to contradict itself. I'd lose track of thought and got angry. I didn't believe in it.
The diagonaliztion argument as in Gödel or Cantor or Russel however always made sense to me.
If you struggle with it like I did, imagine this: OPPOSITE doesn't negate but returns the same as HALT, then there are two cases:
1: It returns yes, original algorithm eventually halts
2: It returns no, it won't halt
So just an extra layer to HALT itself.
But it doesn't have any meaning. HALT itself is not proven to be correct. It is just assumed to exist and the proof is build upon this supposition.
The further you try to "decompose" this proof and and observe it and try to catch where the essence lies, the weirder it becomes.
It is like casting your fishing line and "waiting to see what could be landed" . Only to afterwards realize, it was impossible to go fishing here in the first place.
Humans, I think (or me at least) have a hard time grasping that last "backwards" step in causality, the existence of something would lead to a contradiction somewhere else. This contradiction was provoked by behaving completely normal but under the circumstance that this certain something exists, suddenly the world would fall apart. Ergo this something cannot exist.
This is the crunch point for me, which feels unsatisfying sometimes, but this is where it lies.
I 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.
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?
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 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.
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.
have we tried just not using the opposite function as an input to the halt function?
Thanks
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 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?
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.
solvable same as network heartbeat, can miss eg 1 case its in a long loop, but miss 2 and force quit
In fact, the halt 'Opposite' depends on which program 'Halt' will take. If first program halts then inner 'Opposite' will never stop, then 'Halt' tells it and outer '' will halt. I don't see any contradictions
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.
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.
Even if we can imagine a particular scenario where the halting program can be "fooled" by a specially written program, doesn't that mean that we could write a halting program that would solve for most cases? In other words, we could write a program that while it could never be totally sure it was correct could still determine whether the program would halt with a high degree of certainty - a "good enough" solution? It follows that if we could write such a program, our computers should be able to tell us most of the time whether our programs will eventually halt or not - simply by calculting the delta between the halt condition of a loop and the progress that the program is making towards that condition, instead of the os always blindly saying that it isn't sure.
I 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'
At 2:55, you misspelled 'Contradiction' 'Contadiction' in the title.
Brian ❤❤❤❤❤
I was wondering how you prove this.
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.
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?
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.
So in many cases it can decide if a program is going to halt or loop forever, but not for every program in general.
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.
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
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?
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
First, were there a program (A) called Halt which could determine whether a program (B) would halt or continue, it would by that very definition (as per the video) in actuality only be required of program (A) to determine whether a program (B) output fed to it would halt. It would not have to analyze if program (B) would continue on for that is the only possibility left if program (A) determined that the program (B) would NOT halt or whether it was unable to determine that program (B) would halt. If one were to deny this, he would by that be also denying that the program (A) had any ability to ever determine if program (B) would halt and of course, the instruction was to assume that it could.
At that, I think all is settled with regard to the initial goal defined. But in anticipation that this would not be sufficient for some….the goal as stated was to determine whether a program (B) would halt or continue as per program (A) which would output that answer. Then for some reason we are instructed that a program (C) would be required to take the output of program (A) as to whether program (B) would halt or not and do the opposite. Why? The goal was defined and achieve before program (C’s) introduction. This makes no sense. So program (B) performs its function, is judged by program (A) as to whether it will halt or continue on and program (C), as per the video is required to look at the output of program (A) and do the opposite. So the input of program (C) is the output of program (A) as per the function of program (B).
Claiming then that the program (C) would be input to itself and by that, create a contradiction for if it halted, it would continue on and if it continued on, it would halt, is the same fraud promoted in the liar paradox by Quine. In the liar paradox, “this statement is false”, self-reference is employed to generate the paradoxical function, i.e., if “this statement is false” is true that it is false, then it is false and thus NOT true, but then it is in fact false by that true, etc., thus the paradox. The liar paradox is complete sophistry and defies logic. The term “statement” in “this statement is false” is a set definition as well as a subject noun. But it is empty, i.e., it has no members. There is no reference object which might be judged as true or false. The adjective false (within the statement “this statement is false” is the means of its judgment), connected to the term “statement” by the linking verb “is”, is denied its function because the set definition/subject noun is empty. Here the term “statement” is not a noun like rabbit whose definition is self-contained so to speak. Additionally, this piffle breaks the law of non-contradiction as well as other logical rules. So, the halting problem is employing kind of self-referencing, i.e., if program (C) COULD run itself, which itself makes no sense, then the same kind of contradiction would be generated, i.e., that if it halted, it didn’t and if it didn’t halt, it did. How is this functional, logical or meaningful? Turing did not discover a contradiction in mathematics, he introduced one from outside, created one by the manipulation of the logic of the problem originally defined.
Can ANYONE show me if I am wrong and how? Tell me exactly where, because I think this is a fraud and it makes me suspect Goedell’s incompleteness theorem as well.
I agree with jamestagge3429 that the word ‘Statement’ in ‘This Statement Is False’ is empty of meaning; therefore, the so-called paradox is meaningless. The statement does not define what the statement is.
I also find it very suspicious that denying Halt’s result says nothing if it is genuine.
Halt is supposed to be able to tell if any general programme will halt or not. How is it that by arbitrarily denying Halt’s result, we make this Halt programme irrelevant and illogical? What is illogical is to deny Halt’s result without any valid reason to generate a contradiction.
@@rogeraudet2987 Thank you so much. It’s hard to get anyone to be bold to agree that such nonsense as Quine’s liar paradox of the Halting problem as presented in these videos, is all piffle. As for the term statement in the liar paradox, it is a set definition with no members and thus as you said, has no meaning, leaving the only way to consider the overall statement is as a self reference which makes it illegitimate on its own. Also, the halt program could not analyze the reverser program for the latter is structured to accept either halt or continue as an input and thus, by definition could be analyzed to output either halt or continue, so the entire scheme cannot work. It’s just more piffle. Turing might have been correct but none of the analogies posted in youtube is correct, each one illogical.
@@rogeraudet2987 Thank you so much. It’s hard to get anyone to be bold to agree that such nonsense as Quine’s liar paradox of the Halting problem as presented in these videos, is all piffle. As for the term statement in the liar paradox, it is a set definition with no members and thus as you said, has no meaning, leaving the only way to consider the overall statement is as a self reference which makes it illegitimate on its own. Also, the halt program could not analyze the reverser program for the latter is structured to accept either halt or continue as an input and thus, by definition could be analyzed to output either halt or continue, so the entire scheme cannot work. It’s just more piffle. Turing might have been correct but none of the analogies posted in youtube is correct, each one illogical.
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.
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.
The little computer buddies are so cute!
_The counter will never reach -1_
Nonsense. You just have to wait until the 64 bit variable overflows.
But counting that long might take a ridiculously long time.
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)
}
}
I know my thinking is flawed but why can the opposite program talk to the halt program? Opposite given it's own code will do the opposite of what it's internal halt predicted, but that's not a problem because another halt program will succefully determine it's outcome. The only thing the halting problem proves is that a machine cannot determine if ITSELF will halt or not
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? 😂
if x < 0 { halt }
this should work, right
Yes, that works for a very specific case. However, if in the same program you make it loop until steps is equal to 0.5, you keep getting issues.
What if there is a halting program that can tell whether a program can either halt, not halt or enter a contradiction state.
“halting+contradiction” program
A program can't "enter a contradiction state". It either halts or doesn't, there is no third option.
@@banana85247
Sure it can, the contradiction state is shown in this video.
@@Jaun_ Let’s assume that the halting program can produce a “contradiction” state then. So, HALT(OPPOSITE, OPPOSITE) = contradiction state.
Now, I define a program BAD_PROGRAM, that takes a program as an input, which:
A. Loops forever if HALT(program, program) is yes
B. Halts if HALT(program, program) is no
C. Halts if HALT(program, program) is our new contradiction state
What happens if we call HALT(BAD_PROGRAM, BAD_PROGRAM)?
1. If HALT(BAD_PROGRAM, BAD_PROGRAM) is yes, then BAD_PROGRAM halts, however by *(A)* BAD_PROGRAM must loop forever. This is a contradiction.
2. If HALT(BAD_PROGRAM, BAD_PROGRAM) is no, then BAD_PROGRAM loops forever, however by *(B)* BAD_PROGRAM must halt. This is a contradiction.
3. If HALT(BAD_PROGRAM, BAD_PROGRAM) gives “contradiction,” then the evaluation of HALT(BAD_PROGRAM, BAD_PROGRAM) reaches a contradictory state. However, by *(C)*, BAD_PROGRAM doesn’t reach any contradictory state; in fact HALT must output “yes” because BAD_PROGRAM is defined to halt in this case. HALT, therefore is saying that BAD_PROGRAM both halts and is in a contradictory state, which is logically inconsistent because these two states are mutually exclusive.
Well, we *could* say HALT(BAD_PROGRAM, BAD_PROGRAM) = contradiction2, which is a new fourth state: “when HALT, augmented with the ability to discern contradictory states for ordinary Turing machines, gives logically inconsistent behavior for a contradictory Turing machine.” What if I then defined BAD_PROGRAM_2, which halts if HALT(program, program) = contradiction2?
We can repeat that ad infinitum, but do you see the problem here? No matter how you augment the halting program to account for contradictory states, there will *always* be a counterexample which will give inconsistent behavior from the halting program. It is an inescapable contradiction that can’t be encoded as an additional state.
The issue, ultimately, doesn’t arise from BAD_PROGRAM being “contradictory”, but HALT itself being contradictory. The very existence of a generalized halting problem solver is logically inconsistent.
Whenever an article title contains a question, the answer is no.
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" ?
The Halting Problem is what "Watchdog Timers" were created for.
OBJECTION!!! if you give the value -1, to the program used as an explanation, it will halt after the counter overflows.
misspelled contradiction at 2:40?