The Impossible Problem NO ONE Can Solve (The Halting Problem)

[@upandatom]

Get Nebula using my link for 40% off an annual subscription! go.nebula.tv/upandatom And if you're having déjà-vu, yes I have made a video about the halting problem, but this one is better.

[@odizzido]

I am going to try nebula again. It had performance issues when I tried it when it first started out but I imagine those have been solved now.

[@fredashay]

Jade, do you think the Halting Problem will ever be able to be solved? _(And to the Chinese .50 cent army guy who keeps following me around YT and harassing me for being an advocate of Democracy, go eff yourself and eff Xi Jinping!!!)_

[@govcorpwatch]

1:35. I walked by a part of the original ENIAC while working for UPenn Computer Graphics Lab. After discussion with an original ENIAC worker, they said that the ENIAC was created NOT for just "artillery tables" but for computing Nuclear weapons. No joke, That IS the classified purpose of the ENIAC. People still don't know this.

[@TheTransitmtl]

ChatGPT is a LLM. It can't solve anything. It's just so good at making groups of words sound coherent that people mistake its output for some kind of reflection. I use it for simple coding tasks like writing very simple unit tests and even at that it makes many errors

[@njnjhjh8918]

I adore you, Jade, but does a HaltChecker cause a paradox if it never runs? HaltChecker has two inputs. You only give HaltChecker Reverser as input and nothing else and what is Reverser's input?

[@chrisshuttleworth]

Your use of multiple nested monitors and the “programs” watching them (in different clothing and hairstyles so we could differentiate between them) was very creative. Well done!!

[@Slackware1995]

Except it doesn't describe what she is saying.

[@davealan5685]

Part of her job is pick out lots of cool cloths and hairstyles for her various videos. If I were an objective tax auditor, I'd allow her to tax deduct all or nearly all of them provided she maintained a reasonably sized wardrobe for personal use as well.

[@cybisz2883]

I have never before seen such a fun, simple, and clever illustration of the halting problem than your haltchecker & reverser. That was pure genius!

[@xbzq]

It's also incorrect and missing. If it's genius then it must be evil genius.

[@Chaitany9]

Wt do u mean by hault checker

[@xbzq]

@@Chaitany9 Did you watch the video? It's incorrect. Working is hard isn't it? Halt, not hault.

[@SapSapient]

I very much appreciate the clear, methodical approach these videos take in explaining moderately complicated ideas. I also had not realized how developed Turing's ideas were so early in his career.

[@thegzak]

This is actually a deeply complex idea, the trick is to explain it so masterfully that it feels simpler than it really is 😉 Well done!

[@lonestarr1490]

Most of the groundbreaking work by the really big names in math, physics, computer sciences and alike has, more often than not, been done in the early years of their careers, like in their early 30's or even their 20's. Einstein, in his annus mirabilis 1905, has been 26 years old. The years from 25 to 35 are really the most creative decade you're given in your lifetime. Peek performance not only in sports but also in science, as it turns out.

[@stylis666]

@@lonestarr1490 And in arts as well. As you said, in all creative fields. Thankfully that doesn't stop people from being creative outside of their peak, but you seem to be very correct in the assessment that most creativity is expressed in early adulthood. Probably due to many factors of which the brain and the rest of the body are just a few of the factors. One/some of the other factors might be the spreading and increasing of talents, efforts, and focus. So that also doesn't mean that less value is produced in the same time, but it is more spread out over different areas, so there are less pronounced peaks.

[@Orion40000]

@@lonestarr1490 Asimov wrote a story that suggested that the Earth is a petri dish filled with agar jelly. Humanity was the bacteria that formed on it, and its growth represented the increase in human knowledge. Sometimes, a bacterium would evolve which was so hugely successful that it would explode in population, massively increasing our sphere of knowledge. So far, so good. He then went on to suggest that there was an outside force - a galactic penicillin - that stopped us learning too much too quickly. Maybe for our own good, or maybe for the good of the society the penicillin represented. As soon as we started growing by an uncomfortable amount, those outstanding bacteria would be killed. If such an analogy were accurate, I wonder how old you could get before the penicillin noticed you?

[@HalfdeadRider]

@@lonestarr1490 Maybe it is changing in science as it is in sports, people are staying fitter and stronger much longer than 35-40 already.

[@zerksari]

Excellent! Watched easily over 100 hours on incompleteness and studied it myself at university. This video is easily the most 'visualized' digestable walkthrough. Props!

[@cykkm]

Jade had another vid on the TM and the halting problem specifically, a couple years back, on this very channel. That one had, IMO, even more concise illustration of the proof. Do find it if you liked this one!

[@zerksari]

@@cykkm Saw it, I agree. This one is more.. 'digestable' I would surmise. Both are really good. Don't get me started on Turing. What they did to the genius at easily the level of Bach should be cried and taught globally. They stole a part of our future. These folks don't come around that often..:(

[@fikipilot]

You had fun filming and editing haltchecker and reverser. It looked like fun. I love the filmography of this complex maths discussion. Love it!!!

[@decreasing_entropy3003]

This has been very intuitive; the personification of the Haltchecker and Reverser has been very discernible, even the core statement of Russell's paradox aptly put. Well made video!

[@AndrewMellor-darkphoton]

Alan Turing could not do PHD in computer science because he had to invent it first, he got a PHD in mathematics. 12:05

[@upandatom]

you’re right my bad

[@AndrewMellor-darkphoton]

@@upandatom thanks for responding.

[@PasseScience]

For the curious, some connections between Halting Problem and Gödel incompleteness (some are "obvious" , others more interesting): 1) Given a program p the statement "p halts" (or not) is a mathematical statement like any other. 2) When you work with a mathematical theory you work with axioms and the rules to combine them to make proofs, theorems. 3) Given a mathematical theory (with some conditions) it's possible to write a program, taking a statement S, that will browse every possible valid proofs of finite length of your theory and stop if it hits a proof of either S or not S. (it's because the set of proofs of finite length is a countable infinity, you can browse them by increasing length L, and below L you know there is a finite number of proofs) 4) Having such a proof browsing program would at first glance seem to give an halting program, you would just ask it to find either a proof or a disproof that a given program p of your choice halts or not (you give it S="p halts") and by construction you know that if such a proof (or disproof) exists your proof browsing program will find it in finite time (not bounded, but finite) 5) But because of the reduction by absurdum argument of the video above we know that halting program cannot exist. 6) So it means that for some program pi, when you give the statement S = "pi halts" to your proof browsing program it will never stop. 7) Allowing to conclude that in your theory the statement "pi halts" doesn't have a proof (of finite length) nor a disproof. So you have an example of a statement that is independent of your axioms.

[@Slackware1995]

The problem is that in her example the only reason she can conclude that the halting program doesn't exist is to specifically create 2 program that take as their input the output of the other program AND define one program to reverse it's input. That doesn't prove that a halting program can't exist (she gave several examples of it existing) only that in her specific unusual example that the outputs of both programs would be wrong. That is like claiming that math doesn't exist because of divide by zero.

[@PasseScience]

@@Slackware1995 Na, it's not what she is doing, you did not get the point, let me unfold it (keep in mind that a program can be interpreted as data in the rest of this answer): What you are trying to find the existence of is a program Halt(x, y) that would tell you for *ANY* program x and *ANY* data y if x(y) eventually stops or not. (And of course you want such a Halt program to never be wrong and always give you an answer in finite time). To show that such a Halt program can't exist it's enough to show that if it was existing you could have a contradiction. Let's consider the following program: Paradoxe(x): If Halt(x,x) loop else stop; So here I built the program Paradox that is using inside the program Halt (that we initially supposed existing for the sake of the demo), Paradoxe takes an input x and will loop forever if Halt conclude that x on x stops and stop if halt concludes that x on x never stops. It's important to see that if Halt exists and is of finite length then Paradoxe exists and is of finite length (I just built it above). Now look at what happens if you run Paradoxe(Paradoxe): it will loop if Halt concludes Paradoxe(Paradoxe) stops and stop if halt concludes Paradoxe(Paradoxe) loops, which is a contradiction. So the only assumption we made at the beginning was necessarily wrong: a program Halt(x,y) cannot exist (A program that would tell you for ANY program x and ANY data y if x(y) eventually stops or not.) because if it did we could reach such a paradox.

[@Slackware1995]

@@PasseScience I understand the paradox. The issue is that you can't make a simple program that has an input the output of a second simple program whose function is to "reverse" the input an send that as an output that is used as an input to the first program as proof that the first program can't and doesn't exist. Simply because the paradox exists doesn't mean that there are an infinite number of unknown paradoxes and because the paradox is known the first program can be adjusted to check for it. Even if there are many such unknown paradoxes that doesn't mean that one they will never be found and the first program changed to account for them. In more simple terms her programs were written to be proof and then she assumed that nothing will ever change. This is ironic considering she discussed mechanical computers, then how much digital computers have evolved in the past 70ish years, and mention quantum computers. We have no concept of what computers will be able to do in 50 years, let alone 100, 200, 1000, ad infinitum. Furthermore, just because you can find 1 specific, limited instance of a failure doesn't make something not exist. Divide by zero doesn't make math not exist. The fact that there isn't a computer model that can show what stresses a structure will endure based on real life changes in wind at various height levels doesn't mean computer modeling doesn't exist. This is why her conclusion that a halting program doesn't (and never will) exist because of a single paradox is a false conclusion.

[@PasseScience]

@@Slackware1995 *The issue is that you can't make a simple program that has an input the output of a second simple program whose function is to reverse the input and send that as an output that is used as an input to the first program as proof that the first program can't and doesn't exist.* I am not sure to get the construction I described. If you suppose there is a Halt(x,y) program doing what I described in the previous commentary, what prevents me of defining the program Paradox like that: Paradoxe(x): If Halt(x,x) loop (while true if you prefer) else stop; Nothing prevents me from doing so, I just did. If Halt was an existing and finite program Paradox would be as well. Keep in mind that the existence of the program Paradoxe is NOT THE PROBLEM. The problem occurs when you try to evaluate and describe one of it's possible execution, the one where it is launched on itself as data, it's the specific execution Paradox(Paradox) that introduces a paradox not the existence of the program Paradox I described. *Simply because the paradox exists doesn't mean that there are an infinite number of unknown paradoxes and because the paradox is known the first program can be adjusted to check for it.* It means exactly that, you cannot adjust your halt program because the construction that has been described can take the new Halt program and would still allow to build the program Paradoxe(x) You can fix your halt program any way you want you'll still be able after to build the program Paradoxe above, and reach a contradiction when looking at the execution Paradox(Paradox), you will never conclude, never reach an Halt program that fix every issue because we have a demonstration on how to build an issue if we have an halt program that is working.

[@Slackware1995]

@@PasseScience Congradulations on describing a program that you know will fail. Creating a program designed only to prove a paradox does not mean that all halt programs do not exist (as claimed in the video) and will never exist. Again, divide by zero does not mean math doesn't exist. You can create a halt program that would invalidate this paradox (there are many ways to do this that are simple). Claiming that you can't know ahead of time all possible paradoxes is obvious, but it doesn't mean that the halt program can't be fixed in the future.

[@migfed]

This episode has become now, I do believe firmly, into one of your own anthology of finest videos featured by you. Thank you so much. The concept was sharply posted and yet clearly for anyone without great knowledge of computer science.

[@alvaro_ch]

Was about to state the same 👍

[@silkwesir1444]

Yes. I think never before where so many previous videos mentioned.

[@xbzq]

It's incorrect. The halting checker needs two inputs, a program, and an input for that program. That's just the start of why this is very wrong. Udiprod made the correct explanation many years ago and she should have watched it before releasing this incorrect video.

[@andrewj22]

​@@xbzqThanks. I was finding the explanation very confusing. If the halt checker was supposed to work given a ore-defined, specific input for the program it was checking, then there should be no necessary problem determining whether "reverser" would halt or not. I'll look up the explanation you referred to.

[@kensmith5694]

A program that says "yes", "no", and "maybe" to the halting question turns out to be a very useful thing even though there are cases it can't handle. When working on code to do some useful task, it can be very useful to have something that finds mistakes that cause your code to stick in a loop. Many compilers contain code that produces an "unreachable code" warning message for a lot of such cases.

[@SetemkiaFawn]

Very important aspect of Turing's creation now known as the Turing Machine. The various steps that the machine could perform were meant to duplicate things that could be done by a computer. When he started his work the only computer that he knew of was a human using brain, pencil, and paper. He was trying to characterize what a computer could compute.

[@cykkm]

Strictly, you mean the UTM. Also, the concept of non-deterministic TM is at the core of computational complexity theory. E.g., it's how the NP class is defined. Yes, he was a tragic genus. A troubled mind of Poincaré's magnitude. I was blown away by his paper on biology and life. It parallels Schrödinger's “What is life?” in a sense, but from the mathematician's perspective. I forgot the title, but you can find it. You won't be disappointment, for sure! And, speaking of computers, it was unclear whether ENIAC would be able to compute everything computable when it would've been built. Von Neumann himself was on the team that designed it, and he was uneasy while the machine was being constructed, because he couldn't prove it, in genera. Ironically, he was running into undecidable equivalence problems.

[@prototypeinheritance515]

@@cykkm I don't get how it was so hard to prove universality on the ENIAC. Couldn't you just write a simulator for a universal TM and prove the correctness of said simulator?

[@Jesse_359]

​@@cykkm You can compute everything but only within bounded time. The logical error they keep making is in the proposal that an unbounded time (or set of any sort) is a legitimate logical structure. Once you bound your questions at T-0 and T-Ω these questions compute to a final (and initial) state without paradox. It's not necessarily useful, particularly as the amount of computation time you require might equal the total amount of time available to you in all of existence, so from a practical standpoint it's meaningless - but it IS solvable in a purely logical context.

[@cykkm]

@@prototypeinheritance515 You can, if you in fact have the computer built and humming. Otherwise, you can't.

[@AnthonyFlack]

Well, an electronic computer is not really much help to understanding the concept, right? If you can follow a flow chart, you can conceptualise a program, and a computer's just a faster pencil. The computer could be imagined as a factory worker, following instructions with no training. It has a direct application to industrial labour, and of course the first "computers" were rooms full of people doing sums. Interesting to note that Richard Feynman started his career managing the human computer of the Manhattan Project in the 1940s, and ended his career designing highly parallel supercomputers in the 1980s, using the same ideas. Conway's Game of Life was devised on paper as well, ironically enough for such a classic computer program. He used to run it on a Go board. I think by the time Conway actually saw it running electronically he was already done with it and no longer interested. He'd already determined it was Turing Complete.

[@周品宏-o7w]

15:48 I want to point out this proof is not rigorous because Reverser requires one input to run properly, Halt Checker cannot evaluate Reverser without an input. If you want to know the rigorous proof you can find it in the Wikipedia page of halting problem.

[@tarmaque]

I'd like to quote a commentator on a Sabine Hossenfelder video: "I didn't understand this before watching the video, but after watching it I feel like I don't understand it on a much higher level."

[@upandatom]

😂

[@haniyasu8236]

I think what's even more wack than the halting problem are all of the weird conclusions in forces in broader mathematics and computer science. For instance, using it, you can show that there are number for which we can *never* compute. A prime example is Chaitin's constant, which is (in essence) the probability that a randomly generated program will halt. It's a perfectly well defined number (for a particular programing language, look at the probability that any program of finite size N will halt, then take the limit as N goes infinite), but we can *never* find a program to compute its digits, since knowing the digits would let you solve the halting problem. To see this, suppose you had a program of size N that you wanted to check. First, you generate *all* programs of size N and run them in parallel (by taking steps in all of them before moving on to the next step). Then, each time a program finishes, update a running tally of the proportion of programs that have completed. Finally, once that proportion agrees with Chaitin's constant to the first N bits, you know that *no more programs will finish*, so all of the remaining programs will never halt. But, since the halting problem is impossible, this means that the digits of Chaitin's constant could never be computed because that was what lead to the program working in the first place. What's even crazier though is that this doesn't just apply to computers, it applies to *us* as well. Since the human brain is Turing complete, this means that after the first few digits, it's literally impossible for us to ever know the digits, period. Which, idk about you, but it's just crazy to me to think we can know that a math problem has an answer, but we can *never* know what it is.

[@Anonymous-df8it]

'the human brain is Turing complete' Proof?

[@haniyasu8236]

​@@Anonymous-df8it Literally just the fact that you can write down a Turing machine on a sheet of paper and follow its rules step by step.

[@Anonymous-df8it]

@@haniyasu8236 How do you know that it isn't equivalent to an oracle machine with an incomputable oracle?

[@haniyasu8236]

@@Anonymous-df8it Well, I suppose I should have been more precise and said "Turing Equivalent". Not only can the brain simulate any Turing machine, but a Turing machine can also simulate the brain, so the the set of problems they can solve should be exactly identical. Said another way, since a Turing machine can simulate the human brain, then if the human brain could solve the halting problem (or compute Chaitin's constant), then a Turing machine could just by simulating what the brain did. Also, if you don't believe that we can simulate the human brain.. idk what to say. It's a physical system governed by physical laws we can simulate. It may be difficult, but I can't see how it'd be _impossible_.

[@Anonymous-df8it]

@@haniyasu8236 What would it take to build an oracle machine?

[@sofar55]

I'm still confused on the halt checker/reverser programs. Individually, Checker and Reverser returning running or halted makes sense. Check reads an outside program and says run. Rev says halt. Check then reads Rev and says halted. Rev then says run. These seem like sequential events and/or separate instances of each program. The description implies that Rev is causing the paradox by trying to run/halt simultaneously, but if Check can run on the outside program and Rev, shouldn't Rev be able to run on the result of Check multiple times also?

[@bananaforscale1283]

That confuses me too.

[@tallowisp8868]

TLDR: You do run Checker exactly once to check if Reverser halts or not. Long explanation: Let's assume we have a Checker program that always outputs if a given program halts or runs forever. Now we can write a Reverser program based on that exact Checker program. It's just a small extension that you add after Checker decided the output. The modifications for Reverser could be as follows: If the output of Checker would be "halts" add an infinite loop. If the outpout of Checker would be "runs forever" halt the program. So Reverser does not have an output. Reverser runs forever if the answer of Checker would be "halts" and halts if the output of Checker would be "runs forever". Now the crucial idea is not to run the programs multiple times. You do run Checker exactly once and give it the program Reverser as input. So Checker has to decide if Reverser will halt or not. The final logical step is a bit of an inception moment: Let's say Checker outputs that Reverser "halts". The crucial thing to realise is that Reverser is based on Checker so the only way that Reverser could halt is if Checker would output "runs forever". This means Checker has to output both "halts" and "runs forever" at the same time which is a contradiction.

[@shexec32]

The missing part is that Check is being recursively fed itself as part of the container. What does outer Check do if inner Check halts? Finally, what would happen in the recursive case?

[@BlackcapCoder]

The trick is that you pass the checker+reverser program as input into itself. Regardless of whether the input program to the innermost instance of checker+reverser halts or not, checker+reverser can neither halt, nor not halt.

[@InShadowsLinger]

So the explanation is: Suppose you have a program A that can decide whether any given program will halt (the halt checker). Then you create a new program B that has the program A in it and what ever you feed to B is immediately fed directly to A and based on A’s output B decides whether it is going to halt (if A say the inputs runs forever) or run forever (if A says input will halt). This is the reverser in the video. And now comes the important part that is not clear from the video: you need to feed B to itself. That is where the paradox comes from. If B was supposed to halt and you feed it to B, it will not halt and vice versa. Maybe it was implied in there somewhere with the “inception” but you have to squint pretty hard.

[@coolcat23]

There are many flaws in this video: 1. Turing's proof method (which is just a variant of Russel's paradox -- both can be recognised as diagonalization proofs -- not a new ingenious invention) only applies to computing devices with infinite memories. These do not exist. Any real computer has a finite amount of states and one can, in theory, check if a state reoccurs or not. The actual issue with checking termination with real computers is the exponential explosion of states. The theoretical limit show by Turing does not apply to real computers. 2. As Rice's theorem shows, this is not an issue that is specific to computers. It is a computability issue (or rather a semantics issue in self-referential domains), not a computer issue. 3. It is incorrect to state that a computer's universality automatically constitutes a weakness. Just use Turing-incomplete formalisms like Petri Nets or the typed lambda calculus without recursive types. One can then either guarantee termination or easily check whether it occurs. 4. In cases of practical interest, it is typically possible to proof termination for programs even when they are written in a Turing-complete language, e.g., by using loop variants. One does not have to say "This is impossible", one simply uses Hoare logic, for instance, and performs a termination proof. 5. Even though no universal halting algorithm exists, one can create very useful program analysers. Not even starting to recognise a large class of cases, just because there is a theoretical limit, would be foolish. 6. An operating system is not a "program that runs other programs" in the sense like an interpreter (a program) runs other programs.

[@lost4468yt]

If you have a sensor that measures reality (like most computers do), you can no longer do what you said in number 1 and compare the state. You can have the same state multiple times, but have different states later.

[@danielkohwalter5481]

I didn't see any contradiction on the way the halt problem was presented. The two instances of the reverser or the haltchecker are independent. The second one uses a different input from the first. Therefore, there is no problem to give different result. "Run forever if the haltchecker returns 'halt'". The second instance of reverser will run forever because the haltchecker program returns "halt", because it's analysing the reverser with its input. Its input is the output of haltchecker that returns "run forever". It outputs that because it sees the program "count from 1 to N until reach N" and its input, let's say "-1". Where is the contradiction?

[@tallowisp8868]

Yeah the explanation wasn't the best. While Reverser and Checker are independent programs the trick is to only run Checker once and give it Reverser as input. I just added a comment with a clearer explanation.

[@dogedev1337]

if you know some programming, consider this code: function doesHalt(program) { // checks if program halts and returns true or false } function paradox() { if (doesHalt(paradox)) { while(true) {} } else { return } }

[@danielkohwalter5481]

@@dogedev1337 Ok... so you run the function paradox... it is a self referenced function, and enters in an infinite recursion... so it's not a problem of the function doesHalt is possible or not. You can make function doesHalt(program) { return 0; } that the problem will be the same. Try for yourself. And she says that the function doesHalt receives both the program as its inputs. So, a parameter is missing. In this case, the input will always change, because the input of one instance is not the input of another instance.

[@njnjhjh8918]

@@danielkohwalter5481 Yes, a parameter is missing. It really irked me and the explanation doesn't make sense without it

[@Technium]

​@@danielkohwalter5481 When you say "paradox is a self referenced function and enters in an infinite recursion", you are making an assumption about how doesHalt works. Like you said, if doesHalt were implemented to just return false all the time, then paradox would halt just fine without any infinite loop or anything. In order for doesHalt to work correctly, it would need to "detect" that an infinite loop is happening in a more clever way, and this infinite loop detection is exactly the impossible part.

[@publicayers]

I’ve spent years studying computability. This is my new favorite discussion of completeness, consistency, decidability, and the halting problem. I love it!

[@skun406]

Are you just spamming keywords for yt algorithm lol

[@TheZoltan-42]

08:15 A note on the square root limit. That's not something that is part of being a prime number. From a mathematical point of view, you should check all k 1

[@CorwynGC]

No you really should NOT check past sqrt(n). No one did that when they didn't have computers.

[@TheZoltan-42]

@@CorwynGC From a practical point of view, of course not. But this has nothing to do with the maths. When you implement things, you always look for ways to improve and optimise, but that is not related to the definitions. Think about the definition of a sorted ordered list, and defining a function that leads to it from any set, which is pretty straightforward, and the dozens of methods we invented to implement the sorting.

[@CorwynGC]

@@TheZoltan-42 It has everything to do with the math. Math is all about optimizing. Newton's method for finding Pi does the same job as earlier methods, it is famous math merely because it does it faster.

[@prolarka]

I love this video for its last 4-5 mins. That part is always left out in other explanations. A huge thank you for making this video.

[@Jaabaa_Prime]

20:22 Turing had a PhD in Mathematics, there was no "Computing Science" curriculum in 1938, not even in Princeton.

[@kevinjin3835]

The Halting Problem: “Any observer is necessarily its own blind spot.”

[@christianmuller2863]

Danke!

[@jimf2525]

Great video. I love the detail and background. I rate this equal to Veritasium’s. I hope the Gödel is better than the other videos on it. Thank you and your team!

[@PasseScience]

I unfold here the diagonal argument of the end (someone asked it to me in a reply to my com so I copy paste it here if anyone else is curious about the same thing) Keep in mind that a program can be interpreted as data in the rest of this answer: What we are trying to find the existence of is a program Halt(x, y) that would tell you for *ANY* program x and *ANY* data y if x(y) eventually stops or not. (And of course you want such a Halt program to never be wrong and always give you an answer in finite time). To show that such a Halt program can't exist it's enough to show that if it was existing you could have a contradiction. Let's consider the following program: Paradoxe(x): If Halt(x,x) loop else stop; So here I built the program Paradox that is using inside the program Halt (that we initially supposed existing for the sake of the demo), Paradoxe takes an input x and will loop forever if Halt conclude that x on x stops and stop if halt concludes that x on x never stops. It's important to see that if Halt exists and is of finite length then Paradoxe exists and is of finite length (I just built it above). Now look at what happens if you run Paradoxe(Paradoxe): it will loop if Halt concludes Paradoxe(Paradoxe) stops and stop if halt concludes Paradoxe(Paradoxe) loops, which is a contradiction. So the only assumption we made at the beginning was necessarily wrong: a program Halt(x,y) cannot exist (A program that would tell you for *ANY* program x and *ANY* data y if x(y) eventually stops or not.) because if it did we could reach such a paradox.

[@agnosticpanda6655]

It's a great breakdown, but I think you should have made it even more clear that decidability has absolutely nothing to do with computers and is solely based on logic. The halting problem could have been discovered by the greeks.

[@michaeldebellis4202]

The halting problem is about First Order Logic (FOL) not propositional logic. The Greeks only had propositional logic (FOL without universal or existential quantification) which is decidable and to which the halting problem doesn't apply. Also, it has plenty to do with computers. The early years of AI were in many ways all about the halting problem. Logic is seen by most people as the most powerful way to describe and reason about problems. At least the most powerful way to semantically reason, not using numeric machine learning algorithms. Because of the halting problem no automated reasoner that supports the full power of FOL can be guaranteed to terminate. Hence, much of the history of semantic AI has been about finding subsets of FOL that still provide powerful languages but are guaranteed to terminate and to work with decent performance. That's why the first expert systems were based on fairly simple forward chaining rules. If-then rules and modus ponens are a very limited subset of FOL but they were all that computers of that time could support. Since then there have been more sophisticated languages like Prolog and more recently the Web Ontology Language which supports Description Logic, a much more powerful subset of FOL than just rules.

[@michaeldebellis4202]

Also, another application of the Halting problem is to prove that it is impossible to have any general purpose algorithm that can analyze code and prove that the code will terminate. That's why it's called the Halting Problem.

[@thomasharris9059]

@@michaeldebellis4202Nobody disagrees this is intimately linked to computer science, but the other commenter is correct: computers are merely one application of decidability. The video should have made that clearer. It’s like making a video on Godels incompleteness theorems and only talking about number theory. Need to loop it back around.

[@michaeldebellis4202]

@@thomasharris9059 "Nobody disagrees this is intimately linked to computer science," The first sentence in his comment that I was replying to says: "decidability has absolutely nothing to do with computers "

[@thomasharris9059]

@@michaeldebellis4202 It doesn’t. Eulers number doesn’t have anything to do with calculus either even though that’s its greatest application.

[@raman_14264]

Contradiction:- Jade can't run forever and Halt at same time.😮😮😮 Truth :- Jade this lesson was awesome. Cant wait for next lesson. Humour :- Watching 5 Jade's at same time was literally fun. Your editor deserves a promotion.

[@Misteribel]

Just halted all developers in the company to watch this! You've a gift in explaining ❤

[@Briyan-vh9ew]

Great Video, Didn't quite understand why the reverser would change? since its using the input from the previous halt checker output? and not the current halt checker which uses the reverser output as input. 16:00.

[@pauljs75]

I guess part of this is why you learn how to make set-reset latches in Factorio when wanting circuit controlled processes to stay in a somewhat steady state without excessive fluttering. You throw things into a range of acceptability rather than an exact value, so you don't get the true/untrue superimposition thing happening.

[@khaitomretro]

ENIAC wasn't the first programmable computer. It wasn't even the first electronic programmable computer. It also needed to be rewired to reprogram it. The Z3 was the first programmable, fully-automatic, electromechanical, digital computer. Colossus was the first electronic programmable computer. However, the the first one we'd recognise as a computer (using von Neumann architecture, with memory to store both program and data) was the Manchester Baby.

[@duggydo]

I saw this video and halted what I was doing to watch 😊😂

[@time3735]

Same.😂

[@slugface322]

Agreed I do the same everytime she posts a new video.

[@guillaumelagueyte1019]

You can't prove it!

[@christianheichel]

That's a dad joke.

[@tsebomonatisa4850]

You so funny. 🤭

[@jsflood]

Great video! At 14:00 regarding the eternal loop ? All computers programs have a fixed size variable in memory, as the number stored in that memory is added by 1 in each iteration it will eventyally wrap around. If this is a signed variable it will HALT wen it comes to -1. But if the variable is unsigned, there is no negative numbers and therfore it will never wrap around to any negative numbers and it goes into an eternal loop as the condition is never met.

[@stefanl5183]

Indeed! Great observation! further I would add that if you are checking to see when the number goes negative, you'd have to be using signed variables otherwise "negative" would be undefined and have no meaning. So any such program would have to be using signed variables. Therefore the program would indeed halt.

[@trxe420]

I have been a software engineer since the mid 90's and often I take for granted just how incredible computing actually is. To think of what we have accomplished and the complete paradigm shift that is coming, well, my peers may have programmed us right out of a career but it was worth it. It is interesting to me that even in computer science nature governs causality and prevents paradoxes.

[@davidioanhedges]

What Thomas J. Watson considered a computer ... would now equate to a state of the art supercomputer ... there are around 5 ... (one is an IBM) It is generally consider the the first modern computer was Colossus ... it was before ENIAC (ENIAC had to be partly rebuilt to do something different... Colossus with just a paper tape)

[@KdUqPdI]

I can picture it: 10000's of years from now Jade materializes before the ruler of the universe Rolo's Basilisk to answer for her crimes but she isn't worried. She remembers her arcane studies and starts to sing. The Halting Song of the Cyber Witch! The Basilisk twitches, then goes limp collapsing dead to the floor. Jade smiles and takes her seat on the throne.

[@johnchessant3012]

It's so awesome when such an important result in math can be understood relatively easily

[@WWLinkMasterX]

I've seen this topic presented dozens of times, but your visual example with the Halter/Reverser characters is probably the best, most digestible way I've ever seen it done.

[@zacharysmith9588]

Very well done as always! I'm looking forward to your video on the Incompleteness Theorem

[@silvergolderlens7205]

What about programs that either halt or don't depending on the input? For example a program like "Count up from 0 until the given input is reached". For input 5 it will halt, for input -1 it will run forever. The reverser is such a program. For Turing's case, the Reverser code fed to Haltchecker has a different input than the Reverser running Haltchecker so it seems reasonable that one halts and the other does not (one inside the other).

[@DJUniverse1]

Yeah, I think It wasn't clear enough in this video. The Haltchecker should get as input both program and some input for the program, and then decide wether the program will holt on this specific input or not. In the alan turing proof, he really created this revresa program as represented in the video, but the input is so important, and the proof is wrong without mentioning it. It goes as follows: Given a reversa program, it's own description. Let's call it A(A) It sends it's input and the program description to the Haltchecker (let's call it Halt) Which in this case will be: Halt(A,A) And if Halt(A,A) returns "halt" Then, it won't halt And the opposite. (We can give a description of a program as an input to the same program, because the program description is just some sequence of characters which can be counted as an input) Then we ask whether A(A) halt or not. If it does, it means that Halt(A,A) didn't halt which means that A(A) doesn't halt, which is a contradiction. The opposite is exactly similar, and in both case we get a contradiction which leads to the assumption of such program to exist to be false. So in conclusion, the only difference between the real proof and the proof described in the video is just the input of the program that we check upon the program, whether it will halt on this input or not. Because your right, the input matters, and it can be that on one input it halts and on another it doesn't.

[@silvergolderlens7205]

@@DJUniverse1 Ok I understand now. Thank you

[@jacksonstarky8288]

I studied a lot of formal logic and took a lot of computer courses when I did my cognitive science degree... twenty-three years ago now. Ouch. The most interesting results I found among everything I read over my five years (yes, I took an extra year; originally was going to do a history major, because my school wasn't big enough to offer a philosophy major) were from Godel and Turing. Philosophy of mathematics is a subject I wish I'd been able to study formally in greater depth.

[@rustyshimstock8653]

Exceeds expectations. Thanks!

[@spark_coder]

I feel like this version of the video explains this concept so much more intuitively and in depth than the previous version. Thank you very much 🎉

[@happybp]

Thanks!

[@BlackKingdomEnterprise]

Love your videos...keep contributing more...thank you❤

[@luxhey]

Shout out to my fellow programmers who knows the program counting up from 0, and halting when it reaches -1, would actually halt. At least if we do not assume infinite memory. Gotta love integer overflow! Jokes aside, that detail is not important for the purpose of this very informative and well done video! Keep it up! :D

[@EthanAQueen]

This depends entirely on how the compiler or interpreter handles all the bits being set. You could even write functions that do math based on binary and not use the default behavior. Quite frankly, the default behavior is stupid.

[@luxhey]

@@EthanAQueen That is correct. I assumed signed integers, and the most common compiler/interpreter behavior.

[@prototypeinheritance515]

The assumption is that the program runs on a turing machine, which doesn't have fixed size integers.

[@unquotequasiquote7076]

quick parenthesis: proof assistants are way closer to mathematics than regular computer program. Proof assistants are type system (like rust/haskell's type system) that are mathematically proven to be equivalent to set theory (its reallllllly far from the chatgpt's field). The compiler (because its a language) then helps the programmer type check its program and thats the proof!

[@Tletna]

The Halting problem's always confused me. If the reverser does the opposite of the halt checker, wouldn't the halt checker then change its result and then the reverser would change its result and it would just keep going? So, there's no paradox there. There might be a paradox if you have another halt checker try to peer into the first pair of halt checker and reverser (since they'd forever be alternating). Edit: The only big problem I have with the reasoning going on in Jade's video is this: Is the premise that modern computers are "universal" even true in the first place? We're logically assuming that universality leads to undecidabiity. Now, I think this logic was persuasive is already debatable. But, *even if* we agree with the logic there, it still needs a valid premise. Are modern computers *truly* 'universal'. I would argue that even though there seems to be an *infinite* number of functions a complex and powerful enough computer can perform (given enough power/time), I don't believe that computers could ever be infinitely infinite, meaning to an infinite cardinality of infinity. I don't believe electronic, magnetic, or quantum states are infinitely broad and deep. In fact, they're very limited.. on/off.. or however many quantum states there can be simultaneously (but that number isn't infinite). So, even if your processor can process infinity math/logic operations at the speed of light minus the slowing from heat etc, the machine it still only processing N * infinity amounts of data per time unit. Essentially, due to the limit of the design of how a modern computer works, it cannot possibly do everything. So, it is not 'universal'. My argument would be that there is no such thing as a *truly* universal computational machine or algorithm. It doesn't exist. I am not yet able to prove this unfortunately. So, that's where I get stuck.

[@knopfir]

the thing i get the least is, how is it a logical contradiction? If the reverser changes state between running forever and halting based on the input given to it (by the haltchecker), then why is the fact that it halted/ran infinitely in the PAST a logical contradiction? you changed the input. you restarted the program and told it to check again and give you an output.

[@taziir443]

The paradox is in the definitions of having the programmes halt forever vs run forever. If halt checker's status can be changed because of reverser, it's no longer able to complete it's function of a permanent state of running or halted forever. At least that's my interpretation- happy to be proved wrong

[@rmsgrey]

The key to the paradox is that the halt checker itself always halts. If it gets stuck forever alternating, then it's not a halt checker after all.

[@Tletna]

Thanks for the replies folks. I just don't understand how the infinite alternating is a problem. If there is another checker that can poll to check the state as quickly or quicker than the halt checker and reverser, then we can always know the current state of the halt checker and then by inversing that the reverser. So, we *do* always know the state of the reverser and we know it is stopping and going (therefore not halting). We can therefore make a new halt checker that is slightly different than the original that looks at the pattern of the reads from the checker polling the original halt checker and uses that to determine if the original reverser halts or not. I think the only possible problem with this is: how does the new halt checker *prove* that the pattern of stop/go/stop/go/stop/go goes on forever and isn't just going to go on for like 50,000,000,000 cycles and then stop? I think, if anything, *that* is the problem, not that the original halt checker and reverser alternate but that we don't know for how many cycles they will alternate.

[@joshuataylor2105]

The explanation in the video is subtly wrong. The haltchecker should be the outermost program, which is then unable to answer it's question about reverser. I can't remember exactly what input reverser is supposed to be given here to make that work though. (It's supposed to be haltchecker again, but in a way that isn't an infinite nesting of programs.)

[@tallowisp8868]

Since there seems to be some confusion about the halting problem explanation let me try to explain it a bit better. It's really hard to get right and make it understandable. The rest of the video was fantastic but that explanation was not the best imo. Let's assume we have a Checker program that always outputs if a given program halts or runs forever. Now we can write a Reverser program based on that exact Checker program. It's just a small extension that you add after Checker decided the output. The modifications for Reverser could be as follows: If the output of Checker would be "halts" add an infinite loop. If the outpout of Checker would be "runs forever" halt the program. So Reverser does not have an output. Reverser runs forever if the answer of Checker would be "halts" and halts if the output of Checker would be "runs forever". Now the crucial idea is not to run the programs multiple times. You do run Checker exactly once and give it the program Reverser as input. So Checker has to decide if Reverser will halt or not. The final logical step is a bit of an inception moment: Let's say Checker outputs that Reverser "halts". The crucial thing to realise is that Reverser is based on Checker so the only way that Reverser could halt is if Checker would output "runs forever". This means Checker has to output both "halts" and "runs forever" at the same time which is a contradiction.

[@rarrmonkey]

If you redefine set theory so that sets do not include themselves (or derivatives there of) you avoid contradictions and "solve" the halting problem. A = X & A [ X 0 ] If the result of a question is not dependent on the result of the question everything is good. Or if you allow answers to be [Yes, No, Circular Reference] you might be able to answer all question in theory.

[@CorwynGC]

Not necessarily. There are plenty of questions for which answering could take forever. Imagine trying to find a Fermat's last theorem solution before the proof that none exist. No way to know if the program will ever halt.

[@handschich7736]

Never heard a non-german speaker that spelled the word "Entscheidungsproblem" as good as you did! Good job! By the way: It's also a really great video!

[@RAJSINGH-of9iy]

16:43 I didn't get the point there. Both reversor were diff programs ,right??? Why that would be a contradiction??? Kindly clear my point.

[@GlassDeviant]

If a computer (non-quantum) counts with signed integers (the default) from zero upwards, it will eventually reach the limit of its bit width and loop into negative numbers, then count back up until it reaches -1.

[@erikblaas5826]

... unless said computer program has an overflow check, then it will simply return an error like; "can not calculate / overflow" and terminate programming. Wich in turn will also halt the program.

[@GlassDeviant]

@@erikblaas5826 I'm speaking of default behaviour. You can attach alternate algorithms to anything.

[@ZiggyGrok]

Unless the compiler optimizes the check out because signed overflow is undefined behavior and converts the loop into an infinite loop

[@ZiggyGrok]

But also, her algorithms clearly assume an abstract Turing Machine, which has no such limits

[@GlassDeviant]

@@ZiggyGrok The premise is that the question breaks actual computers, not make believe computers.

[@CovidIslandDiscs]

I thought the Turing non-halting and Godel's incompleteness theorems were the same thing. Roger Penrose in the Emperor's New Mind presents it like that.

[@KohuGaly]

They are related. The core principle of the proof is the same. They both use the same method to construct a counter-example to the hypothesis, thus proving it false.

[@leof5545]

I THINK EVERYONE GETS THIS WRONG, PLEASE HELP ME UNDERSTAND: You can't just input a program alone in the reverser, as the reverser contains haltchecker which needs a program AND a test input. In the presented scenario, haltcheker would "loop" just waiting forever for its inputs to be completed (remeber, its missing the test input for the inputted program), so the whole reverser would enter a true "loop".

[@nobodythisisstupid4888]

I thought it was incredibly interesting when I realized that the Halting Problem, Russel’s Paradox, and Godel’s Incompleteness Theorem were in some way all describing the same fundamental logical idea when viewed through various lenses (computability, set theory, and generalized formal logic). Different conclusions are drawn from these different approaches but they all touch on a fundamental principle about the limits of logic. I felt incredibly validated when I discovered that these were all connected because they were all a form of a diagonal argument, and I found some other theorems that also were proved with a diagonal argument.

[@your_butter_chicken]

I just wanted to hug Hilbert so bad after the mega-realistic animation of him crying 🥺

[@masterchiefburgess]

Learned about the halting problem back in 1984, in my 3rd year computer science course "Foundations of Computer Science" as part of my computer science degree. A fascinating concept!

[@aleksandarstevanovic5854]

i love your storytelling skills :) lets dive in the haltchecker, how would you write it, "wait for the output, if you get it return that it doesnt have infinite loop", now... if the program runs fine haltchecker will run fine, if program gets stuck haltchecker will get stuck... if you say to haltchecker "wait for an hour, if you dont get the result say it has an infinite loop", now its not a haltchecker, program may run fine but slow, let say an hour and five minutes.... now for workaround, haltchecker v3 will be "look at this app, will it run? BUT WITHOUT ACTUALLY RUNNING IT" to avoid getting it stuck, this is the impossible problem, no matter how sophisticated technology haltchecker cannot exist

[@TarasZakharchenko]

Sure we cannot decide whether a program is halting or not, but we can design programs in that way that they would halt every time. One example: limit program length to some finite size, exclude recursive calls from source, exclude loops and you have guarantee that your program will eventually halt. Of course such limitations are limiting number of programs that may be written, but maybe more fine tuned limitations will help us to design more practical and safer software.

[@KohuGaly]

In practice, you often need the exact opposite - a program that provably never halts. For example, web servers, or control units in engines, or even most desktop applications (you don't want your web browser, game or excel to halt in any other way than proper shutdown).

[@CorwynGC]

The halting problem is almost never a concern in REAL WORLD computing.

[@KohuGaly]

@@CorwynGC I have to disagree on that. The halting problem has a pretty serious impact on most real world programming, because it makes certain programming tools impossible. If halting problem had a solution, you would not need to rely on approximate heuristic solutions to stuff like optimization, virus detection, unit testing, compilation, etc. HP is not an issue for most programs most software developers write, but it very much has is an issue for tools they make those programs with.

[@TarasZakharchenko]

@@CorwynGC as the author highlighted, the problem is not just about program halting itself, but quite big class of problems which are closely tied to idea of completeness.

[@TarasZakharchenko]

@@KohuGaly sure but it is always possible to split the program into pieces which are supposed to be computed withing finite time-span and use intuition and common sense to ensure the those pieces will run in infinite loop as designed. The problem is that we cannot keep in mind program design altogether so we have natural limitation.

[@jeffdege4786]

I have to tell you, arguments about computability might convince your faculty advisor, but they are a hard sell for a customer. I once had a customer demand that a complicated scheduling routine always return the optimal schedule, and rejected the idea that it find a near optimal. That finding the optimal was an NP problem didn't change his mind.

[@mrau83]

The problem I have with the halting problem is that it approaches the problem from the perspective that one program will >>definitively and unavoidably

[@DavidAntrin]

The halting problem doesn't say that you can't figure it out for any particular program. You might be able to. It's that you can't do it in general.

[@mrau83]

@@DavidAntrin Both yes and ... no. The thing is that the halting problem is presented as something different than any other problem that people have with mathematics as if the computer world was in some way distinct and in general inferior but.. assuming that self aware machines are possible then there is no difference between halting problem and for example incompleteness problem addressed by Godel and his theorems. Basically the halting problem is not solvable if math is incomplete -- I do understand that when Turing was dealing with the halting problem computers did not exist and it was not known how exactly they (would) work but still this is something that nowadays should make the halting problem a footnote, an interesting comment to the Godel incompleteness theorems and that's most probably it. I'm not sure whether I'm expressing myself clearly but in essence the point that I want to show is that at least I don't see a good reason to rename stuff that already been addressed and proven and act as if it's something different while at the same time provide a flawed example that as a side effect also makes it look as if it was something different (due to the assumption that a program would need to run another program [would need to run itself in the given example] to be able to determine whether the program halts and also due to the flawed example presented in this video: that the program that for an input received itself means that the main program running it's own copy can't have two contradictory outputs). I'm not arguing against the conclusions, I'm against the flawed example that is considered and presented as a valid one.

[@devluz]

1:35 Just spent a while reading about the first digital computer. Looks like there is quite some disagreement which one counts as the first. Every time I read about these topics it makes me question patent laws ... we always learn in history about "the first" but once you look it up you realize history is a lot more complicated.

[@meharomnediakala397]

Hi Jade, I love to see your fascination with mathematical paradoxes! These mind-bending riddles have indeed captured the imagination of thinkers for centuries, pushing the boundaries of our understanding. Your explorations into paradoxes like Russell's Paradox, the Barber Paradox, and the Liar Paradox reveal the inherent limits of classical logic-a system rooted in principles established over 2000 years ago. While this framework has served us well, it's fascinating to see where it bumps into its own constraints, leading to seemingly impossible situations. However, consider these paradoxes not as endgames, but as invitations to venture further. Our current logical framework, which deduces that statements must be either true or false, is just one perspective. Quantum mechanics has taught us that reality may defy such binary classification. For instance, particles can exist in states of uncertainty until they're observed, a notion that defies the bivalent nature of classical logic. Remember that what our intuition can perceive is often shaped by this classical logic, subtly guiding our "gut feelings" about what seems right or wrong. Yet, intuition can sometimes lead us beyond the black and white boundaries of traditional logic. It can point us towards a spectrum of possibilities that classical logic might neglect. So, while paradoxes appear to present unsolvable puzzles, they actually remind us that our tools for understanding the world are still evolving. These paradoxes aren't just curiosities or dead ends; they are challenges to our current way of thinking and signposts indicating that there are uncharted territories of logic and reasoning to explore. They underscore the importance of adaptability in our logic and the potential for new systems of thought that can encompass the wondrous complexities of the world we strive to understand. Keep delving into the intriguing world of paradoxes, and let your intuition and research guide you toward ever-expanding horizons of knowledge!

[@RomanHold]

5:20 no! Knowing some problems can't be solved by any computer or human is simply the definition of logic. Because when that happens the question (like the collatz conjecture) is constructed in such a way, that the answer "lies outside of the room of definition of the classic logic" and it basically is impossible to answer with either "yes or no". Because it is a 50% true and 50% false statement. But you can have "logic" or "magic" written on condensators. Let's just hope you don't get the opposite of that which you wanted like what they do with the negative sign and numbers with a imaginary unit and that circle scam.

[@peters616]

Ironically, there's something about how Turing proved the halting problem is undecidable that implicates a kind of infinite loop itself. Because of the recursion involved, the halting problem analyzes the program that analyzes the halting program, I think it is axiomatic that an infinite loop will occur and the computing resources required to solve the problem will become infinite. Maybe a separate problem is whether it's possible to prove the halting problem is decidable for any program that does not call the halting program.

[@johneckelkamp9655]

If one assumes that the human mind works like a computer (albeit an almost incomprehensibly complex one), then it makes sense that we are limited in what we can underestand. We our thinking selves have the same limitations as any computer.

[@lorigulfnoldor2162]

"A general case of a program" is a pretty weird notion, though. You do not need Turing and his, no doubt, genius work to point out no code can ever crack the "general case". To point this out, simply imagine a program whose code length is more than the number of discernible states of the universe. No code inside of our universe can EVER decide ANY thing for the program of such a size, because no computer inside of our universe can host enough memory to write down this monster-program! Also, you sadly forgot to mention that "halt-decider" works not simply on "reverser" of any kind, but on a "reverser" specifically feedbacking its output into the SAME "halt-decider". This non-mention makes the explanation a bit hard to follow =(

[@Entikai]

6:47 - "Imagine a set that contains all sets that do not contain themselves. Does this set contain itself?" Yes it does!!! If it does, that means that it holds all self-missing sets plus one self-containing set (itself). And that's not a big deal because you forgot to say "only", as in "Imagine a set that contains all sets that do not contain themselves, -and only those sets-." If you said that, it would be a paradox. But not specifying that means that maybe our set can be a mix set and contain all self-missing sets plus one self-containing set (itself).

[@prototypeinheritance515]

you've just avoided the question

[@Entikai]

What do you mean?

[@prototypeinheritance515]

@@Entikai Because something is an element of a set if and only if it fulfills the condition, in this if the element is a set that doesn't contain itself. What you're talking about is a superset of the original one because you're ignoring the the "only if" part (that's just how sets work). That's how you're dodging the question, you're talking about something else entirely. Your set is not the one that contains all sets that contain themselves, because it does contains itself. An example for the implicit equivalence is the Set P = { x ∈ℕ | x is Prime}. It doesnt mean x ∈P ⟹ x is Prime, because non Primes would be allowed. It means x ∈P ⟺ x is Prime

[@Entikai]

Ok, I didn't know the definition of a "set" and a "superset". If a word "set" promises exclusivity, then the paradox works. In my original post, I said maybe our set can be a "mix set" not knowing that that breaks the definition of a set.

[@kolty99]

Great episode. Also I think somebody should mention the acting was great. 16:26, I really felt bad for the Haltchecker.

[@Makebuildmodify]

“if a PhD student was trying to design an algorithm to do any of these tasks then supervisor can point out that their Endeavor is futile”, does this mean that the supervisor can only point out specific futile endeavors but not ANY endeavor?

[@thecasualengineer99]

hi, thanks for this thought provoking content. A question i must ask about a count up program. If number representations did not have limitations, then I would agree that the count up would never reach -1. Computationaly, the numbers used are represented by a limited bit width, and depending on the CPU, programing and hardware detection, the variable counting up will either flag overrun state or continue with all bits including the sign bit set as a series of nagatives counting towards zero. The question is: Would haltchecker be capable of determining the hardware detection of an overrun and flag it?

[@Nerdule]

You've actually hit on an important qualification that got left out of the video: the Halting Problem *technically* only applies to computers with infinite memory. For computers with finite memory, it's at least theoretically possible to determine in finite time whether they run forever or not: there's only so many possible states their memory could ever be in, which means if you wait long enough and keep track of every single memory state, eventually it will either repeat one (in which case it definitely loops) or halt. However, in most cases this doesn't really help much, because the number of possible memory states is *enormous* - if an arbitrary program makes use of even 64 bits of memory, that adds up to 2^64 possible states, which means you could potentially have to wait up to 18,446,744,073,709,551,616 steps in the worst case before it's used up all of them, so it's not really practical to just try it and see if you can't analyze it otherwise. For simple programs like that one, though, it certainly is possible to analyze that kind of thing! If you know that big numbers eventually wrap around to negatives, then you can prove mathematically that it'll get there eventually if it keeps counting up, which means that haltchecker (which encompasses every strategy for analyzing programs and every method for deciding which strategy to use) would definitely catch it.

[@prototypeinheritance515]

haltchecker is an abstract program which doesn't run on any real computer and isn't restricted to any specific architecture. But that doesn't matter because this abstract machine can emulate any real machine, so the answer to your question would be yes. The converse is true, any abstract algorithm can be implemented any real (turing-complete) computer, which includes unbounded integers. I personally find it a bit irritating that everyone seems to always assume that integers in programs must always be fixed size; while there are languages that have arbitrary-precision integers as a default.

[@Nodalthree]

Write a program that can modify itself (replace its instructions in the program) based on the initial data that identifies what is to be accomplished. Meaning a program that reads the initial data and modifies itself to produce a checking account spread sheet, but can also read the initial data and then draw a diagram. One program that can change itself to address and manage the data in its memory.

[@RonRosser]

If a computer cannot come up with true random number. Why do people think that a computer can become self aware?

[@DrMikeHeffron]

Thanks!

[@_kopcsi_]

as far as I can remember she has already made a video about the halting problem. although this video has a wider and more global scope. and I really liked it. I could rephrase the essence of the topic in the following way: Hilbert's program actually lead to the realisation and revelation of two fundamental trade-offs: one related to the consistency-completeness duality and one related to the universality-decidability duality. the former is related to logic and Godel's work (incompleteness theorems), while the latter is related to computation and Turing's work (halting problem). and in a sense these two big topics also form a duality (static logic and dynamical computation). but there are other similarities and deep connections as well. e.g. the Russel paradox mentioned in the video, Godel's theorems and even the halting problem are related to self-referentiality. and as much as I am not sure that these seemingly insurmountable fundamental limitations are in fact insurmountable, I am as sure that if they can be circumvented somehow, then it can be achieved precisely through a deeper understanding of self-referential structures (and in this field Douglas Hofstadter laid the first foundations ). furthermore, I find it fascinating that this halting problem is just as fundamental and universal as e.g. the NP-completeness in computational complexity theory, where every NP problem could be solved if we could solve the "guessing problem" that hides deep in the heart of NP-completeness. but if we dive into Godel's theorems we can find similar pattern: Godel's theorems are about nothing but the problem of logical induction (and the problem stems from the fact that consistency is conserved/invariant only for deductions, but not inductions). if we could solve in a general way the induction problem, we could actually find everything. this is why I believe that these seemingly far and disconnected problem classes (which are already some kind of hubs of many many problems) have a common core. what is more, I do believe that even the so-called causality dilemma (how something can be created from nothing) is related to these problem classes. so I am not 100% sure that these fundamental problems and questions can be solved and answered, but if yes, then we are just ahead of a huge leap in science and understanding.

[@SandroSmith]

Oh, so it's not only me who had deja vu

[@killerbee.13]

The difference is that P and NP are both classes of decidable problems. Even if we could prove that P=NP and then run every NP-hard problem in P time, we would not in any way expand the boundaries of computability. All we could do is solve problems faster. She didn't really go into the mathematical foundation of universality, but there's really no way to get around it. The only thing that might be able to solve uncomputable problems is physics, which exists outside of logic and math, but so far even quantum mechanics has never even so much as suggested a lead in that direction. (Such non-computer solvers are called oracles) The universe itself can "solve" some problems quickly, which is what quantum computers are all about, but none of those problems is one that a classical computer couldn't also solve, given more time. And of course even if we did find out that physics is undecidable, which I doubt, I'm not sure we'd be able to get anything out of it, since we by definition wouldn't be able to prove using mathematics that it was solving the right problem to begin with. You can't prove an oracle is accurate, you have to assume it is. The self-referentiality in Russel's paradox was "solved" in math by making an infinite stack of layers of reference, where each layer can only refer to the layers beneath it. We call those layers "orders" of logic. Essentially, you just sidestep the problem. If you want to prove anything about first-order logic, you use second-order logic to analyze it. If you want to prove something about second-order logic, you use third-order logic. However, you can't just continue that forever. The system can never prove absolutely that it is consistent, even with infinite layers, because each layer is only as consistent as the next layer up, and there's no last layer to prove anything with. This is the kind of induction that doesn't actually produce a result. So, we can't actually prove that mathematics is consistent, we can just say that we have never managed to find a paradox within the current model, and if we did, we'd have to make the smallest possible adjustment and see what we can keep, as we did multiple times in the past. The similarity between Gödel's theorems and Turing machines is that both of them involve turning complex things into numbers. Just regular numbers, which are simple enough that you have to have them in order to even have math at all. Since you can do that, you can never completely remove those complex things from math. Turing machine programs don't directly look like numbers in the normal mathematical models but the conversion is simple, and in fact we use such a conversion for real computers. Every file, including programs, is just a (really, really huge) number whose digits (in binary) have a special meaning. So you can't do the first-order logic trick for Turing machines, since the input of a Turing machine is a number and a program is also a number. Thus, if you could ever stretch the limits of computability, you could turn that method into a number and feed it into itself. There's no such thing as a second-order program that operates on first-order programs as inputs because the second-order program would be a simple number and thus you could feed it into *itself*, with no need of a third-order program.

[@_kopcsi_]

​@@killerbee.13 I didn't say that P and NP classes of problems are not decidable problems. I said this: "... this halting problem is just as fundamental and universal as e.g. the NP-completeness in computational complexity theory, where every NP problem could be solved if we could solve the "guessing problem" that hides deep in the heart of NP-completeness. but if we dive into Godel's theorems we can find similar pattern: Godel's theorems are about nothing but the problem of logical induction (and the problem stems from the fact that consistency is conserved/invariant only for deductions, but not inductions). if we could solve in a general way the induction problem, we could actually find everything. this is why I believe that these seemingly far and disconnected problem classes (which are already some kind of hubs of many many problems) have a common core ..." this quoted train of thought means that the three topics (which are related to problems and their solvability); the NP-completeness, Godel's incompleteness and Turing's halting problem; have a common core, a similarity. and this similarity is the fact that: 1, if we could somehow solve an NP-complete problem, then we could solve any NP problem. 2, if we could somehow generalise induction (so guarantee the conservation of consistency just like it is inherently guaranteed in the case of deduction) and thus automate inductive reasoning, then we could formulate any a priori knowledge. 3, if we could somehow solve and bypass the halting problem, then we could solve many many other problems as well. "The only thing that might be able to solve uncomputable problems is physics, which exists outside of logic and math, but so far even quantum mechanics has never even so much as suggested a lead in that direction." -- I disagree. physics is not outside of logic and math. on the contrary, the most fundamental layers of physics lie deep down in logic and math. "The universe itself can "solve" some problems quickly, which is what quantum computers are all about, but none of those problems is one that a classical computer couldn't also solve, given more time." -- classical computers practically unable to solve certain problems (this is what NP problems are all about). this is one aspect of computational boundedness. but it is interesting to note that if we could solve an NP-complete problem, then we could create such an algorithm that has a similar logic as quantum computers (parallel rather than serial sequences). "The self-referentiality in Russel's paradox was "solved" in math by making an infinite stack of layers of reference, where each layer can only refer to the layers beneath it. We call those layers "orders" of logic. Essentially, you just sidestep the problem. If you want to prove anything about first-order logic, you use second-order logic to analyze it. If you want to prove something about second-order logic, you use third-order logic." -- yes, I know all of these. but I am not 100% sure at all that this is the correct way to handle these paradoxes and contradictions. this applied method's essence is to remove impredicativity. but is it really the best to remove self-referentiality in this way? in my country there is a saying that "He throws out the baby with the bathwater." which perfectly fits in this topic. when those very smart mathematicians and logicians (Russel et al.) tried to fix the fundamentals of mathematics, they actually over-regulated the system that we call mathematics. just think it over. by eliminating this kind of self-referentiality we didn't eliminate only contradictions (where statements can be neither true nor false) but also tautologies (where statements can be both true and false). e.g. the set of all normal sets cannot be normal, but it cannot be abnormal either, but the set of all abnormal sets can be both normal and abnormal. this kind of feature and structure is completely eliminated from set theory, for example. I do believe that there is a fundamental error here and in the not too far future it will be fixed, what is more, this will be a starting point of a huge scientific leap. self-referentiality will be the key to many many mysteries in current science (especially regarding logic and philosophy of science). - by excluding impredicative logic, what happened figuratively is that with theories based on predicative logic, we are able to formulate the relationships that exist at the true-false (existent-nonexistent) level, where we approach reality from the outside with theories based on direct-reference. however, this type of reduction in itself limits our possibilities in understanding and describing reality, because we cannot formulate a comprehensive, consistent theory on the true-false (existent-nonexistent) level (since existence itself is based on impredicative logic). - with theories based on impredicative logic, we would able to formulate relationships above the true-false (existent-nonexistent) level (tautology-contradiction level: the possibility of existence and the lack of this possibility of existence), where we could approach reality from the inside with theories based on self-reference. with the help of impredicative logic, we could determine the consistency range of the universe, and thus the decomposition of "possibility of existence" and its inverse (“impossibility of existence"). "However, you can't just continue that forever. The system can never prove absolutely that it is consistent, even with infinite layers, because each layer is only as consistent as the next layer up, and there's no last layer to prove anything with. This is the kind of induction that doesn't actually produce a result. So, we can't actually prove that mathematics is consistent, we can just say that we have never managed to find a paradox within the current model, and if we did, we'd have to make the smallest possible adjustment and see what we can keep, as we did multiple times in the past." -- yes, this is why this method is just a temporary strategy. and considering the deep logic of this method we can realise that religions and even the current scientific cosmological model (big bang theory) do the same. we take the question and postpone the answer by adding new layers and pushing the answer. that is, we postpone the compulsion to answer by adding new and new levels. e.g. by inserting the god (creator) entity, and so religions push the causality dilemma ("how something came into existence from nothing") one step further. why? since it sounds nice that an omnipotent created everything, but it does not explain where this creator comes from. the big bang theory applies exactly this logic, only it hides the unknown answer, or more precisely the compulsion to answer, behind a mathematical singularity rather than a creative entity. this is why I mentioned above this causality dilemma, because I do see analogies with the other sets and classes of problems. I am convinced that in the future we will have a better logical framework for and logical description of reality which will inevitably built on the concept of self-referentiality (instead of eliminating it). just think it over: why does self-referentiality play such a critical role in all of these topics (Russel's paradox, Godel's incompleteness theorems, Turing's halting problem, NP-completeness etc.)? "The similarity between Gödel's theorems and Turing machines is that both of them involve turning complex things into numbers." -- there are much more similarities. e.g. both form fundamental trade-offs Godel's trade-off is about the consistency-completeness duality, while Turing's trade-off is about the universality-decidability duality. but it is a general pattern in our cosmos that trade-offs can be exceeded or evaded. I still don't know how, but I am not 100% sure at all that these limits are insurmountable limits.

[@morryDad]

I was once asked by a VP at my company if we could write a program to automate root cause analysis. RCA is the root bug of a failing program. Basically, he was asking for one program to analyze another until us where it was broken. After controlling myself enough not to laugh at his face, I took it back to my desk and pondered it a bit. I didn’t realize that it was a halting problem, just wrapped in a different coloured bow. I sent him a nice little email, explaining the basics of the halting problem, and that seem to satiate his bizarre request.

[@ArneChristianRosenfeldt]

So how did you know that a program failed ( halted ) in the first place.

[@chrisalmighty]

I don't know whether it is a problem of the choice of illustration in this video but one thing that seems straight forward to me is that: Observation HaltChecker's Output is Reverser's Input Conclusion It is therefore not possible to give HaltChecker the Reverser program as its Input Program EXCEPT where there are two different Reversers in which case there is no Contradiction because the Reverser that Halts (passed as input to HaltChecker) isn't the same Reverser that goes on continuously (uses HaltChecker Output as its input).

[@xniyana9956]

I've finally grasped the halting problem. I've heard many explanations of it but never grasped it fully until this video. Well done!

[@njnjhjh8918]

What is HaltChecker's second input?

[@xniyana9956]

@@njnjhjh8918 It's the input that will be passed to the program that's being checked. If you're a programmer, ask ChatGPT to represent the proof as code. That's what I did and then the proof made complete sense to me.

[@xbzq]

This video has an incorrect explanation. You still don't fully grasp it. It is obvious it's wrong if you think about it for two seconds. Udiprod has a video that correctly explains it in case you want to _actually_ fully grasp it.

[@JSorngard]

Fun fact: if you have a faster than light engine you can solve the halting problem. Just follow these steps: 1. Place a computer with the program you want to check inside an FTL capable spaceship 2. Hook it up to the ship 3. If at this point a future version of your spaceship shows up out of an FTL jump, the program will eventually halt, if no spaceship shows up the program runs forever 4. Start the program on the original version of the computer 5. If at some point the program halts, the spaceship FTL jumps outside of the future light cone of its past self from step 2 6. The spaceship uses normal rockets to boost itself into a reference frame where step 2 just happened, and step 4 hasn't happened yet (this is possible since events outside an event's current light cone are not causally connected to it) 7. The spaceship FTL jumps to step 3, completing the algorithm

[@prototypeinheritance515]

basically the ftl drive acts like an oracle that can tell confirm if a program halts in constant time but only if the answer is positive

[@JSorngard]

@@prototypeinheritance515 you actually get the result in constant time if it is negative as well, since the absence of a spaceship in step 3 implies that the program runs forever. So if the program never halts you know it in step 3

[@lost4468yt]

This doesn't solve the problem? You're just running the algorithm itself. It also just doesn't even work if you have something where you're never sure if it halts.

[@JSorngard]

@lost4468yt You're using time travel to tell you past self whether the program halts. If no future spaceship arrives in step 3 you know it doesn't halt. If one does arrive then you know the program halts at some point in the future (otherwise the spaceship would never return). It's also only when you don't know whether the program halts that this algorithm is relevant. Otherwise, why run it?

[@lost4468yt]

@@JSorngard no it ran for the ship, and that info was brought back. And the algorithm could run for such a long time that the ship can never get to the end.

[@thinboxdictator6720]

13:56 count up [from 0] until -1 is reached will halt assuming it is unsigned integer. :)

[@Strakester]

Something I always like to bring up with the halting problem: The "count up from 1 until you reach -1" program will halt. The number will eventually overflow, in which case the program will crash, or it will wrap around to the negatives and eventually hit -1. You might say the general algorithm will never halt, but *any* implementation of this algorithm for *any* computer architecture that exists in the real world, or will ever exist in the real world, will halt, since all datatypes which store numbers have inherent limitations. Another example is "Divide a number in half until it reaches 0". In theory, if running on a perfect Turing machine, it never halts. But running on any computer architecture that does or will ever exist in the real world, it will eventually halt, as the number is rounded down to 0. Of course, you can resolve this discrepancy: you just have to include the entire processor architecture and runtime environment into your theoretical Turing machine algorithm, to correctly emulate its quirks and limitations! Then you can have your rigorous general mathematical algorithm that also provides a real-world answer, it's just... a lot more work than what you originally thought was three lines of pseudocode.

[@monad_tcp]

6:06 the discovery of the limit of computation was what founded the field ironically.

[@ttt3001]

Can someone help me; I don't get the last part. She says that the 6 questions (at 19:50) are general questions. But "does this program add 2 numbers" is sounds specific. Why can't we know if a program adds 2 numbers?

[@KohuGaly]

Because the program can be arbitrarily convoluted. If it's convoluted enough, it becomes impossible to tell if it even ends, let alone if it returns a specific output. No matter how smart your analysis of algorithms gets, it is always possible to construct counter-examples where your analysis will fail. That is the general point that the halting problem demonstrates.

[@RepChris]

Very good explanation. It covered a good chunk of the middle half of my lecture "theoretical compsci 2: formal languages, computability, and complexity"! Of course there were a lot of simplifications but adding "if given infinite memory" after every second sentence, introducing a lot of the definitions only there to allow for mathematical rigor, or having to explain what a "non-trivial semantic property" is for Rice are appropriate in a deep mathematical context they arent necessary to get the most important parts across.

[@micknamens8659]

15:50 The halt-checker needs as input the reverser code as well as the input for reverser. Otherwise the question whether it halts is meaningless.

[@sayushamatya8330]

It may sound dumb but it's just a question I had; why can't the reverser run forever at first and then halt next; as they seem to receive different inputs. The reverser initially receives a 'runs forever' instruction and then receives a 'halt' instruction. So, 'since the input is different, the output is also different' so where's the contradiction?

[@xbzq]

You're right and this video is wrong. It's obviously wrong and you should win a prize for being one of the very very few who saw it. Although I left a comment about it being wrong too, but it got deleted. Suppress the truth, I guess. Sad.

[@BallotBoxer]

I love how this channel makes big ideas so easy to understand.

[@jonanon8193]

@Up and Atom - the halting problem is a problem with the question allowing for only two results, yes or no. Make the possible results yes, no or unknown and then many many situations will yield yes or no and so it may not have been futile to write a program to do that.

[@imaginary8168]

16:02 I don't see how that's a contradiction. The 2 reversers are different form each other so they should be allowed to be in different states. What am I missing?

[@vandera]

YES YOU'VE DONE IT! Finally someone mentions Godel without making my brain hurt! Seriously, that was a very clear explanation of some very complicated concepts, loved it!

[@Merilix2]

Exactly as you sayd. The halteproblem isnt IT specific but more deeply related to math logic as described by Russell's paradox. Especially if a function get itself as an argument.

[@thomaslangbein297]

A sharp mind with a talent of using comprehensible language when explaining complex relationships. Great stuff! Thanks!

[@danielschegh9695]

I always find it more useful to reframe this topic. As typically presented, as is done here, it's put in terms of "general case" that can't be done, but "specific cases" can be. I find that is somewhat backwards. The paradoxical cases presented all have one thing in common: self-reference, aka, "feedback loops". The barber shaving himself, the set containing itself, the halting program analyzing the reversing program that depends on the halting program output, etc. This also isn't surprising. Anybody who uses a spreadsheet (like Excel) runs into this from time to time, where you accidentally try to create a formula in a cell that gathers information from other cells that includes the one you are writing the algorithm in. It's also conceptually the same as the time paradoxes like the grandfather paradox where you go back in time and kill your grandfather. This is a self-referential loop since you are an output of your grandfather. Another way of saying this is, universal computing and mathematical completeness work fine except when there is a self-referential feedback loop (aka, closed loop). It is a limited case where they can't work, and it is not surprising (or perhaps even a big deal) that they can't work in such cases. What it means in a practical sense is that you need to design to avoid such self-referencing closed loops. The grandfather paradox can be solved if it leads to a different "timeline" (as in "many worlds" interpretation of quantum mechanics). So, for example, if there can only be one timeline, there cannot be time travel into the past. If there can be multiple timelines, it is possible there can be time travel, but it coincided with entering a different "reality" branch. (This doesn't mean that such time travel is possible -- e.g., conservation of mass, matter, energy issues. It simply means the paradox creates a constraint on the solution.) Given this, I'm never sure what the value of this topic is toward practical use of math or computation. The examples used in the end simply show that practical solutions have a limitation boundary, but the cases beyond that boundary don't appear to serve a useful purpose, so it is arguably a trivial problem. Yes, it's true that a spreadsheet cannot have a cell with a calculation that adds all cells (including itself). What useful purpose would having such a spreadsheet that could do that do, or even mean? You can, however, have a spreadsheet where the cell adds all other cells, and that is useful. I don't see it as a problem per se, but a triviality with some required checking. It seems on par with checking that calculations do not divide by zero. Good to know it's a limiting factor and you need to check it.

[@lsauce45]

In 11:32 , You could have used Vsauce's *"Or Did He?"* . That'd more cool!

[@svz5990]

16:28 that haltchecker looks very scared

[@jakubjan44]

This is the best explanation of the Halting Problem I have evear heard.

[@IHaveaPinkBeard]

Always happy to see your new videos!! Up and Atom is rare Internet gold!

[@peterjensen8070]

This greatly disturbs me, and perpetuates the myth that the halting problem is a practical barrier. The halting problem is only undecidable on infinite memory machines. On finite machines the entire state space can be explored and the halting question can be answered definitively. ("Is the same state entered twice" has an unambiguous, decidable answer on a finite machine.) We see this exploration of state leveraged in formal verification all the time (to great success in real-world situations, i.e. will a program compute x). I suggest editing the practical applications of the halting problem discussion, as it's dead wrong when not dealing with infinite memory.

[@tkimaginestudio]

Exactly. Perpetuating the myth that the halting problem applies to any real computer is harmful. This does not mean that checking termination or other semantic properties is easy because in the case of termination the state space is hopelessly large for non-trivial examples but there is a difference between "intractable" and "impossible".

[@prototypeinheritance515]

You're right in theory, but it's not practical since the amount of possible states grows exponentially with the size of memory.