Understanding the Halting Problem

[@fredoverflow]

I love how the green robot is still running when the video ends 😂

[@Ggdivhjkjl]

We may need to force stop him 🤖

[@pafnutiytheartist]

He's fine, one day he'll overflow and reach -1

[@Thekingmaker]

The robot was red

[@lightning_11]

@@pafnutiytheartist That's what I was thinking...

[@NachitenRemix]

wtf@@Thekingmaker

[@Trank933]

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!

[@samarthtandale9121]

You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!

[@lightning_11]

It feels like we should still be able to make programs that solve the haunting problems in certain, restricted scenarios.

[@StephanTrube]

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.

[@StephanTrube]

@@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.

[@jard]

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.

[@clovernacknime6984]

I don't think arming an AI with an unlicensed nuclear accelerator would be a good idea.

[@elis9851]

​@@StephanTrubedoesnt this contradiction proof, only prove that there are atleast one circumstance where the halt program will fail. (I see it as halt will either go into a infinite loop, trying to get the resulting condition or it will recognize that it will go into an infinite loop and therefore say that the program would go on indefinitly. The opposite program is just a way of reversing the answer, so we shouldnt take its false result as wrong, because if it indeed does the opposite the result should come out wrong if everything is working correctly!?). Because this is a computer working with instructions it would need to follow the ordinary path of the input with that program to determine where such an error would occur, in doing this it would get stuck in the infinite loop. Its just like if we created a program that determined how many rows of code that would be run with a specific input, the opposite program would break that too regardless of how we designed it.

[@Wonders_of_Reality]

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.

[@Strakester]

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?

[@urielmarles7036]

​@@Strakesterrounding is not necesarilly the actual result. In python you get an out of memory

[@superspartanman4480]

So glad you are making more videos, I discussed this exact problem with my buddy over spring break

[@jaideepshekhar4621]

Glad to see you back dude! :) It would be great if you went further into NP and NP hard problems, and their classes. Cheers! :)

[@tobias131314]

Thanks

[@chuckgaydos5387]

Finally, a math problem that can be solved with a sledgehammer.

[@GuitarSlayer136]

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.

[@NathanSMS26]

2:44 Contadiction

[@Dark_Slayer3000]

Luckily we can easily write a halting program for any specific program, just not for every program.

[@Wonders_of_Reality]

Exactly! Many teachers omit this optimistic thought.

[@MrDifsh]

​@@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.

[@Wonders_of_Reality]

​@@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.

[@emtacolor]

this video came at just the right time. my algorithm analysis final is in a week

[@Anythiny]

never stop this channel please

[@NEMountainG]

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!

[@fredoverflow]

Sure, e.g. IntelliJ IDEA detects many silly infinite loops where the loop body does not influence the loop condition at all.

[@NEMountainG]

@@fredoverflow Thank you! I’ll investigate this. I am curious as to what the theoretical limits are though :)

[@TheEvilCheesecake]

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.

[@nightfox6738]

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.

[@fredoverflow]

@@nightfox6738 Your idea is known as "symbolic execution" in the mainstream.

[@arthursamenu5327]

I never understood these thing for many years ! this dude is a rockstar!

[@debanwitahajra]

The best video on KZbin. I mean, yes.

[@asmaarefaatVO]

This channel is like water and air to the human being!

[@GCKteamKrispy]

Brian, thank you so much for these and CS50w videos. Your explanations are amazing

[@dancer2234]

But is it possible to make an algorithm that can determine whether a program will run forever in all cases EXCEPT when evaluating a program which contains itself? That seems essentially equally practically useful

[@WolfiiDog13]

Well, most OSs have some way of telling if an application is stuck or not, but it's never 100% certain

[@mega_micro]

@@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.

[@israelRaizer]

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.

[@bsargent]

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.

[@Lemon_Inspector]

Unfortunately, determining whether a program "refers to itself" is equivalent to the Halting Problem.

[@giveaway4002]

really really awesome easy wayto understand.

[@李庭瀚]

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.

[@swapbriarASMR]

shhh new proof just drop

[@ahmadmazbouh]

@@swapbriarASMR holy hell!!

[@realdelana]

I got so excited when I saw a notification that you've posted a new video. Keep us the good work

[@TheGraphicsgriffin]

Love your videos!

[@elidavid1993]

Great video! At 2:44 there is a typo on contradiction.

[@davestrider2045]

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.

[@CoolRubiksCube]

Can you do so for the following program? n = 0 while (1){ n += 1 seen = [ ] x = n while (x != 1){ if ( (x % 2) == 0 ){ x = x/2 } else { x = 3*x + 1 } if ( seen contains x ){ HALT() } seen.add(x) } }

[@akam9919]

@@CoolRubiksCube what is "seen"

[@CoolRubiksCube]

@@akam9919 A list, defined by ```seen = []```

[@akam9919]

@@CoolRubiksCube Ah! Okay, thanks! I don't know how I didn't see it before.

[@mrosskne]

what does it get you?

[@bubblesort8760]

again one of those videos. Thank you sir for your efforts.

[@hihoktf]

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.

[@godlyvex5543]

It doesn't though. It's the input, it's not running. Having a program stored on your hard drive doesn't require it having an input, so why would using it as an input require that?

[@camerontangen2957]

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.

[@krajsyboys]

You can easily solve this bug by inputting 0.5 Hope this helps! :D

[@kendakgifbancuher2047]

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

[@Ryrzard]

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.

[@fredoverflow]

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.

[@jaxmc1912]

​@@krajsyboys 0.5 is not an integer though so the program wouldnt accept it

[@OllieWille]

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?

[@senzmaki]

my thoughts exactly

[@the_cheese_cultist]

you're right, the proof isn't formal enough. here's a version that avoids this issue: imagine a program H that given a program M and input w can determine whether M halts on w. create a program G that takes a program M and runs H(M, M) now create O which takes input M, runs G on M, and does the opposite of its output. now run O on O. G will run H on O, O so H will run O on O. if it halts, H and G will say halts, so O will run forever on input O, so H was wrong. if it runs forever, H and G will say runs forever, so O will halt on input O, so H was wrong.

[@godlyvex5543]

No? Opposite is a file and a program. When you put a program like 'minecraft' as an input into a program like 'winzip', to turn minecraft into a zip file, you don't need to run minecraft at any point in the process. The same applies here. Opposite is a program that can accept other programs as inputs, just like winzip. You can also put winzip into winzip and encounter no issues. Not the same copy of winzip, since windows prevents running files from being modified to avoid any issues, but this isn't an issue with the 'opposite' program. Just have two copies of 'opposite', and feed one into the other. No issues.

[@workonly-bf4vz]

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

[@bcs_AyushkumarRai]

Simply amazing kindly upload more videos, and thank you.

[@kvelez]

I've been watching your channel and it's been great. Please do encryption algorithms, sorting algorithms, and history of computing.

[@alaminshuvo3815]

This video is truly an asset! 💙

[@1ntellect]

Thank you Brian Yu!

[@ytoh6408]

From Harvard?

[@1ntellect]

@@ytoh6408 Yup!

[@martingeorgiev999]

Great video. Also, the robots are absolutely adorable.

[@samkelo_m_]

This is mind blowing 🤯

[@marcc1179]

this is the third video that I watched...finally, I understand the proof!

[@mykydragon9265]

This videos is soooo good.

[@pedrosso0]

Is there any proof that does not use self reference?

[@naturegirl1999]

I’m also curious about this

[@nightfox6738]

@@naturegirl1999 Me too. Afaik it doesn't exist though. There are a lot of these "Proofs by contradiction" in math that use self-reference to make some concept blow up in your face and while I get the mathematical rigor and all it just feels like a cop out. It's similar to the set of all sets that do not contain themselves. A set of all sets, by definition contains itself as it is a set, then adding on the stipulation that it doesn't contain itself seems to me about as useful as asking for an orange that isn't an orange. I understand the reason is to show incompleteness in a rigorous mathematical system but it seems manufactured to contradict itself and draw a conclusion that doesn't really help us solve anything. How does it benefit us to know that math is incomplete because a few fringe cases that aren't even useful anyway don't work? Isn't it enough to know that math works for most cases, and the ones that don't will show a clear contradiction? Does it matter that math is incomplete? Back to the halting problem, does it matter that it can't handle self reference? Couldn't we propose a ternary output "does it halt" function that says yes, no, or this is a contradiction that actually works?

[@naturegirl1999]

@@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.

[@TheModernPolymath]

why are we giving a program itself as an input to the halt function in the opposite program? can someone please explain..

[@DocUzuki]

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.

[@hkcprivate6977]

At 2:55, you misspelled 'Contradiction' 'Contadiction' in the title.

[@husmertmert]

Some says the green robot still runs to this day..

[@sledzik1235]

Can we write an program wchich tests if the halting problem can be solved on a given program?

[@StephanTrube]

Yes, it is only unsolvable in general. For specific programs, solutions exist.

[@transientaardvark6231]

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.

[@karansmittal]

Awesome content Spanning Tree

[@davidfrisch5099]

Great work, thanks !

[@Amonimus]

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.

[@eveleynce]

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

[@KohuGaly]

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.

[@chachachi-hh1ks]

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.

[@CC1.unposted]

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

[@Tom-lf7zw]

have we tried just not using the opposite function as an input to the halt function?

[@godlyvex5543]

If you made a plate called 'the indestructible plate', and I proved it wasn't indestructible by dropping it on the ground, would you saying "it's indestructible as long as you don't drop it on the ground" suddenly make it indestructible again? So, too, is the machine not possible. Just turning your head and looking away from the mistake existing doesn't suddenly mean it can't make mistakes.

[@Tom-lf7zw]

@@godlyvex5543 if you had a plate that was indestructible except by dropping it on the ground that would be a hell of a plate

[@danielbrandstetter8713]

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.

[@anthonycannet1305]

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.

[@KohuGaly]

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.

[@anthonycannet1305]

@@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.

[@KohuGaly]

​@@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.

[@Dr.tech-]

I like this channel, please cover more algorithms

[@baranxlr]

Weird thing is, if you restrict the program size, like "for a program with less than 500 characters, decide if it halts" then the problem IS solvable, at least on paper: You just make a lookup table for every possible program and the answer Yes/No. The unsolvability is because we're trying to make a program that solves halting for any sized program.

[@jonasfariacosta]

Hi, I love your videos! May I ask which program you use to make the animations? Is it Unity?

[@silviocupica2521]

Why was it re-uploaded?

[@MrTeen-ul7yc]

The first video did not halt

[@iddoutoufikislem1846]

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?

[@asefsgrd5573]

Cute robots! Your explanation videos are the best in the market according to my experiences!

[@milakohen630]

Brian ❤❤❤❤❤

[@James2210]

misspelled contradiction at 2:40?

[@Shiro-vh5oh]

why does this sound like the cs50 TA Brian

[@Fungustus1]

The little computer buddies are so cute!

[@widmo206]

I feel like there would be three options: a) the program halts -> HALT() returns true, b) the program loops forever -> HALT() returns false, c) there is a contradiction -> HALT() crashes because it can't decide Also, at 4:50 you pass the OPPOSITE() code to HALT() with OPPOSITE() as an argument, but the result would be indeterminate not because it's a contradiction, but because the OPPOSITE you passed along is missing an input! (since you're only passing the code)

[@Unreql]

You're third option doesn't work as we have assumed that there is a perfect halt program that is always right, therefore it can't crash.

[@jpalz]

@@Unreql So the "proof" doesn't prove that it's impossible to write a Halt program, only impossible to write a perfect Halt program.

[@maskangel]

@@jpalz no, the proof proves that it is not possible to write a halt program. a "non-perfect" halt program is just not a halt program, it is a different program.

[@jpalz]

@@maskangel It's similar to the "universal set" paradox. A set of all sets must contain itself, but that can't be possible. But a set of all sets "except itself" is possible. A program which perfectly determines whether a program will halt is impossible, _ONLY_ because it may fail when self-reference is involved. Of course that is correct, it just seems like a cheeky answer. By that logic, a lot of programs are impossible to write. Just about every program will have some potential flaw when you apply a rigorous enough scenario. Consider a program which reads the exact color of an image to 1-bit accuracy. This is also Impossible, because there might be situations where the camera fails, or the lighting is off a little bit, etc. So would we say "It is impossible to write a program which can read colors"? No. It would be reasonable to say "It is impossible to write a program which can PERFECTLY and unfailingly read colors", but what's the point of that statement? So, "It is impossible to write a program which can determine with perfect accuracy whether a given program will halt" is a true statement. But it feels like an academically manufactured dead-end, and I hate it.

[@jpalz]

"Can you write a program which will perfectly add two integers without error?" "Nah." "What? Why not?" "Well, if you feed the input a string then it will give an error, so it's impossible." "So just check that the inputs are bother integers before adding them" "But then it won't perfectly add two integers without error.." Does that sound silly?

[@theAstarrr]

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

[@CoolRubiksCube]

Still confusing?

[@theAstarrr]

@@CoolRubiksCube I'm gonna watch this soon and find out

[@theAstarrr]

@@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

[@ichamsakkar4249]

Great video. Reminds me of udiprod's video in which they show the same proof.

[@v0xl]

what happens if "HALT" itself doesn't halt in this case?

[@Lemon_Inspector]

The same thing that happens in geometry when your triangle has 4 sides.

[@chachachi-hh1ks]

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.

[@the_cheese_cultist]

a decider is a program which, given input, always halts and gives an output of yes/no. a property which can be checked by a decider is called decideable. the halting problem is not decideable a recognizer is a program which, given input, either halts and outputs yes/no, or runs forever, which is interpreted as a no answer. a property which can be checked by a recognizer is called recognizable the halting problem is recognizable there is also co-recognizer, where running forever is interpreted as yes. the halting problem is not co-recognizable there are problems which aren't even recognizable or co-recognizable, like checking whether two programs are functionally identical.

[@steviousmusic]

I was wondering how you prove this.

[@Chooooseeeenone]

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?

[@AnonymousThinker-zz9dz]

so the halt orogram can't check if the opposite program will when the opposite program is given itself as input. Thats it though right? This doesnt prove that the halt program can't solve everything else rught? Maybe a halt program could determine whether any other program will halt?

[@msman3249]

What if we add a Null state? Which means it's impossible to tell.

[@anukthotawatta982]

its like Pinocchio saying "My nose will now grow"

[@KevinInPhoenix]

The Halting Problem is what "Watchdog Timers" were created for.

[@surferriness]

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 heard the explanation to this problem in 10 different videos and still doesn't get git. What is that even mean to give to the program input that is a program

[@paulblart7378]

First of all, let me tell you that this video is probably your best bet of understanding it, as it's the closest thing I've seen to the actual formal proof. Or better yet, stop looking at these analogies and just look up the formal proof. Second of all, I really don't see what's confusing about anything in this proof. Why are you hesitant about the idea of using a program as an input? What makes it so strange as opposed to using number of text as input? Any sort of entity can be an input or output to a program and it's perfectly valid. Imagine an antivirus program: their input is a program file, and their output is their analysis of how dangerous the file is.

[@ilikepigs7937]

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.

[@Nikolas_Davis]

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?

[@Lemon_Inspector]

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.

[@StephanTrube]

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.

[@blacklistnr1]

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.

[@malekabdoh8639]

Could it work if a condition is you can’t use the output to decide if something is going to loop

[@paulblart7378]

This comment makes literally no sense whatsoever. Please rewatch the video.

[@malekabdoh8639]

@@paulblart7378 what do you mean I’m just asking if it’s answer can’t affect the output will there still be a paradox

[@paulblart7378]

@@malekabdoh8639 Your question is way too generic. There might be, there might not be. But either way, that's completely irrelevant to the proof.

[@malekabdoh8639]

@@paulblart7378 I was asking under that circumstance would there be a new paradox

[@prolarka]

So in many cases it can decide if a program is going to halt or loop forever, but not for every program in general.

[@scanerang]

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

[@KohuGaly]

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.

[@Katniss218]

doesn't "giving opposite program itself as input" produce infinite recursion or something?

[@zmaj12321]

No, because the input program does not need to be executed. Someone else in the comments gave a good example: winzip is a program that takes another program as input. You could input Minecraft into winzip and get an output without having to run any Minecraft code. Similarly, you can run a copy of winzip into winzip with no problems.

[@cjrsacred]

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?

[@godlyvex5543]

That isn't really the focus of the video. The video just explains the proof against a perfect solution to the halting problem. Asking "but what if there was an imperfect proof?" is something tons of people have already asked, and isn't the focus of the video.

[@cjrsacred]

⁠@@godlyvex5543I understand. But just like my analogy, calling a solution imperfect only because it has one singularity neither makes any sense nor has valuable applications. This video starts with a real life scenario and ends up with a conclusion that doesn’t necessarily have something to do with it. I feel like I watched a video that starts with a question “why finding prime factors of a big number is complicated” and ends with a conclusion “we can’t divide numbers by zero therefore division operation doesn’t exist but finding prime factors requires such a non-existing operation.”

[@godlyvex5543]

@@cjrsacred What? This comment is nonsense. You described a completely different situation with no similarities and said "this situation is like that one." No, it isn't all all like that. Establishing that a general solution to always figure out whether a problem will halt or not, being proven impossible, is a fairly useful thing to know, unlike the situation you described. And what do you mean I'm calling a solution imperfect because it has "one singularity"? Do you know what a singularity is? I'm calling it imperfect because a perfect solution DOES NOT EXIST. That's the whole thing the video set out to explain. If your solution works for most things but not every last one, then it is by definition imperfect, or could also be called a partial solver.

[@aumbattul2268]

please make one vid on 'n clique problem'

[@kilroy1964]

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.

[@Someone-c8f9l]

I think the program could be made, but things have to exist in the real world. It may be that to implement the Halt program, it would require a third input, a description of the execution environment that the parameter program would be run on. Basically, the problem becomes an answer to the question of "What would this program do when given this input, within this environment". The Halt program might also have to fully evaluate recursively defined components of the input program, and since the input program is recursively defined without a base case, it would eventually cause a stack overflow thus ending the recursion. In this setup, the Opposite program could be legitimately run in such a manner explained in the video, but it would have to be run on actual hardware with more ram than the execution environment descriptor given to the Halt program for the output to be correct. Put simply, when something is actually run on real hardware, it will certainly do something and that something can be predicted, but the resources given to the prediction engine must be greater than that of the execution environment under question in order to guarantee the prediction can be accurately generated in the general case. Mathematics and logic are fascinating and useful tools, but it seems to me great care needs to be taken when using them to make claims about reality. Mathematics and logic seem less constrained than the universe system we actually reside in so you can create conundrums whose real answer is "reality doesn't work like that".

[@Sans-fl4pe]

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.

[@mrprofile101]

I still don't understand the proof contradiction. Can't this be used to disprove everything in existence everywhere as long as you preface it with: "Hey, whatever the answer is, flip it"? for example if I am trying to prove that 2+2=4 couldn't I use the contradiction proof to say "2+2 isnt four because I decided beforehand that 2+2 is going to be the opposite of whatever 2+2 is" Or proving the existence of an animal "if cats exist, then cats don't exist, else cats exist" There is a piece of the puzzle that I am missing. Also, can't you just limit the input to only valid ones and solve this issue? example: "oh, you're using an opposite machine? that's not allowed, close program or go into some default state"

[@Ryrzard]

Proof by contradiction depends on assuming that the conclusion is true and using it to derive a contradiction. Assuming that 2 + 2 = 4 does not lead to contradiction but 2 + 2 = 5 does so you can use proof by contradiction to prove that 2 + 2 does not equal 5 because if it did then it would lead to a logical contradiction.

[@elichapin3366]

i think that within finite computers, we can build a program that will determine it for sure, if at any point of time, all the elements of a program are the same, then you know it has to loop, for example, if the elements of your program were represented in numbers, and as the program ran, they changed: 1, 3, 8, 2, 4, 1, as soon as you get one again, you know that 3, 8, 2, . . . are going to follow, eventually getting 1 again, so you know it loops, but because the computer is finite, there are only so many states the elements of the program can be in without looping, so you wont have to wait forever, so if you run the program, wait until it either terminates, or has the same set of elements, and you'll know if it loops or not. the reason why an infinitely large computer doesn't work, is because you might wait forever, it going threw an infinite set of unique elements, without looping

[@Ryrzard]

@@elichapin3366 That only works for some problems. And even then you'd have to assume statically allocated memory which isn't always true.

[@mkriskt]

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! 😂

[@kendakgifbancuher2047]

So its halted eventually? 😂

[@totalme302]

What about a program that will tell whether Halt can do work properly or not.

[@paulblart7378]

Halt doesn't exists, as this proof has shown, so a program that analyzes Halt can't exist either... at least, not in a meaningful manner.

[@wonay]

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.

[@the_cheese_cultist]

a trivial such HALT program would be one who always outputs UNKNOWN

[@wonay]

@@the_cheese_cultist yes obviously. But the aim would be to have as high a percentage of yes/no as possible.

[@the_cheese_cultist]

@@wonay you will always have an infinite number of programs you can't determine for. so percentages don't really work for this.

[@-CmonMeow]

solvable same as network heartbeat, can miss eg 1 case its in a long loop, but miss 2 and force quit

[@charlesje1966]

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?

[@the_cheese_cultist]

if you limit the length of loops you can determine halting, but you also become not turing complete.

[@realdelana]

There was a mistake at 2:40 with the proof by contradiction

[@the.amarok]

I hope you can help me with my problem: I never understood this proof, because (from my point of view) when you put opposite into opposite, the input isn't really valid. For opposite to work, it needs an input of a program that either halts or loops, but the outcome would depend on the input of the other program. If we decide an input for the most inner program, the output of all programs exists, if we don't give any "real" input, no program ever starts to analyse anything, so we can either count this as halting or as undefined. I am sure this proof is correct since many people way smarter than me have used it, but I just don't get why there seems to always be a input-reliant program without input involved.

[@mudkip_074]

I see your confusion, the video is abstracting how the programs interpret what you give them. The 'input' for a program would always just be a number. HALT takes this input, interprets it as a code for a program (according to some encoding scheme, like how a program in a real computer is stored in memory as a set of 1s and 0s), and a code for some input to that program (maybe it reads the odd numbered bits for the program, and the even ones for the input, the exact method used doesn't affect the argument, so the video doesn't mention it), then tells you if that program halts for that input (perhaps saying 'no' if the first code doesn't make sense as a program). OPPOSITE takes its input (just a number) and interprets it as a program, then works out what HALT does when given this number for both the program and the input for that program, then does the opposite of that. So OPPOSITE(OPPOSITE) halts if and only if HALT says it won't. In slightly more formal terms, we define HALT(m,n) to be 1 if the program with code m halts on input n, and 0 otherwise. And OPPOSITE(m)=NOT(HALT(n,n)) where NOT(0) halts immediately and NOT(1) just dives straight into an infinite loop ( we can also define NOT(2),NOT(3,) etc. to also loop, just to make sure NOT is always defined, but it never gets fed anything but 0 or 1 so it doesn't really matter). We then try to work out OPPOSITE(m) where m is the code for OPPOSITE. Effectively we're asking the infallible yes or no question answering machine "If I built a machine that always does the opposite of whatever you say it does and fed it this input, what would it do?". Hope this helps.

[@the.amarok]

@@mudkip_074 Thanks for breaking it down, but you lose me at interpreting the code for a program as an input. Sure, it's all zeros and ones, but if we interpret this using some kind of code language, there still exist errors (like using a string variable to answer a bool question), and that would be what happens when you use unrefined code as some kind of input, at least in my head. So how can we use a program that lacks the ability to be run (error: input missing) as a valid input for said program?

[@mudkip_074]

@@the.amarok It's not the program itself that's being used as input, but the code for it. A bit like if you clicked on the word.exe executable file and selected 'open with mspaint, paint would try to read the code that's supposed to be the code for microsoft word as though it were an image. Either paint would realise that this sequence of data doesn't make any sense as an image (formatted wrong, ie, paint is expecting 1s in certain places but word.exe has zeroes, because it isn't an image file) and halt and give an error message, or it would try to open it anyway and give an image file (would probably just be a jumbled mess of pixels). Errors like answering a bool question with a string don't occur because what type of data something is is something the program does. Whether the sequence 11010 is interpreted as the sting '11010', the int 26, or the float 26.0 depends on whether the program is expecting a string, or an int Modern coding languages (like python, C, Java etc.) store extra data with a variable that says what type of variable it is, to make them easier to use. But there's no reason you can't have a program store the string 'hello' and then interpret that set of 1s and 0s as though it were an int . So when we say what is OPPOSITE(OPPOSITE) we don't really mean feed the program OPPOSITE into OPPOSITE, we mean feed the source code for OPPOSITE into OPPOSITE. Like if you try to open word.exe in word, (which a modern operating system probably wouldn't let you do, but only because it's programmed not to, there's no reason that it can't). It helps me to think of the codes for programs more like serial numbers, so HALT(m,n) is "does the program whose code is m (serial number m) halt on input n?" The code for a program specifies everything the program does, but it isn't the program itself. There's a video about the halting problem by the channel udiprod which gives the same argument, but makes the distinction between a program and the code for a program and the input a program receives a bit clearer.

[@ruroruro]

​@@the.amarok"the program halts" doesn't mean that it has to work or give a "correct" result or anything like that. "Halts" means "does not run forever". In particular, if the program "crashes" on any particular input then it halts on that input (a crashed program doesn't keep running forever, so it's considered to have halted). An invalid program will also "halt" on all inputs. You can think of such a program just as a special case of "crashing" where you crash immediately on the very first step of execution. So, for example HALTS(garbage_data, 123) == yes, because trying to run garbage_data(123) will just immediately crash (assuming "garbage_data" is not a valid program).

[@asailijhijr]

Whenever an article title contains a question, the answer is no.

[@justingiovanetti]

Contradiction is spelled wrong in the video.

[@GameJam230]

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.

[@ravirajac]

What about watchdog timer?

[@Jaun_]

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

[@banana85247]

A program can't "enter a contradiction state". It either halts or doesn't, there is no third option.

[@Jaun_]

@@banana85247 Sure it can, the contradiction state is shown in this video.

[@jard]

@@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.

[@iamagreatape9576]

wouldn't the halt program itself get stuck in a loop in this case and not halt?

[@olixx1213]

That wouldn't be the halt program if it could halt