Marat That means Smith will contradict the Oracle no matter what, bacause Smith is designed for that specifically, as easy as that. And because the assumption is that the Oracle would be able to predict what Smith will do there's a contradiction, and therefore the assumption is wrong. Thus there's no Oracle which is able to predict Smith behavior. And that's all.
@@MrSpock-sm3dd I'm not the best person to explain it either, but I will try to give at least a context for it. Some decades ago, there was that question about if a computer/Turing Machine could solve any problem it was given. This was something pretty difficult to prove, because to prove that, it would be necessary to prove the possibility of the creation of a machine/program that would answer if the given input code - the code of other programs - would halt if executed (return an answer, even if it takes hundreds or thousands of years) or if it would loop forever and never stop computing. As that was something inpractical to prove, Alan Turing instead tried to propose why a machine that powerful couldn't exist, through contradiction (a solid way to prove or disprove things in mathematical language). Alan Turing assumed that this all-powerful machine really could exist, and all that he needed to do to disprove that "it's possible to create a machine/code that can detect if another machine/code will ever stop or if it will loop forever" was prove that using this hypothetical machine, he could use it as part of a bigger machine that would intentionally loop with certain inputs. Then, with said bigger machine, he would give two inputs, both of them being the bigger machine's own source code/descrition. If you're interested, the general way the process works is the following: - You can skip that part if you want- 1) The bigger machine receives the two inputs mentioned above; 2) The all-powerful machine (imagine it somewhat like a compiler) inside it receives the code of the bigger machine, and runs it with the own code of the bigger machine as its own input. Then, it's gonna return YES if it stops/returns something, and NO if it detects that it would loop forever; 3)Another machine was attached to the end of the all-powerful machine, and receives its output (YES/NO) as an input and does the following: if it receives YES, it enters in a loop; if it receives a NO, it stops. 4) If the input code of the bigger machine loops, then the bigger machine testing it will stop; if the input code stops/halts, the bigger machine will loop. That's a contradiction. Spoilers: Turing managed to prove it. He used the all-powerful machine to create a situation were it would contradict itself, so proving a machine like that couldn't exist. I didn't explain it in the best way possible, and I still get confused about some parts of that proof, but I hope it can help you and other people here to get the gist of this situation!
If you're confused by the first version of the proof, and have a little programming knowledge, here's a little more explanation with pseudocode: Assume we have "function oracle(a, i)" which can tell if a(i) loops or halts. We now define a new function: function smith (a): // a is a program if (oracle(a, a) says loop) return; else loop(); The question is, what does smith(smith) do, and what does the oracle say it does? If the oracle thinks that smith(smith) will loop, then smith will halt. Similarly, if smith(smith) loops, it's because the oracle thinks that smith halts when run on smith. Whether smith actually loops or halts when run on itself, the oracle gives the opposite answer, which means that it must give the wrong answer. Therefore, the oracle can't actually solve the halting problem.
I agree, the problem is oversimplified and thus fails to convey the concept in a meaningful way. It's like comparing an undefined var. Is N = N? Error N is undefined. The "Oracle" would need to know all possible states of a program after it's evaluated. So: ~~~Pseudo Code~~~ Oracle(smith(hampster)) = LOOP Oracle(smith(helloworld)) = RETURN Oracle(smith(smith)) = NULL or "Undefined" ~~~Pseudo Code~~~ smith(smith) isn't valid because the second smith was called without a parameter to evaluate it. it would need to be called smith(smith(hampster) ) ) in which case hampster which would return LOOP to the inner smith function in which case the Outer smith function to return RETURN You need to know what smith(NULL) would return in order to return smith(smith) in the first place. It's like trying to guess the number someone is thinking who just lies and changes the number in their head. It's nonsense to think a program COULD predict the number they are thinking, much less when they lie about it to always ensure it's wrong. The computer can't win! ;) To me this problem seems intentionally obtuse. You almost have to dumb yourself down to understand it. I understand what it's trying to say, a program can't predict everything and every possible outcome. Well... maybe a quantum computer can since it can have much deeper logic in it's most fundamental level. In a Quantum computer, agent smith is both, looping and returning at the same time. His states wouldn't be mutually exclusive. It's setting up a paradoxical situation intentionally. That's where people are thrown off by the "Deeper Meaning" of this and I'm sure others intuitively understand what I'm saying on some base level they get the feeling that this is wrong, and they are right with that gut feeling. @LarcenIII on Twitter
I find the argument somewhat confusing. There exist an oracle (function) for the halting problem since the problem is mathematically is completely well-defined. What the argument shows is that this oracle (function) cannot be programmed i.e. is non-computable.
I shall explain in the lowest level possible even though I just watched this video 6 mins ago...Let’s use an analogy. Let’s assume you have a set of containers(programs ) and then you have a set of fruits(another bunch of programs). Now when you put a fruit inside one of the containers, you get two outcomes. They spoiled(halt) or remain fresh(loop). Now let’s make another program, the main dish program. It’s job is to show the opposite of what’s happening inside one of the containers. If the fruit is spoiling inside the containers then the “main dish program” will show that its fresh and vice versa. To summarize you have three programs; -The main dish program -The containers program -The fruits program Each fruit program goes inside their respected container programs and the main dish program checks whether each fruit is spoiling or still fresh and tells you the opposite. However, it’s impossible for the main dish to do such a thing because of how much computation is required to run an infinite iteration of each programs on top of one another, looping and not looping, since a loop requires a lot of processing memories or something. On the other hand, you can write a program that can do such a thing for some finite amount meaning you can’t make it loop forever. The difference is really trying to make a program that loops infinite times for three different programs which is yeah...currently impossible, maybe with quantum computers If there’s anyone out there who’s more knowledgeable about this topic then please correct me since I just translated what I watched a few minutes ago to something that I can understand.
It can. Halting problem can be solved for an unknown set of programs except one instance laid out in the theory. So we can conclude that Halting problem cannot be solved for all possible programs, but maybe a subset of them.
It took me 30 minutes to figure it out! Thanks for the tutorial!! I think the Cantor's diagonalization makes more sense and after understanding it, the contradiction (solution 1) makes more sense.
You're being a little bit disingenuous about the nature of the Halting problem. It's impossible to solve it in the general case. It's not impossible to solve it for certain classes of programs. From a practical point of view most programs we write are easily analyzed by our tools, so it's common for IDEs and compilers to point out where programs have endless loops and unreachable code.
but thats the beauty of it; you can write a decent algorithm to find infinite loops within code, but can never write an algorithm that will find ALL infinite loops within any algorithm! makes us keep writing algorithms :P
This simple proof of the impossibility of the halting problem glosses over the fact that the halting problem is only undecidable for programs with infinite storage. If a program has finite storage one could in principle make a list of all the states it passes through (including the state of all memory locations). If it revisits a state without halting output "loops forever", otherwise when it eventually halts after visiting all the states it can, output "halts". This obviously doesn't work if the program has infinite storage. It's interesting to think about why the "Mr. Smith" argument doesn't work for finite state machines.
While there is a philosophical solution, a practical one exists. You halt all programs after a certain amount of time has passed. You may prematurely halt a program that is still running but if it is more desirable to free up resources and go to something else, then a maximum time makes sense.
I always think of looping as returning to a previous state. And you _can_ check to see if a program does that. The programs that do not halt and cannot be determined not to halt consume ever more memory and enter into ever more complex computations.
its not that simple. calculating more and more digits from the decimal expansion from pi is easy (standard cpu benchmark). imagine i gave you the assignment to write an algorithm that answers the question: if i give you an integer n, does pi have exact those digits in the same order at some point in his decimal expansion? sure, for some inputs the question is easy, like if i give you the number 31415. but if i give you an arbitrary number, 4589789023714878572893417897460900910293123 your program has to calculate pi till it matches the digits. so will it stop or not? you cant decide if you didnt wait long enough and there is an answer (yes or no) or if it will loop forever. maybe pi is so arbitrary that every pattern of digits eventually emerges. maybe this is not the case. if we knew more about pi, this problem would be decidable and the algorithm to decide it would be really easy. output yes or output no, there are no other cases.
so youre trying to tell me, i should start my debugger, let my program run and look for a while. as soon i get bored i quit and simply say: alright, this program doesnt seem to halt. i could nobody convince that the program i wrote wont halt, because i say: well i got bored and stopped waiting, trust me, that program is looping infinite and will never stop. if you need more complex calculations, then you have to do them. because the program might halt eventually and this is what all this is about. simply saying "i cant see that any progress is made, its just doing more and more calculations, i just assume it will never terminate" isnt the way of solving the halting problem. by that logic, someone who is extremely impatient, will never write any code that will terminate. if he immediatly gets bored, he could stop the debugger before the hello world program could print the output to the screen. what i want to tell you is, there are programs that calculate more and more complex computations and consume more and more memory and will halt (maybe it takes 3 years of computation to finally reach the matching digits in the decimal expansion of pi) and there are programs that do the same but wont halt (maybe the digits will never emerge). the question is, is there a way to tell them apart? and not for a specific program, the question is, is there a way to check if any arbitrary program terminates with a given input. and as proven in this (well done) video, there isnt.
I'm not trying to tell you that you should do anything. I am stating what my concept of a "loop" is. And it is a detectable phenomenon. These undecidable programs, while they do not terminate, also do not fall into a pattern, and so do not fit my idea of a loop.
oh boy i didnt understand what you wrote in the first place and why :D english isnt my mothertongue... i thought you wrote your comment to point out that its not hard to decide if some code will halt, since you can check for reaching a previous state again... sorry for the confusion on my side!
Have any comments on intuitionistic logic/constructionist math? They reject the law of excluded middle, and so double negations don't equate to a truth. In this way they also reject existence proofs by contradiction. So here's my question, if we prove something that is not constructable can not be false, then is it true? It seems to me that we get stuck into some kind of limbo where we have proven that it can't be false. So that's super clear. But if it can't be false, and it also can not be constructed, then does it exist? Or is it something like, "well it can't be false, but it also can't be true, so it just doesn't exist." But, if we prove that it can't be false, does this also mean that if it isn't constructable that it exists? And, if we prove that it can not be false, doesn't this also mean that it can't not exist, since we've proven that it can not not exist? (or does this count as relying on a double negation in classical logic?) It just seems odd that constructivists think we can prove something can't not exist, and turn around and say, "welp, I can't construct it, so I guess even though I proved it can't not exist, it doesn't exist after all." It's like they go around contradicting themselves. Or in a different sense, they don't trust what they can't empirically perceive. Metaphysically it would seem that intiutionists/constructivists would be considered radical empiricists, but the ironic thing is that many of these mathematical objects that they are trying to construct obviously don't empirically exist in the external world we interact with using our perception. So it's like they're only comfortable if they can construct something that only exists in some platonic mathematical universe disconnected from true empirical perception anyway, so what does it matter whether or not you can actually construct some idealized mathematical object if you are already 100% certain it actually doesn't exist in perceptible reality? I mean, c'mon that just seems silly. One example of this is perfect geometries and irrational numbers. Perfect shapes do not exist in the perceptible reality we live in, and certainly irrational real numbers also do not exist. Infinity is up for debate (not sure whether the physical scientific universe is finite or not, different from the mathematical universe Platonist's think of when speaking about infinite sets and what not). If you're already considering only some idealized platonic universe of rational thought, if you prove it can't not exist (using logical deduction absent of any empirical observation) why not just assume the default is then, rationaly speaking (again, void of any empirical perception feedback at all), that if it can't not be false, then that means it can not be false. Period. Concluding that it must not exist because it can't be constructed seems to me to be the same as concluding that it can't exist, even though we would have proven exactly that the object couldn't not exist with a proof of a contradiction. So I don't think constructivists have any real arguments. Now, the one exception I can think of is when we are dealing with mathematical objects that *actually do exist in our scientific empirical perceptible reality/universe/multiverse.* For something like number theory, say, where something is proven by contradiction but also can't be constructed or observed physically via perception, well then that's a slightly more convincing argument, because when an object actually exists in our perceptible reality then all of modern science suddenly supports more strongly the constructivist argument. In some ways it would seem that we have to parse/separate between the empirical mathematics and the non-empirical mathematics. And then depending on whether you are a rationalist/realist or an empiricist, you could be allowed to create theoretical models of our reality using mathematics that isn't constructible or that doesn't exist in our objective reality. This comes into play especially when we think about theoretical physics. The question becomes, are we *allowed* to use mathematics that has no bearing on physical reality to explain perceptible physical reality, ie, the areas of objective reality, if they exist, that can not be empirically perceived with our 5 (or more) senses. The question is, *are we allowed* to use idealized, and even more strongly, non-constructible, mathematics to describe the areas of reality that aren't empirically sensible, and for which experimental science *can not* apply. This all reminds me of Zeno's Arrow Paradox, and how our rational thinking, even in 100% logical, often contradicts our empirical science. And guess what, arguably, all of mathematics, especially in ancient civilizations, is founded on our *empirical senses,* especially *vision and touch.* As just one example, the entire concept of "a number" arose out of vision, ie, looking at a thing, and finding visual boundaries in it to "count it" discretely. This is where numbers come from, this is where mathematics comes from. And any abstraction built on this empirical perception is unavoidably tainted by our perceptual information, and in this way if we allow ourselves to use mathematics to describe the parts of physical reality, if they exist, that we can't perceive, then we are making *the large assumption that the areas of reality we can't currently perceive are similar to our own realities.* Anyway, my personal opinion on all of these things, ranging from intuitionistic logic, to metaphysics to theoretical physics remains unsure. On one hand it seems wrong to say that unperceptible reality might not be similar to the reality we can perceive, but on the other hand, our rational logic often contradicts our empirical senses, (Zeno's Arrow Paradox), and all throughout history, every time it was rational logic vs empirical science, the empirical science has always been the correct argument, over the rational logical deduction. You know, the only place to go from here is to speak about death, and what the sources of perception are, and whether or not you believe in the soul, and an independent mind, or a fully biological multi-cellular argument in which a person, or any living being is nothing more than a temporary sum of its parts, only to be disassembled and reassembled again through time. I guess neither of these two views on death are particularly terrible. If we assume we are all part of the sum of our parts, and the conservation of matter applies, then we never become less or more, and our cells have lived in another being before they came back to build us, and they will continue to be reformulated to create new life again in the future after we die, and this constant separation and reformation is actually quite a beautiful and comforting idea. I believe this is the origin of the notions of eastern religious spirituality, specifically Indian origins of Hinduism and Brahman. And the concept of the "mind-body duality" is clearly a western dichotomy put forth by Descartes. Many engineers becomes obsessed with their own consciousness at some point and "turn" into Cartesian Dualists, at least I like to think this. I like to think they flail about shorting cognitive circuits and spinning cognitive tires trying to make use of heavily computational and applied mathematics and physics (like calculus and classical physics + recently a shallow understanding of particle physics, because that's all the engineering curriculum teaches... lol) to try and tackle the issue of their perception and consciousness, and ultimately, their human experience. But I think these people are doomed to failure because they're not familiar with the philosophical ideas at hand, nor are they equipped with the true theoretical understanding of mathematics to actually make headway in this department. Personally I'm much more willing to accept Brahman as a metaphysical explanation of consciousness than a Cartesian Dualism theory. Oh well, I hope you enjoyed reading a little of that. I do think it's all relevant to the question of whether or not constructivist mathematics is something to take seriously, because ultimately it is a metaphysical, or at least epistemological, type of argument against classical logic and classical mathematics (which uses classical logic to be "rigorous"). Thanks.
This may sound stupid, but why is Mr. Smith designed to do the opposite? Why did we have to translate the diagonal loops and halts to their opposite? If we're finding proof by contradiction, aren't we already assuming that the oracle exists? Why do we have to bring in Mr. Smith again for another contradiction? i.e. why can't we just leave the diagonal untranslated?
Well, according to me this proves that there are programs for which the Oracle will give the wrong answer. That means the initial assumption that oracle knows all is wrong. I hope that helps :)
We assume we've found an Oracle that knows how to solve this problem (it knows the entire matrix as we've constructed, e.g. can determine whether any program will halt given any input). The point is, we can always create a Mr. Smith who does not exist in the matrix*, and therefore does something the Oracle can't know, contradicting our assumption the oracle knows all. * No pun intended, I'm literally referring to the dimensional grid we've constructed...
But didn't you just prove that the list of all programs is uncountable? It seems to me like saying you can't put real numbers on a grid, therefore they don't exist.
Sort of. The list of all imaginary programs is uncountable, but the list of all computable programs is countable (because they have an arbitrary, but finite length). This means that Mr. Smith is uncomputable, so you would never be able to actually write the computer program that matches his behavior in terms of looping and halting, for all inputs. en.wikipedia.org/wiki/Computable_function#Uncomputable_functions_and_unsolvable_problems EDIT: Let me clarify how the diagonalization works. Because we know that computable programs are countably infinite, we can make the grid seen in the video. We then create a sequence by taking each element from the diagonal and flipping it. This new sequence defines the behavior of something, but it isn't necessarily a computable program. In fact, it cannot be a computable program because it cannot appear on the list. However, if we could solve the halting problem, then we could easily write the program with the same behavior.
why does mr. smith exist in the first place? what actually is his role if the oracle already determinates whether the program loops or not? is this just how the problem is defined? if it is and we put this into a tautology, we get 2 conditional statements: 1. If oracle says halts, then smith loops 2. If oracle says loops, then smith halts now let's say for 2. p=If oracle says loops and q=smith halts but this wouldn't make any sense because the condition p->q is false when the hypothesis(p) is true and the conclusion(q) false and at the beginning we said that the oracle is always right, meaning the oracle is always true. Also if we use p and q for the 1. we'd get p'->q' with the same outcome.
This is simply Superb!!!!!!The best one I watched on Halting Problems......The animations made it even more clearer.....Keep it up...Thanks Cory...u rock!!!
It seems that both contradictions depend on a program that has access to the output of the Oracle. But that seems odd. An Oracle should be independent of the programs that it analyses. So, the Halting problem for *all* programs might be unsolvable. But this does not hold if you limit the domain to programs that do not have access to the output of the Oracle (i.e., the Decider program).
Agreed. The problem only seems to be unsolvable in a trivial, academic, useless program, so who cares? Is there some larger point the creator is driving at? He didn't explain.
At 5:08: _"Since the list is a complete list of all computer programs, that means, that we can never write a program, that matches the new row, that we generated on all inputs..."_ That's not correct, because _the list is_ *supposed to be* _a complete list of all programs_ *and yet* _we can_ -never- _write a program, that matches the new row, that we generated,_ *not appearing on our supposedly complete list of all programs.* Hence, our list was and is incomplete and is incompletable and therefore, the "oracle" - a program capable of deciding about any halt problem - is not possible. The conclusion is correct. But the deduction to that conclusion is not quite correct.
No. An algorithm is a finite object - under any of the equivalent definitions (e.g. Turing machines). It follows: there are countably many algorithms - countably many Turing machines. (Equivalently: there exists an infinite sequence containing all Turing machines.)
@@MikeRosoftJH Sure. An algorithm is a finite object. But a program doesn't need to be such a finite object as presented that infinite way in this video. But that doesn't mean, that it is completable as shown and demonstrated at 5:08, even if we make the assumption of a Turing machine with an infinite amount of memory.
So, we have an algorithm A that branches to a loop or a halt, according to an input. This input is the output of another algorithm B, which predicts whether a _third_ algorithm C will branch to a loop or a halt. A will do the opposite of what B predicts of C. But it can't do that if C is a duplicate of A. EDIT: Except...isn't this just B correctly predicting the output of C, and A inverting it? B can't predict the output of A, but that's not what it's trying to do. It's only been fed C.
Does this assume an infinite number of possible inputs? If so, why do we need the diagonal example since the search space would be infinite? Even if not, how could we even attempt to solve the problem in a way that isn't just running the code?
This is a very accessible explanation of beginning logic for people who enjoy learning with pop-culture imagery. I positive it will help some students immensely. I especially appreciated how you showed the two proofs to be identical, after a fashion. Perhaps as a follow-up video, you might give an explanation why "the halting problem ... was instrumental in forming the basis of the modern computer," as stated in your precise. I mean, I think it is quite interesting and not at all obvious how an undecidable proposition such as the halting problem would help form the basis of the modern computer.
Questions: It's obvious that you can just hold numbers/booleans in an array to see if they repeat and kick out of a loop if they do.. but that wouldn't work for numbers increasing dramatically. say: integer x=1 while x>0 x++ Would go on indefinitely, or until it hits an integer cap 2,147,483,647 and fail. Did anyone ever design a work around for this? You could probably set a lower maximum x bound in your while loop if you aren't expecting it to repeat for too long.. but is there a way for a program to recognize that incrementing by 1 won't get you any closer to being under 0? Guess not because you could always have a line in the code that says 'if x=100000000: x=0' a while loop can't really see what it has in it so it would be going until the integer overflow..
There's a few points to make here: 1) The fact that the oracle cannot exist is precisely the point. If it did, we would be able to create programs which disprove its correctness (we also have plenty of programs that we can write, but we have no idea if they actually halt or loop). 2) There are still other uncomputable problems (e.g. the busy beaver function en.wikipedia.org/wiki/Busy_beaver). 3) Interestingly, how would you know if one program is embedded in another program? To simplify, how would you know if two programs are even the same at all? The code might be different, but if the output of both programs match exactly, we would consider them the same, right? However, verifying if two programs have the same output is another uncomputable problem (for a similar reason to why the halting problem is uncomputable).
If the video is esoteric, we humans have to basically tell the machine what is an infinite loop and what isn't. So to piggyback off of the video's explanation a bit, compilers themselves have no algorithm that can understand the behavior of while(true); and tell that it's an infinite loop. There is no algorithm that can tell the difference between a real infinite loop and a program that just takes a really long time to run. We have to just specifically tell it "if you read true within a while condition then halt". For programmers out there, it's the difference between a anomaly detection method and a signature-based detection method. Anomaly detection is great, but can come with a lot of false-positives and won't likely catch all examples of what you're looking for. Signature-based (defined programmed behavior) is not as ideal but will for sure catch the case you're looking for and is often the go-to solution for this type of problem. We often make compilers signature-based when detecting errors. These issues in computation are the real reason that A.I. isn't very well progressed in modern times. It appears as if A.I. is very wise now and many media outlets over pronounce the progress to comedic effect. But the honest truth is that A.I. is extremely dependent on explicit definition currently. To those who watch A.I. beat really old NES games, the amount of failures VASTLY exceed a normal human's amount of failures, and that's just of simpler games. More modern games which are designed to be more understandable and don't resort to cheap shots or surprises to kill players are nearly impossible for modern A.I. to complete. Ironic, as hardcore gamers say games are too easy these days, but computers would have a different response, haha.
There can only be infinite length programs in theory, given that a program has a finite length, and only 0-s and 1-s can be in it, there can be only finite variation's of programs, so Cantor's diagonalization doesn't work on them, so if we limit the programs in length (software and hardware limitations exists) can there be a program that gives the answer?
x = Input: while true: print("Loop") if x = 1: print("Halt") break What about this program? I can fairly easly make a very precise statement on when the program halts or loops. If the Input == 1, then it halts. For every other x it loops. So clearly I did not understand the Entscheidungsproblem.
We can make programs that determine whether a program halts or loops in SOME cases. The video demonstrates we can't make one determining it for ALL cases.
So would how about we add a third output of "incomputable" which triggers under the circumstance that the oracle finds that it's own source code in the input code with the same input as it's own. Would this make it possible for the problem to always be solvable (as in being always correct about halting or not if it is possible and always returning unsolvable if solving it would create a paradox)?
I'm afraid I don't understand the difference between a program and an input. Could you demonstrate it using an example? Why would proofs either loop or halt? Axioms are always true, so they would halt either way? Looping would mean it's not provable right? Really though I'm so confused. I keep watching video's about the Halting problem/Gödel's Incompleteness Theorem but I can't seem to grasp it.
Sure! In this context, it's best not to think of programs and inputs as different at all. Programs are just text files (which are really just numbers), and there's nothing strange about feeding a text file or a number into a program. In fact, your computer's OS is a computer program which takes other programs and runs them (like your internet browser). You can also think of a game console, which uses a program (the game system's OS) to execute another program (the game). Here, the game is an input to the game console. A really simple program we can write that takes in another program might be one that returns the length of a program. All we do is look at the program, count up all the characters, and return the amount. We know we can do some simple static analysis like this pretty easily, but now we move onto the actual behavior of a given program. We can write a program that answers the question, "Does a given program finish within 10 minutes?" All you do is take in a program, let it run for 10 minutes, and check if it's done or not. Now the question becomes, "Can you tell if a given program will ever stop?" This question seems like an extension of the previous one, but unfortunately it crosses the line between a solvable and unsolvable problem.
This is a good question, because it doesn't really look like this very math-y explanation maps to real programs. For the number of arguments, we can treat it as if all the arguments are "bundled". Ex. If the program accepts 2 number arguments, let's just think of a version of that program that accepts a string like "5 12" and parses that for the two numbers it wants. If the program doesn't need any arguments, it just ignores whatever you give it. This can be generalized to any number of arguments. And it can work for arguments of any type as well, since any value can be serialized to a string (JSON, some byte stream, or anything else). Let's also assume that these programs validate their inputs and halt (maybe by throwing an error) if the input is invalid. Ex. while a program is doing the aforementioned input parsing, if it seems that the arguments are invalid it just throws an error. Programs aren't really altered by either of these assumptions. If the input is valid and parses and all that, then the program is still doing all the same logic. If the input is invalid, it'll halt with an error. And as for the rest of the proof, it doesn't really matter whether a program is a valid input to itself. What matters is that there is no oracle that can determine for ALL programs whether the program will halt when given itself as an input. In practice, for most programs it'll be pretty obvious. If you look at "function sum(a, b) { return a+b }", clearly it won't accept its own source code as an argument and it will halt with an error. (Really, if this is JavaScript it would probably work with string concatenation, but again let's assume we have a version that validates inputs. Either way, it'll halt). But since there are an infinite number of possible programs, many will be much more complex and run on all sorts of different kinds of inputs. And there will always be some program that trips up the oracle. There cannot exist an oracle that is 100% accurate, which is all that the proof is saying. But it is certainly possible to have some "crappy oracles" that are less accurate.
The point isn't whether or not this actually applies to the sort of programs we tend to write. The point is that this proves that a program that decides whether every possible program and input loops or halts cannot possibly exist because the program you're proposing is self-refuting. Obviously we can analyze certain classes of programs, but we are unable to analyze *all* classes of programs.
I want Robinsons Place Dumaguete to be constructed quickly and not be aborted and delayed and the heavy equipments are going to be used at the Calindagan site while the other one will be in Pampanga.
Thank you! I've watched a number of other videos on the halting problem that didn't get to the heart of the problem: Proof by Contradiction, which you've nicely illustrated: . This logical proof also helped me see the connection to Godel more clearly.
the problem with contradiction is jumping too many steps. if A then B. if not B then not A. you forget there might be an A1/2. so if not B then not A1/2 but still maybe A.
If anyone's confused it might be because this proof comes with a big pre-requisite of infinite memory that's not mentioned. And that doesn't actually exist in the real world. Halting problem is solvable with finite memory because there are not infinite states. In fact it's not even that hard if you are simulating. You simply collect all conditions that lead to loops then determine the possible states of the conditions. Once you find that every condition of the enclosed loop is itself a closed loop, you have an infinite loop. You only can't do this if the states are infinite. Infinite math is pretty bogus TBH. You always get crazy theorem like this. But that being said. The real problem that makes determining if an infinite loop is subjectively "bad" or "good" requires outside information. If there are any side-effects in the loop, then those side-effects may actually be the intention of the program running as expected. The beginning of the video where the spinning wheel was used, is a bit misleading, because a spinning wheel is not a reflection of the theoretical halting problem, but of the event system being blocked not allowing any user-input past some hard limit of time. e.g. let a = 1 while(a != 0) { a = random() } We can simulate the above program and know the conditions of the loop are a, and any of the possible ways that a changes, which is only random(). Since one of those possible outputs is 0, and a 0 could still theoretically happen, we would not detect it as an infinite loop, even if it could run for a very long time depending on the bounds of random(). This is absolutely possible because random() is not infinite on any real world machine. Only by saying that the bounds of random() are infinite, do you conclude that the probability of random() being 0 are 0. Again, infinite math is kinda bogus. At the end of the day, all this proof is really showing is: "if you had a theoretical program with incalculable calculations then calculating if it calculates the incalculable is incalculable" and my answer to that is "duh". Of course this isn't useful. What an actual person would want is some way to detect if a program stops making human-useful side-effects after a human-reasonable amount of time. Which is what operating systems currently check for.
So, in order to "know everything about the universe" (i.e. be "omniscient"), you'd have to actually 'calculate' -- i.e. "run" -- the universe? Or, stated another way, creating a perfect and complete copy (i.e. "model"/"map") of the universe [which would, of course, be part of the universe by definition] is impossible? *Anthropos Cartographer* (the next cognitive and evolutionary leap for the species whose antecedent referred to itself as "Homo Sapiens") It's a map, people. Constructing "[conceptual/internal neurological/sensory experiential simulator ("imagination") generated] models", a.k.a. "[onboard, sensory environment] maps" of our sensory environment --- as well as encoding and transmitting 'facsimiles' (i.e. decoded 'maps', in turn) of them to (a.k.a. "sharing them with") the 'onboard, sensory environment mapping computers' (a.k.a. "brains") of our fellow species members by means of our 'self-indicating/indexing/addressing sensory-information indicating/indexing/addressing' and encoding tool, "human language" [in conjunction with our other cooperatively developed media technologies] --- is what we _do_ ! (Apologies for the 'essay-in-a-sentence'.) Note that the human organism's onboard, sensory-environment mapping computer uses the current state of its onboard map(s) as both 'map' of 'as is', and as its 'blueprint' for its 'to be' states (see "Turing machine") -- i.e. as its 'program(s)' to 'instruct' its subsequent sensory environment mapping/'interacting' [conditional decision] actions. For example, "the scientific method" has proven to be our most powerful and effective (sensory and 'enhanced'-sensory) environment mapping technology/technique/algorithm to date. We (human "civilization") are [i.e. hopefully will soon be] an intelligent, self-aware, self-improving, information processing circuit -- a.k.a. a [human societal] network. Take special note of the word "we" in that statement [because, in addition to the self-evident 'network' definitional reasons, "we" is "quantized" - I'll explain that later, or you can deduce the physical and logical significance for yourself, based on the nature of "the speed of light".). If we keep this in mind, and operate accordingly, there is no limit to what we can do. Oh, and our new 'Constitutional Bill of Fundamental Human Rights', as the official minimal code of ethics and "law of the land" for the individual citizen, and for all organizations thereof (civic, private corporate, and government), is [i.e. hopefully will soon be] our foundational network protocol and operating system (NOS). So, Thank You for this. (and in the meantime, 'Careful with those maps, Eugene.') P.S. "Information": A specific pattern of momentum 'pulses' (waves) as input to a particulate mass object (PMO) I/O device, which 'reroutes' that input (maps it to) a correspondingly specific output pattern and trajectory of momentum "pushes", and/or stores [a portion of] it as a reconfiguration of its internal circuitry/structure/'point-radial momentum' ("mass")'. See also "What is a Worldview" (ua-cam.com/video/AVAmY1HvExI/v-deo.html)
Actually, the Oracle would go on a loop. If Mr. Smith (M) gave himself to the Oracle (O), the Oracle would have to put Mr. Smith into himself, which he already did, so the Oracle would have to say neither.
If your list of 'all' programs doesn't include the agent Smith program is really a list of all programs? Wouldn't claiming to have a complete and simultaneously infinite list be claiming to be able to solve the halting problem assigning your list the definite state of knowably does not halt?
First, were there a program (A) called Halt which could determine whether a program (B) would halt or continue, it would by that very definition (as per the video) in actuality only be required of program (A) to determine whether a program (B) output fed to it would halt. It would not have to analyze if program (B) would continue on for that is the only possibility left if program (A) determined that the program (B) would NOT halt or whether it was unable to determine that program (B) would halt. If one were to deny this, he would by that be also denying that the program (A) had any ability to ever determine if program (B) would halt and of course, the instruction was to assume that it could. At that, I think all is settled with regard to the initial goal defined. But in anticipation that this would not be sufficient for some….the goal as stated was to determine whether a program (B) would halt or continue as per program (A) which would output that answer. Then for some reason we are instructed that a program (C) would be required to take the output of program (A) as to whether program (B) would halt or not and do the opposite. Why? The goal was defined and achieve before program (C’s) introduction. This makes no sense. So program (B) performs its function, is judged by program (A) as to whether it will halt or continue on and program (C), as per the video is required to look at the output of program (A) and do the opposite. So the input of program (C) is the output of program (A) as per the function of program (B). Claiming then that the program (C) would be input to itself and by that, create a contradiction for if it halted, it would continue on and if it continued on, it would halt, is the same fraud promoted in the liar paradox by Quine. In the liar paradox, “this statement is false”, self-reference is employed to generate the paradoxical function, i.e., if “this statement is false” is true that it is false, then it is false and thus NOT true, but then it is in fact false by that true, etc., thus the paradox. The liar paradox is complete sophistry and defies logic. The term “statement” in “this statement is false” is a set definition as well as a subject noun. But it is empty, i.e., it has no members. There is no reference object which might be judged as true or false. The adjective false (within the statement “this statement is false” is the means of its judgment), connected to the term “statement” by the linking verb “is”, is denied its function because the set definition/subject noun is empty. Here the term “statement” is not a noun like rabbit whose definition is self-contained so to speak. Additionally, this piffle breaks the law of non-contradiction as well as other logical rules. So, the halting problem is employing kind of self-referencing, i.e., if program (C) COULD run itself, which itself makes no sense, then the same kind of contradiction would be generated, i.e., that if it halted, it didn’t and if it didn’t halt, it did. How is this functional, logical or meaningful? Turing did not discover a contradiction in mathematics, he introduced one from outside, created one by the manipulation of the logic of the problem originally defined. Can ANYONE show me if I am wrong and how? Tell me exactly where, because I think this is a fraud and it makes me suspect Goedell’s incompleteness theorem as well. .
firstly, there’s nothing wrong with a program being able to handle itself. just look at recursion or virtual machines we create a program C, which runs A and then does the opposite of what it outputs. since we assumed that A already exists, there’s nothing wrong with being able to use it in another program. not exactly sure where your confusion of that is. the fact that putting C inside C creates a liar paradox is literally part of the proof. it creates a paradox where A is always wrong, thus it cannot exist
@@Aagames_ Thank you very much for responding. I greatly enjoy these discussions. So, I don’t think I am at all confused. My study of this topic was not what Turing was claiming and whether or not he was right or wrong about the matter but rather the whether the analogies by others as to what he was claiming made any sense, and they don’t. So I think I can say that they do NOT proves his point but rather confuse it. What you have missed is….(several points, a kind of compilation of several videos meant to validate what Turing claimed) 1. We are instructed to assume that there can be a program which can analyze another program and determine whether it would halt. This is necessary for the analogy. 2. If we proceed from this, we know that by definition, the program (call it program A) does not have to determine whether a program it is analyzing will continue on for there are only two possibilities and if it is unable to determine that it will halt, by definition it will continue on. 3. The point of the reverser program is to introduce a contradiction into the scheme, which we were promised Turing did NOT do. What is the point of the reverser program if program A has already determined whether a program it is analyzing would halt or continue on? The reversal of the finding of program A is not a function of program A. To then indict program A for being unable to perform the task for which it was written after a second program was employed specifically to corrupt its findings is illogical. 4. In this scheme program A is the only one that “runs”. The program it is analyzing does not, i.e., it is only that its structure is analyzed to determine what it would do when it ran. Therefore, if the reverser program is analyzed by program A, it (the reverser program) would also not be running (only its structure analyzed). 5. The reverser program is “available” to accommodate an analysis (which again, would not come) of either halt or continue by means of its structure. Therefore, if program A analyzes the reverser program, there would be no output of program A, which is the input of the reverser program, by which the reverser program would either incline to halt or continue on in opposition. 6. Even if we ignore that the reverser program would not be running, it would only be able to perform that function “after the fact” of the analysis and finding of program A (for it requires an output from program A as its input). It would be a step 2 in a sequence of two steps and therefore could only be considered logically disconnected, a link in a chain as it were, with program A. The effect of the reverser program does not then indict program A. 7. Given that there can be no output of program A that would act as input to the reverser program that would demonstrate its inclination toward halt or continue on, were the system of program A analyzing the reverser program fed to itself as a program to be analyzed, this system into which it was fed could also not then reverse the finding of the former first, for there would be none and second, for the reverser program of the latter would also not be running. I could go on for several pages but I am trying to be succinct. These videos trying to explain Turings scheme do not make any sense and I have seen nothing that is logical that could be said to validate what Turing purportedly claimed. What do you think?
@@jamestagge3429 ok i now understand that you're not directly opposing the proof itself, but rather the way videos explain it (tho im still not exactly sure in what way) nothing wrong with 1 and 2 "The point of the reverser program is to introduce a contradiction into the scheme, which we were promised Turing did NOT do". im not sure what you mean by what Turing promised. "What is the point of the reverser program if program A has already determined whether a program it is analyzing would halt or continue on?" the halting problem is a proof by contradiction, where we assume program A exists, then show that we can create a machine using A that causes A to always be wrong, therefore A cannot exist. it doesn't matter how we create the paradox (as long as we use logical steps), we just need at least 1 example of a situation where A is wrong. i agree with you on 4 "Therefore, if program A analyzes the reverser program, there would be no output of program A" we define program A at the start to ALWAYS give a correct boolean output, so "no output" isn't an option. when program A is given the reverser program, we don't know what it'll do with it, we just know that A will either output 'halts' or 'loops forever', since that's how we defined A. "The effect of the reverser program does not then indict program A." program A is inside the reverser program, and the reverser program does the opposite of A's output. if A thinks the reverser will halt, it will loop forever, if A thinks it'll loop forever, it'll halt. the programs being disconnected doesn't change the fact that A is always wrong in this case. it took me a while to actually understand this problem too, so i understand your position. personally the video made by "udiprod" was the one that got me to actually understand why the proof works.
@@Aagames_ Again, thanks for responding...............So, the problem is that Turing claimed or perhaps others did, that he essentially invented the computer and authored these schemes to show how a material operation could be shown to be a contradiction. This is pure sophistry. IF program A (the halting program) were defined as such and had to function (as is claimed, to analyze another program) then its operation, its ability to function and analyze what another program would do IF that other program were to run, it could only analyze that other program as per its structure or architecture as to whether it would output halt or continue on given a particular input. However, in all of these schemes, that is glaringly contradicted. That the reverser program was defined as it was, means that it could not be analyzed by program A. By definition, the reverser program requires an input which can only be the output of program A. Yet the reverser program is not inclined by means of its structure alone to either halt or continue on absent an output from program A to be its input. So the entire scenario fails and proves absolutely nothing but the intended deception the presented scheme. If the reverser program requires an output from program A as an input, and the reverser program cannot run for there is no output of program A to be its input so that it has something for which to do the opposite, there is no means for program A to find either halt or continue on. Also, consider, if you ignore that above for the sake of my following point, the reverser program can only act “after the fact” of the output of program A, again, that output providing the reverser program’s input. This points to the fact that program A did its job and was not wrong, but that its output was corrupted by the addition of a program which reversed the output of its analysis. This would be akin to the arithmetic of adding 2 + 2 and having it equal 4 but then adding an additional value to the 4 and claiming that the arithmetic cannot be correct. Program A is thus NOT found to be wrong but that the reverser program, a meaningless function in the scheme was added quite literally to corrupt. The entire analogy is a fraud. Go back to Quine’s ridiculous liar paradox, apparently so admired by Turing and Goedell. In it, i.e., “this statement is false”, the term “statement” is the subject noun, but also a set definition, in this case with no members, i.e., there is no reference object, forcing the listener to understand it as self-referencing. Were it, “this statement, that the sky is green, is false”, it would be logical and legitimate. But statement in this case is not a noun like rock or rabbit where the meaning is “self-contained” so to speak. If a researcher were to state to his underling absent any prior utterance, “use that definition” but without any reference to any particular definition, his response would be, “what definition?” Quine’s paradox was piffle and not a paradox at all. It is like stating that “your idea is too heavy”. It is meaningless. Yet one purported to be so brilliant such as Turing or even Goedell admired it immensely, as I understand it. Doesn’t compute for me. Quine’s liar paradox violates the law of non-contradiction and has no semantic value whatsoever. If one were to claim that it does, he would be then stating in extension of his defense of it that there can be no set theory or set definitions of any meaning and turn that particular field of study on its head. It just makes no sense. Most, though not all, self-referencing statements are meaningless. As to my comment on Turing having promised not to introduce into his field any contradictions, I somehow got my critique of the videos on Goedell with Turing. Sorry about that. So, what do you think?
@@jamestagge3429 it seems you think the reverser program can’t run because program A can’t analyze it. I don’t see why it can’t, plenty of irl examples of programs being able to analyze itself exist, plus we define A to be able to take in any program. you seem to think that since the reverser program adds extra code to program A, that program A is not wrong, but the reverser program. the problem with that idea is that program A is in the reverser program to begin with. imagine someone, Hank, claims to be able to answer every yes or no question asked to him with “yes” or “no”, and he will always be correct, aka be able to see the future. To disprove his claim, i ask him “will i ask you another question?”. regardless of if he says yes or no, i simply do the opposite of what he claims. there’s nothing paradoxical about my actions specifically. Hank + me is essentially the reverser program in this scenario. the reverser program is a paradox, that doesn’t mean Hank isn’t the problem. Since I found at least 1 question i can ask Hank, and have him always be wrong, that automatically disproves his claim of answering every question correctly. as for the whole liar paradox debunk, while i do agree with you, i don’t see its relevance to this problem (i misspoke on a previous comment). if A thinks reverser will halt, it will loop, if A thinks reverser will loop, it will halt. that’s effectively the proof. again, i recommend watching udiprod’s video on it, there’s also a link in its description containing several faq’s about it
Yes, you can. But it cannot work for all programs (or might itself get stuck forever when it is attempting to solve for them). There is little use to such a program. Of course it's better than nothing for cases when it can say "it halts", or "it loops forever". But you don't even know if itself will ever halt. It's not reliable enough.
This could be dumb, but, can't you just check if the program gave a output (meaning it ended/returned), or if it executed the same code over and over again? Wouldn't that solve the halting problem? If it returned, then it halted, if it did the same thing for a bit, it looped (I'm not saying check if the vars are the same thou, what if it was finding primes?).
This seems as if a judge in a court is going to kill himself if the suspect is innocent. I don't understand why such a problem should be solved like this? why not analyze the code instead and just predict if it halts or not.
Whilst I completely accept the validity of Turing's proof, I still can't help wondering how I've been able to write programs for the last 40 years which don't get stuck in loops (after suitable debugging, of course).
Boah this channel is amazing, you have an incredible ability to explain things clearly while avoiding oversimplification. I'm sure that if you keep on going you will eventually get the number of suscribers you deserve.
Thank God I finally passed my NP test on my 3rd attempt with the help of Mr DAVID, I used his preparation tips. just 3 days of working with him and I passed. I was referred to him by a friend before my exams. Please friends I recommend you to mr DAVID. The man has the key to getting your exam.
I don't think your diagonalization technique proofed that agent smith doesn't exist. I think what you proved is that an uncountable infinite number of programs exist.
Why are we giving Smith to Smith? We assumed that Oracle was the program which could predict the halt. Shouldn't we give Smith to Oracle and not smith to smith!!
you could have 3 magical oracles explaining this shit and i still wont understand it.
Tsavorite Prince And that means?
Marat That means Smith will contradict the Oracle no matter what, bacause Smith is designed for that specifically, as easy as that. And because the assumption is that the Oracle would be able to predict what Smith will do there's a contradiction, and therefore the assumption is wrong. Thus there's no Oracle which is able to predict Smith behavior. And that's all.
@Fuert Neigt now i am not worried about my exam tomorrow ..!
I can't understand this shit either. I got the idea but I can't correlate this apparent contradiction with anything in real life.
@@MrSpock-sm3dd I'm not the best person to explain it either, but I will try to give at least a context for it.
Some decades ago, there was that question about if a computer/Turing Machine could solve any problem it was given.
This was something pretty difficult to prove, because to prove that, it would be necessary to prove the possibility of the creation of a machine/program that would answer if the given input code - the code of other programs - would halt if executed (return an answer, even if it takes hundreds or thousands of years) or if it would loop forever and never stop computing.
As that was something inpractical to prove, Alan Turing instead tried to propose why a machine that powerful couldn't exist, through contradiction (a solid way to prove or disprove things in mathematical language).
Alan Turing assumed that this all-powerful machine really could exist, and all that he needed to do to disprove that "it's possible to create a machine/code that can detect if another machine/code will ever stop or if it will loop forever" was prove that using this hypothetical machine, he could use it as part of a bigger machine that would intentionally loop with certain inputs.
Then, with said bigger machine, he would give two inputs, both of them being the bigger machine's own source code/descrition. If you're interested, the general way the process works is the following:
- You can skip that part if you want-
1) The bigger machine receives the two inputs mentioned above;
2) The all-powerful machine (imagine it somewhat like a compiler) inside it receives the code of the bigger machine, and runs it with the own code of the bigger machine as its own input. Then, it's gonna return YES if it stops/returns something, and NO if it detects that it would loop forever;
3)Another machine was attached to the end of the all-powerful machine, and receives its output (YES/NO) as an input and does the following: if it receives YES, it enters in a loop; if it receives a NO, it stops.
4) If the input code of the bigger machine loops, then the bigger machine testing it will stop; if the input code stops/halts, the bigger machine will loop. That's a contradiction.
Spoilers: Turing managed to prove it. He used the all-powerful machine to create a situation were it would contradict itself, so proving a machine like that couldn't exist.
I didn't explain it in the best way possible, and I still get confused about some parts of that proof, but I hope it can help you and other people here to get the gist of this situation!
If you're confused by the first version of the proof, and have a little programming knowledge, here's a little more explanation with pseudocode:
Assume we have "function oracle(a, i)" which can tell if a(i) loops or halts. We now define a new function:
function smith (a): // a is a program
if (oracle(a, a) says loop)
return;
else
loop();
The question is, what does smith(smith) do, and what does the oracle say it does? If the oracle thinks that smith(smith) will loop, then smith will halt. Similarly, if smith(smith) loops, it's because the oracle thinks that smith halts when run on smith.
Whether smith actually loops or halts when run on itself, the oracle gives the opposite answer, which means that it must give the wrong answer. Therefore, the oracle can't actually solve the halting problem.
Undefined Behavior I
I agree, the problem is oversimplified and thus fails to convey the concept in a meaningful way.
It's like comparing an undefined var. Is N = N? Error N is undefined.
The "Oracle" would need to know all possible states of a program after it's evaluated.
So:
~~~Pseudo Code~~~
Oracle(smith(hampster)) = LOOP
Oracle(smith(helloworld)) = RETURN
Oracle(smith(smith)) = NULL or "Undefined"
~~~Pseudo Code~~~
smith(smith) isn't valid because the second smith was called without a parameter to evaluate it.
it would need to be called smith(smith(hampster) ) )
in which case hampster which would return LOOP to the inner smith function
in which case the Outer smith function to return RETURN
You need to know what smith(NULL) would return in order to return smith(smith) in the first place.
It's like trying to guess the number someone is thinking who just lies and changes the number in their head.
It's nonsense to think a program COULD predict the number they are thinking, much less when they lie about it to always ensure it's wrong. The computer can't win! ;)
To me this problem seems intentionally obtuse. You almost have to dumb yourself down to understand it.
I understand what it's trying to say, a program can't predict everything and every possible outcome.
Well... maybe a quantum computer can since it can have much deeper logic in it's most fundamental level.
In a Quantum computer, agent smith is both, looping and returning at the same time. His states wouldn't be mutually exclusive.
It's setting up a paradoxical situation intentionally. That's where people are thrown off by the "Deeper Meaning" of this and I'm sure others intuitively understand what I'm saying on some base level they get the feeling that this is wrong, and they are right with that gut feeling.
@LarcenIII on Twitter
Best explanation i've come across so far..thanks a lot for this..btw some amazing stuff here on your channel .Subscribed.
I hope you guys can link Zeno's paradoxes to this series. Awesome work tho :)
666 likes......
I find the argument somewhat confusing. There exist an oracle (function) for the halting problem since the problem is mathematically is completely well-defined. What the argument shows is that this oracle (function) cannot be programmed i.e. is non-computable.
You can try to explain this in an infinite number of different ways, and I'll always not comprehend it.
you are an exmaple of row b that halts on every input
@@SogMosee I wish you could give gold on youtube.
@@SogMosee BURN
I shall explain in the lowest level possible even though I just watched this video 6 mins ago...Let’s use an analogy.
Let’s assume you have a set of containers(programs ) and then you have a set of fruits(another bunch of programs).
Now when you put a fruit inside one of the containers, you get two outcomes. They spoiled(halt) or remain fresh(loop). Now let’s make another program, the main dish program. It’s job is to show the opposite of what’s happening inside one of the containers. If the fruit is spoiling inside the containers then the “main dish program” will show that its fresh and vice versa.
To summarize you have three programs; -The main dish program
-The containers program
-The fruits program
Each fruit program goes inside their respected container programs and the main dish program checks whether each fruit is spoiling or still fresh and tells you the opposite. However, it’s impossible for the main dish to do such a thing because of how much computation is required to run an infinite iteration of each programs on top of one another, looping and not looping, since a loop requires a lot of processing memories or something. On the other hand, you can write a program that can do such a thing for some finite amount meaning you can’t make it loop forever. The difference is really trying to make a program that loops infinite times for three different programs which is yeah...currently impossible, maybe with quantum computers
If there’s anyone out there who’s more knowledgeable about this topic then please correct me since I just translated what I watched a few minutes ago to something that I can understand.
then you don’t exist lol
but why can't the program work for an input that isn't itself?
It can. Halting problem can be solved for an unknown set of programs except one instance laid out in the theory. So we can conclude that Halting problem cannot be solved for all possible programs, but maybe a subset of them.
It took me 30 minutes to figure it out! Thanks for the tutorial!! I think the Cantor's diagonalization makes more sense and after understanding it, the contradiction (solution 1) makes more sense.
Ahh I see what you did there. Why doesn't this have any likes?
You're being a little bit disingenuous about the nature of the Halting problem. It's impossible to solve it in the general case. It's not impossible to solve it for certain classes of programs. From a practical point of view most programs we write are easily analyzed by our tools, so it's common for IDEs and compilers to point out where programs have endless loops and unreachable code.
but thats the beauty of it; you can write a decent algorithm to find infinite loops within code, but can never write an algorithm that will find ALL infinite loops within any algorithm! makes us keep writing algorithms :P
@@Ibenlo I was confused in a similar fashion when my prof explained it. But a guy in comments pointed out the correct quantifiers.
But first, we need to talk about *Parallel Universes* *Mario 64 select file theme starts *
Ggero TJ "Henry" Yoshi
I was reading Roger Penrose's book on this, and he just rushed the explanation in one sentence - your cartoon from 3m50s is brilliantly clear!
really good and clear proof of the Halting Problem using diagonalisation - many thanks
What's that guy doing there at 3:09? Is that an easter egg featuring XZBIT?
Best vid on the Problem so far...good work man
This simple proof of the impossibility of the halting problem glosses over the fact that the halting problem is only undecidable for programs with infinite storage. If a program has finite storage one could in principle make a list of all the states it passes through (including the state of all memory locations). If it revisits a state without halting output "loops forever", otherwise when it eventually halts after visiting all the states it can, output "halts". This obviously doesn't work if the program has infinite storage. It's interesting to think about why the "Mr. Smith" argument doesn't work for finite state machines.
While there is a philosophical solution, a practical one exists. You halt all programs after a certain amount of time has passed. You may prematurely halt a program that is still running but if it is more desirable to free up resources and go to something else, then a maximum time makes sense.
Dude your channel is awesome! Keep up the good work!
I love the fun graphics added to make proofs more digestible.
I always think of looping as returning to a previous state. And you _can_ check to see if a program does that. The programs that do not halt and cannot be determined not to halt consume ever more memory and enter into ever more complex computations.
its not that simple. calculating more and more digits from the decimal expansion from pi is easy (standard cpu benchmark). imagine i gave you the assignment to write an algorithm that answers the question: if i give you an integer n, does pi have exact those digits in the same order at some point in his decimal expansion?
sure, for some inputs the question is easy, like if i give you the number 31415. but if i give you an arbitrary number, 4589789023714878572893417897460900910293123 your program has to calculate pi till it matches the digits. so will it stop or not? you cant decide if you didnt wait long enough and there is an answer (yes or no) or if it will loop forever. maybe pi is so arbitrary that every pattern of digits eventually emerges. maybe this is not the case. if we knew more about pi, this problem would be decidable and the algorithm to decide it would be really easy. output yes or output no, there are no other cases.
That falls into doing ever more complex calculations (unless a given sequence is found.)
so youre trying to tell me, i should start my debugger, let my program run and look for a while. as soon i get bored i quit and simply say: alright, this program doesnt seem to halt.
i could nobody convince that the program i wrote wont halt, because i say: well i got bored and stopped waiting, trust me, that program is looping infinite and will never stop.
if you need more complex calculations, then you have to do them. because the program might halt eventually and this is what all this is about.
simply saying "i cant see that any progress is made, its just doing more and more calculations, i just assume it will never terminate" isnt the way of solving the halting problem. by that logic, someone who is extremely impatient, will never write any code that will terminate. if he immediatly gets bored, he could stop the debugger before the hello world program could print the output to the screen.
what i want to tell you is, there are programs that calculate more and more complex computations and consume more and more memory and will halt (maybe it takes 3 years of computation to finally reach the matching digits in the decimal expansion of pi) and there are programs that do the same but wont halt (maybe the digits will never emerge). the question is, is there a way to tell them apart? and not for a specific program, the question is, is there a way to check if any arbitrary program terminates with a given input. and as proven in this (well done) video, there isnt.
I'm not trying to tell you that you should do anything. I am stating what my concept of a "loop" is. And it is a detectable phenomenon. These undecidable programs, while they do not terminate, also do not fall into a pattern, and so do not fit my idea of a loop.
oh boy i didnt understand what you wrote in the first place and why :D english isnt my mothertongue...
i thought you wrote your comment to point out that its not hard to decide if some code will halt, since you can check for reaching a previous state again...
sorry for the confusion on my side!
Have any comments on intuitionistic logic/constructionist math? They reject the law of excluded middle, and so double negations don't equate to a truth.
In this way they also reject existence proofs by contradiction. So here's my question, if we prove something that is not constructable can not be false, then is it true?
It seems to me that we get stuck into some kind of limbo where we have proven that it can't be false. So that's super clear.
But if it can't be false, and it also can not be constructed, then does it exist? Or is it something like, "well it can't be false, but it also can't be true, so it just doesn't exist."
But, if we prove that it can't be false, does this also mean that if it isn't constructable that it exists?
And, if we prove that it can not be false, doesn't this also mean that it can't not exist, since we've proven that it can not not exist? (or does this count as relying on a double negation in classical logic?)
It just seems odd that constructivists think we can prove something can't not exist, and turn around and say, "welp, I can't construct it, so I guess even though I proved it can't not exist, it doesn't exist after all." It's like they go around contradicting themselves. Or in a different sense, they don't trust what they can't empirically perceive.
Metaphysically it would seem that intiutionists/constructivists would be considered radical empiricists, but the ironic thing is that many of these mathematical objects that they are trying to construct obviously don't empirically exist in the external world we interact with using our perception. So it's like they're only comfortable if they can construct something that only exists in some platonic mathematical universe disconnected from true empirical perception anyway, so what does it matter whether or not you can actually construct some idealized mathematical object if you are already 100% certain it actually doesn't exist in perceptible reality? I mean, c'mon that just seems silly. One example of this is perfect geometries and irrational numbers. Perfect shapes do not exist in the perceptible reality we live in, and certainly irrational real numbers also do not exist. Infinity is up for debate (not sure whether the physical scientific universe is finite or not, different from the mathematical universe Platonist's think of when speaking about infinite sets and what not).
If you're already considering only some idealized platonic universe of rational thought, if you prove it can't not exist (using logical deduction absent of any empirical observation) why not just assume the default is then, rationaly speaking (again, void of any empirical perception feedback at all), that if it can't not be false, then that means it can not be false. Period. Concluding that it must not exist because it can't be constructed seems to me to be the same as concluding that it can't exist, even though we would have proven exactly that the object couldn't not exist with a proof of a contradiction. So I don't think constructivists have any real arguments.
Now, the one exception I can think of is when we are dealing with mathematical objects that *actually do exist in our scientific empirical perceptible reality/universe/multiverse.* For something like number theory, say, where something is proven by contradiction but also can't be constructed or observed physically via perception, well then that's a slightly more convincing argument, because when an object actually exists in our perceptible reality then all of modern science suddenly supports more strongly the constructivist argument.
In some ways it would seem that we have to parse/separate between the empirical mathematics and the non-empirical mathematics.
And then depending on whether you are a rationalist/realist or an empiricist, you could be allowed to create theoretical models of our reality using mathematics that isn't constructible or that doesn't exist in our objective reality. This comes into play especially when we think about theoretical physics.
The question becomes, are we *allowed* to use mathematics that has no bearing on physical reality to explain perceptible physical reality, ie, the areas of objective reality, if they exist, that can not be empirically perceived with our 5 (or more) senses. The question is, *are we allowed* to use idealized, and even more strongly, non-constructible, mathematics to describe the areas of reality that aren't empirically sensible, and for which experimental science *can not* apply. This all reminds me of Zeno's Arrow Paradox, and how our rational thinking, even in 100% logical, often contradicts our empirical science.
And guess what, arguably, all of mathematics, especially in ancient civilizations, is founded on our *empirical senses,* especially *vision and touch.* As just one example, the entire concept of "a number" arose out of vision, ie, looking at a thing, and finding visual boundaries in it to "count it" discretely. This is where numbers come from, this is where mathematics comes from. And any abstraction built on this empirical perception is unavoidably tainted by our perceptual information, and in this way if we allow ourselves to use mathematics to describe the parts of physical reality, if they exist, that we can't perceive, then we are making *the large assumption that the areas of reality we can't currently perceive are similar to our own realities.*
Anyway, my personal opinion on all of these things, ranging from intuitionistic logic, to metaphysics to theoretical physics remains unsure. On one hand it seems wrong to say that unperceptible reality might not be similar to the reality we can perceive, but on the other hand, our rational logic often contradicts our empirical senses, (Zeno's Arrow Paradox), and all throughout history, every time it was rational logic vs empirical science, the empirical science has always been the correct argument, over the rational logical deduction.
You know, the only place to go from here is to speak about death, and what the sources of perception are, and whether or not you believe in the soul, and an independent mind, or a fully biological multi-cellular argument in which a person, or any living being is nothing more than a temporary sum of its parts, only to be disassembled and reassembled again through time.
I guess neither of these two views on death are particularly terrible. If we assume we are all part of the sum of our parts, and the conservation of matter applies, then we never become less or more, and our cells have lived in another being before they came back to build us, and they will continue to be reformulated to create new life again in the future after we die, and this constant separation and reformation is actually quite a beautiful and comforting idea. I believe this is the origin of the notions of eastern religious spirituality, specifically Indian origins of Hinduism and Brahman. And the concept of the "mind-body duality" is clearly a western dichotomy put forth by Descartes. Many engineers becomes obsessed with their own consciousness at some point and "turn" into Cartesian Dualists, at least I like to think this. I like to think they flail about shorting cognitive circuits and spinning cognitive tires trying to make use of heavily computational and applied mathematics and physics (like calculus and classical physics + recently a shallow understanding of particle physics, because that's all the engineering curriculum teaches... lol) to try and tackle the issue of their perception and consciousness, and ultimately, their human experience. But I think these people are doomed to failure because they're not familiar with the philosophical ideas at hand, nor are they equipped with the true theoretical understanding of mathematics to actually make headway in this department. Personally I'm much more willing to accept Brahman as a metaphysical explanation of consciousness than a Cartesian Dualism theory.
Oh well, I hope you enjoyed reading a little of that. I do think it's all relevant to the question of whether or not constructivist mathematics is something to take seriously, because ultimately it is a metaphysical, or at least epistemological, type of argument against classical logic and classical mathematics (which uses classical logic to be "rigorous").
Thanks.
This may sound stupid, but why is Mr. Smith designed to do the opposite? Why did we have to translate the diagonal loops and halts to their opposite? If we're finding proof by contradiction, aren't we already assuming that the oracle exists? Why do we have to bring in Mr. Smith again for another contradiction? i.e. why can't we just leave the diagonal untranslated?
It is simply an example of how to generate a new line that isn't in the original matrix. It is a guaranteed way of doing so.
Well, according to me this proves that there are programs for which the Oracle will give the wrong answer. That means the initial assumption that oracle knows all is wrong.
I hope that helps :)
We assume we've found an Oracle that knows how to solve this problem (it knows the entire matrix as we've constructed, e.g. can determine whether any program will halt given any input). The point is, we can always create a Mr. Smith who does not exist in the matrix*, and therefore does something the Oracle can't know, contradicting our assumption the oracle knows all.
* No pun intended, I'm literally referring to the dimensional grid we've constructed...
Unreal content. Where have you gone?
You are almost at 1000 subs. I can't believe you have so few, this channel is amazing.
But didn't you just prove that the list of all programs is uncountable? It seems to me like saying you can't put real numbers on a grid, therefore they don't exist.
Sort of. The list of all imaginary programs is uncountable, but the list of all computable programs is countable (because they have an arbitrary, but finite length).
This means that Mr. Smith is uncomputable, so you would never be able to actually write the computer program that matches his behavior in terms of looping and halting, for all inputs.
en.wikipedia.org/wiki/Computable_function#Uncomputable_functions_and_unsolvable_problems
EDIT: Let me clarify how the diagonalization works. Because we know that computable programs are countably infinite, we can make the grid seen in the video. We then create a sequence by taking each element from the diagonal and flipping it. This new sequence defines the behavior of something, but it isn't necessarily a computable program. In fact, it cannot be a computable program because it cannot appear on the list. However, if we could solve the halting problem, then we could easily write the program with the same behavior.
why does mr. smith exist in the first place? what actually is his role if the oracle already determinates whether the program loops or not? is this just how the problem is defined?
if it is and we put this into a tautology, we get 2 conditional statements:
1. If oracle says halts, then smith loops
2. If oracle says loops, then smith halts
now let's say for 2. p=If oracle says loops and q=smith halts
but this wouldn't make any sense because the condition p->q is false when the hypothesis(p) is true and the conclusion(q) false and at the beginning we said that the oracle is always right, meaning the oracle is always true.
Also if we use p and q for the 1. we'd get p'->q' with the same outcome.
@@UndefinedBehavior I was thinking the same question!
This is simply Superb!!!!!!The best one I watched on Halting Problems......The animations made it even more clearer.....Keep it up...Thanks Cory...u rock!!!
Subscribed! I needed some help on Cantor's Diagonalization and your videos came up and I got hooked. They're awesome! Thank you!
That was incredible. I'm really enjoying your channel. Keep up the great work!
It seems that both contradictions depend on a program that has access to the output of the Oracle. But that seems odd. An Oracle should be independent of the programs that it analyses.
So, the Halting problem for *all* programs might be unsolvable. But this does not hold if you limit the domain to programs that do not have access to the output of the Oracle (i.e., the Decider program).
Agreed. The problem only seems to be unsolvable in a trivial, academic, useless program, so who cares? Is there some larger point the creator is driving at? He didn't explain.
At 5:08: _"Since the list is a complete list of all computer programs, that means, that we can never write a program, that matches the new row, that we generated on all inputs..."_
That's not correct, because _the list is_ *supposed to be* _a complete list of all programs_ *and yet* _we can_ -never- _write a program, that matches the new row, that we generated,_ *not appearing on our supposedly complete list of all programs.*
Hence, our list was and is incomplete and is incompletable and therefore, the "oracle" - a program capable of deciding about any halt problem - is not possible.
The conclusion is correct. But the deduction to that conclusion is not quite correct.
No. An algorithm is a finite object - under any of the equivalent definitions (e.g. Turing machines). It follows: there are countably many algorithms - countably many Turing machines. (Equivalently: there exists an infinite sequence containing all Turing machines.)
@@MikeRosoftJH Sure. An algorithm is a finite object. But a program doesn't need to be such a finite object as presented that infinite way in this video.
But that doesn't mean, that it is completable as shown and demonstrated at 5:08, even if we make the assumption of a Turing machine with an infinite amount of memory.
So, we have an algorithm A that branches to a loop or a halt, according to an input. This input is the output of another algorithm B, which predicts whether a _third_ algorithm C will branch to a loop or a halt. A will do the opposite of what B predicts of C.
But it can't do that if C is a duplicate of A.
EDIT: Except...isn't this just B correctly predicting the output of C, and A inverting it? B can't predict the output of A, but that's not what it's trying to do. It's only been fed C.
Does this assume an infinite number of possible inputs? If so, why do we need the diagonal example since the search space would be infinite? Even if not, how could we even attempt to solve the problem in a way that isn't just running the code?
These videos and your channel are really helping with my 'Theory of Computing' course. You deserve so many more views.
This is a very accessible explanation of beginning logic for people who enjoy learning with pop-culture imagery. I positive it will help some students immensely. I especially appreciated how you showed the two proofs to be identical, after a fashion.
Perhaps as a follow-up video, you might give an explanation why "the halting problem ... was instrumental in forming the basis of the modern computer," as stated in your precise. I mean, I think it is quite interesting and not at all obvious how an undecidable proposition such as the halting problem would help form the basis of the modern computer.
Questions: It's obvious that you can just hold numbers/booleans in an array to see if they repeat and kick out of a loop if they do.. but that wouldn't work for numbers increasing dramatically.
say:
integer x=1
while x>0
x++
Would go on indefinitely, or until it hits an integer cap 2,147,483,647 and fail. Did anyone ever design a work around for this? You could probably set a lower maximum x bound in your while loop if you aren't expecting it to repeat for too long.. but is there a way for a program to recognize that incrementing by 1 won't get you any closer to being under 0? Guess not because you could always have a line in the code that says 'if x=100000000: x=0' a while loop can't really see what it has in it so it would be going until the integer overflow..
Is this related to Gödel's incompleteness theorems?
you are underrated af you deserve more subscribers
Incredible explanation! Thank you.
This is the explanation we deserve! ♥️
But what if you exclude programs that base their input on the oracle program? That seems to be the source of the issue.
There's a few points to make here:
1) The fact that the oracle cannot exist is precisely the point. If it did, we would be able to create programs which disprove its correctness (we also have plenty of programs that we can write, but we have no idea if they actually halt or loop).
2) There are still other uncomputable problems (e.g. the busy beaver function en.wikipedia.org/wiki/Busy_beaver).
3) Interestingly, how would you know if one program is embedded in another program? To simplify, how would you know if two programs are even the same at all? The code might be different, but if the output of both programs match exactly, we would consider them the same, right? However, verifying if two programs have the same output is another uncomputable problem (for a similar reason to why the halting problem is uncomputable).
If the video is esoteric, we humans have to basically tell the machine what is an infinite loop and what isn't. So to piggyback off of the video's explanation a bit, compilers themselves have no algorithm that can understand the behavior of while(true); and tell that it's an infinite loop. There is no algorithm that can tell the difference between a real infinite loop and a program that just takes a really long time to run. We have to just specifically tell it "if you read true within a while condition then halt".
For programmers out there, it's the difference between a anomaly detection method and a signature-based detection method. Anomaly detection is great, but can come with a lot of false-positives and won't likely catch all examples of what you're looking for. Signature-based (defined programmed behavior) is not as ideal but will for sure catch the case you're looking for and is often the go-to solution for this type of problem. We often make compilers signature-based when detecting errors.
These issues in computation are the real reason that A.I. isn't very well progressed in modern times. It appears as if A.I. is very wise now and many media outlets over pronounce the progress to comedic effect. But the honest truth is that A.I. is extremely dependent on explicit definition currently. To those who watch A.I. beat really old NES games, the amount of failures VASTLY exceed a normal human's amount of failures, and that's just of simpler games. More modern games which are designed to be more understandable and don't resort to cheap shots or surprises to kill players are nearly impossible for modern A.I. to complete. Ironic, as hardcore gamers say games are too easy these days, but computers would have a different response, haha.
Okay but why Oolong with wings? Also, can't you just check to see if the memory state remains constant while the machine instructions are repeating?
There can only be infinite length programs in theory, given that a program has a finite length, and only 0-s and 1-s can be in it, there can be only finite variation's of programs, so Cantor's diagonalization doesn't work on them, so if we limit the programs in length (software and hardware limitations exists) can there be a program that gives the answer?
What ??
Explain yourself.
x = Input:
while true:
print("Loop")
if x = 1:
print("Halt")
break
What about this program? I can fairly easly make a very precise statement on when the program halts or loops. If the Input == 1, then it halts. For every other x it loops. So clearly I did not understand the Entscheidungsproblem.
We can make programs that determine whether a program halts or loops in SOME cases. The video demonstrates we can't make one determining it for ALL cases.
Very Nice Explanation!!
So would how about we add a third output of "incomputable" which triggers under the circumstance that the oracle finds that it's own source code in the input code with the same input as it's own.
Would this make it possible for the problem to always be solvable (as in being always correct about halting or not if it is possible and always returning unsolvable if solving it would create a paradox)?
Isnt the Oracle suppose to be african american?
I'm afraid I don't understand the difference between a program and an input. Could you demonstrate it using an example?
Why would proofs either loop or halt? Axioms are always true, so they would halt either way? Looping would mean it's not provable right?
Really though I'm so confused. I keep watching video's about the Halting problem/Gödel's Incompleteness Theorem but I can't seem to grasp it.
Is a good example for a program: a calculator? And an input could be: 1=1? But don't we know that the program will always halt, since 1+1=2?
Sure! In this context, it's best not to think of programs and inputs as different at all. Programs are just text files (which are really just numbers), and there's nothing strange about feeding a text file or a number into a program. In fact, your computer's OS is a computer program which takes other programs and runs them (like your internet browser). You can also think of a game console, which uses a program (the game system's OS) to execute another program (the game). Here, the game is an input to the game console.
A really simple program we can write that takes in another program might be one that returns the length of a program. All we do is look at the program, count up all the characters, and return the amount.
We know we can do some simple static analysis like this pretty easily, but now we move onto the actual behavior of a given program. We can write a program that answers the question, "Does a given program finish within 10 minutes?" All you do is take in a program, let it run for 10 minutes, and check if it's done or not.
Now the question becomes, "Can you tell if a given program will ever stop?" This question seems like an extension of the previous one, but unfortunately it crosses the line between a solvable and unsolvable problem.
"axioms are always true or false"
'the statement below this one is false'
'the statement above this one is true'
BOOM, BAYBEYY!!!!!
best video explaining the halting problem!! Thanks
awesome channel you have here. i liked you used the cantors method. you are the first one i saw doing this on youtube.
What if the oracle could tell you if a program loops or halts as long as the program doesn’t involve the oracle itself?
This is blowing my mind. I can’t fathom THIs
"when that program is run with itself as input..." that makes no sense, are you assuming all programs take inputs? and only 1? and of random datatype?
This is a good question, because it doesn't really look like this very math-y explanation maps to real programs.
For the number of arguments, we can treat it as if all the arguments are "bundled". Ex. If the program accepts 2 number arguments, let's just think of a version of that program that accepts a string like "5 12" and parses that for the two numbers it wants. If the program doesn't need any arguments, it just ignores whatever you give it. This can be generalized to any number of arguments. And it can work for arguments of any type as well, since any value can be serialized to a string (JSON, some byte stream, or anything else).
Let's also assume that these programs validate their inputs and halt (maybe by throwing an error) if the input is invalid. Ex. while a program is doing the aforementioned input parsing, if it seems that the arguments are invalid it just throws an error.
Programs aren't really altered by either of these assumptions. If the input is valid and parses and all that, then the program is still doing all the same logic. If the input is invalid, it'll halt with an error.
And as for the rest of the proof, it doesn't really matter whether a program is a valid input to itself. What matters is that there is no oracle that can determine for ALL programs whether the program will halt when given itself as an input.
In practice, for most programs it'll be pretty obvious. If you look at "function sum(a, b) { return a+b }", clearly it won't accept its own source code as an argument and it will halt with an error. (Really, if this is JavaScript it would probably work with string concatenation, but again let's assume we have a version that validates inputs. Either way, it'll halt). But since there are an infinite number of possible programs, many will be much more complex and run on all sorts of different kinds of inputs. And there will always be some program that trips up the oracle.
There cannot exist an oracle that is 100% accurate, which is all that the proof is saying. But it is certainly possible to have some "crappy oracles" that are less accurate.
The point isn't whether or not this actually applies to the sort of programs we tend to write. The point is that this proves that a program that decides whether every possible program and input loops or halts cannot possibly exist because the program you're proposing is self-refuting. Obviously we can analyze certain classes of programs, but we are unable to analyze *all* classes of programs.
If something is built to contradict something self, the Orical is correct; the other thing is going out of it's way to be such an issue.
I am having a severe existential crisis right now, having my final next week which is based on this topic is not helping...
How did it go?
@@richardjames712 lol that was 2 year ago when I was still a cs freshman. It went well and saved my grade at the end thank god
i really liked your video! That must have been a lot of work
I want Robinsons Place Dumaguete to be constructed quickly and not be aborted and delayed and the heavy equipments are going to be used at the Calindagan site while the other one will be in Pampanga.
I like how he just casually put Mario and other characters in there.
Also my brain just exploded ; - ;
i hope its better now
Thank you!
I've watched a number of other videos on the halting problem that didn't get to the heart of the problem: Proof by Contradiction, which you've nicely illustrated: . This logical proof also helped me see the connection to Godel more clearly.
other program just can look at the programs source and it can finds if its looping or not.
This is amazing I actually get it now
Thnks, awsm explaination, and also thnks for the code snippet example.
What about non-deterministic Turing machines. Might they solve the Halting Problem?
does program b have a syntax error
the problem with contradiction is jumping too many steps. if A then B. if not B then not A. you forget there might be an A1/2. so if not B then not A1/2 but still maybe A.
If anyone's confused it might be because this proof comes with a big pre-requisite of infinite memory that's not mentioned. And that doesn't actually exist in the real world. Halting problem is solvable with finite memory because there are not infinite states. In fact it's not even that hard if you are simulating. You simply collect all conditions that lead to loops then determine the possible states of the conditions. Once you find that every condition of the enclosed loop is itself a closed loop, you have an infinite loop. You only can't do this if the states are infinite. Infinite math is pretty bogus TBH. You always get crazy theorem like this.
But that being said. The real problem that makes determining if an infinite loop is subjectively "bad" or "good" requires outside information. If there are any side-effects in the loop, then those side-effects may actually be the intention of the program running as expected. The beginning of the video where the spinning wheel was used, is a bit misleading, because a spinning wheel is not a reflection of the theoretical halting problem, but of the event system being blocked not allowing any user-input past some hard limit of time.
e.g.
let a = 1
while(a != 0) {
a = random()
}
We can simulate the above program and know the conditions of the loop are a, and any of the possible ways that a changes, which is only random(). Since one of those possible outputs is 0, and a 0 could still theoretically happen, we would not detect it as an infinite loop, even if it could run for a very long time depending on the bounds of random(). This is absolutely possible because random() is not infinite on any real world machine. Only by saying that the bounds of random() are infinite, do you conclude that the probability of random() being 0 are 0. Again, infinite math is kinda bogus. At the end of the day, all this proof is really showing is: "if you had a theoretical program with incalculable calculations then calculating if it calculates the incalculable is incalculable" and my answer to that is "duh".
Of course this isn't useful. What an actual person would want is some way to detect if a program stops making human-useful side-effects after a human-reasonable amount of time. Which is what operating systems currently check for.
what happened to the audio?
beautiful videos
This channel is amazing i can't believe you only have 900 subscribers
Walter White We gon' change that
Thank you so much, keep it up!!
why was oolong there?
So, in order to "know everything about the universe" (i.e. be "omniscient"), you'd have to actually 'calculate' -- i.e. "run" -- the universe? Or, stated another way, creating a perfect and complete copy (i.e. "model"/"map") of the universe [which would, of course, be part of the universe by definition] is impossible?
*Anthropos Cartographer* (the next cognitive and evolutionary leap for the species whose antecedent referred to itself as "Homo Sapiens")
It's a map, people.
Constructing "[conceptual/internal neurological/sensory experiential simulator ("imagination") generated] models", a.k.a. "[onboard, sensory environment] maps" of our sensory environment --- as well as encoding and transmitting 'facsimiles' (i.e. decoded 'maps', in turn) of them to (a.k.a. "sharing them with") the 'onboard, sensory environment mapping computers' (a.k.a. "brains") of our fellow species members by means of our 'self-indicating/indexing/addressing sensory-information indicating/indexing/addressing' and encoding tool, "human language" [in conjunction with our other cooperatively developed media technologies] --- is what we _do_ ! (Apologies for the 'essay-in-a-sentence'.)
Note that the human organism's onboard, sensory-environment mapping computer uses the current state of its onboard map(s) as both 'map' of 'as is', and as its 'blueprint' for its 'to be' states (see "Turing machine") -- i.e. as its 'program(s)' to 'instruct' its subsequent sensory environment mapping/'interacting' [conditional decision] actions.
For example, "the scientific method" has proven to be our most powerful and effective (sensory and 'enhanced'-sensory) environment mapping technology/technique/algorithm to date.
We (human "civilization") are [i.e. hopefully will soon be] an intelligent, self-aware, self-improving, information processing circuit -- a.k.a. a [human societal] network. Take special note of the word "we" in that statement [because, in addition to the self-evident 'network' definitional reasons, "we" is "quantized" - I'll explain that later, or you can deduce the physical and logical significance for yourself, based on the nature of "the speed of light".). If we keep this in mind, and operate accordingly, there is no limit to what we can do.
Oh, and our new 'Constitutional Bill of Fundamental Human Rights', as the official minimal code of ethics and "law of the land" for the individual citizen, and for all organizations thereof (civic, private corporate, and government), is [i.e. hopefully will soon be] our foundational network protocol and operating system (NOS).
So, Thank You for this. (and in the meantime, 'Careful with those maps, Eugene.')
P.S. "Information": A specific pattern of momentum 'pulses' (waves) as input to a particulate mass object (PMO) I/O device, which 'reroutes' that input (maps it to) a correspondingly specific output pattern and trajectory of momentum "pushes", and/or stores [a portion of] it as a reconfiguration of its internal circuitry/structure/'point-radial momentum' ("mass")'.
See also "What is a Worldview" (ua-cam.com/video/AVAmY1HvExI/v-deo.html)
Your channel is awesome.
wait, what does it say about our brain being a computer?
bingo.
What's the actual problem?
Actually, the Oracle would go on a loop. If Mr. Smith (M) gave himself to the Oracle (O), the Oracle would have to put Mr. Smith into himself, which he already did, so the Oracle would have to say neither.
I agree with you, this video is only assuming that the oracle can only output 2 answers.
Hmm, what does it mean to say neither, i.e. it doesn't loop or halt?
the Oracle says that Mr. Smith is a MF
What you wrote makes no sense, a program can only either run forever or halt at some point, there is on 3rd option
If your list of 'all' programs doesn't include the agent Smith program is really a list of all programs?
Wouldn't claiming to have a complete and simultaneously infinite list be claiming to be able to solve the halting problem assigning your list the definite state of knowably does not halt?
First, were there a program (A) called Halt which could determine whether a program (B) would halt or continue, it would by that very definition (as per the video) in actuality only be required of program (A) to determine whether a program (B) output fed to it would halt. It would not have to analyze if program (B) would continue on for that is the only possibility left if program (A) determined that the program (B) would NOT halt or whether it was unable to determine that program (B) would halt. If one were to deny this, he would by that be also denying that the program (A) had any ability to ever determine if program (B) would halt and of course, the instruction was to assume that it could.
At that, I think all is settled with regard to the initial goal defined. But in anticipation that this would not be sufficient for some….the goal as stated was to determine whether a program (B) would halt or continue as per program (A) which would output that answer. Then for some reason we are instructed that a program (C) would be required to take the output of program (A) as to whether program (B) would halt or not and do the opposite. Why? The goal was defined and achieve before program (C’s) introduction. This makes no sense. So program (B) performs its function, is judged by program (A) as to whether it will halt or continue on and program (C), as per the video is required to look at the output of program (A) and do the opposite. So the input of program (C) is the output of program (A) as per the function of program (B).
Claiming then that the program (C) would be input to itself and by that, create a contradiction for if it halted, it would continue on and if it continued on, it would halt, is the same fraud promoted in the liar paradox by Quine. In the liar paradox, “this statement is false”, self-reference is employed to generate the paradoxical function, i.e., if “this statement is false” is true that it is false, then it is false and thus NOT true, but then it is in fact false by that true, etc., thus the paradox. The liar paradox is complete sophistry and defies logic. The term “statement” in “this statement is false” is a set definition as well as a subject noun. But it is empty, i.e., it has no members. There is no reference object which might be judged as true or false. The adjective false (within the statement “this statement is false” is the means of its judgment), connected to the term “statement” by the linking verb “is”, is denied its function because the set definition/subject noun is empty. Here the term “statement” is not a noun like rabbit whose definition is self-contained so to speak. Additionally, this piffle breaks the law of non-contradiction as well as other logical rules. So, the halting problem is employing kind of self-referencing, i.e., if program (C) COULD run itself, which itself makes no sense, then the same kind of contradiction would be generated, i.e., that if it halted, it didn’t and if it didn’t halt, it did. How is this functional, logical or meaningful? Turing did not discover a contradiction in mathematics, he introduced one from outside, created one by the manipulation of the logic of the problem originally defined.
Can ANYONE show me if I am wrong and how? Tell me exactly where, because I think this is a fraud and it makes me suspect Goedell’s incompleteness theorem as well.
.
firstly, there’s nothing wrong with a program being able to handle itself. just look at recursion or virtual machines
we create a program C, which runs A and then does the opposite of what it outputs.
since we assumed that A already exists, there’s nothing wrong with being able to use it in another program. not exactly sure where your confusion of that is.
the fact that putting C inside C creates a liar paradox is literally part of the proof. it creates a paradox where A is always wrong, thus it cannot exist
@@Aagames_ Thank you very much for responding. I greatly enjoy these discussions. So, I don’t think I am at all confused. My study of this topic was not what Turing was claiming and whether or not he was right or wrong about the matter but rather the whether the analogies by others as to what he was claiming made any sense, and they don’t. So I think I can say that they do NOT proves his point but rather confuse it.
What you have missed is….(several points, a kind of compilation of several videos meant to validate what Turing claimed)
1. We are instructed to assume that there can be a program which can analyze another program and determine whether it would halt. This is necessary for the analogy.
2. If we proceed from this, we know that by definition, the program (call it program A) does not have to determine whether a program it is analyzing will continue on for there are only two possibilities and if it is unable to determine that it will halt, by definition it will continue on.
3. The point of the reverser program is to introduce a contradiction into the scheme, which we were promised Turing did NOT do. What is the point of the reverser program if program A has already determined whether a program it is analyzing would halt or continue on? The reversal of the finding of program A is not a function of program A. To then indict program A for being unable to perform the task for which it was written after a second program was employed specifically to corrupt its findings is illogical.
4. In this scheme program A is the only one that “runs”. The program it is analyzing does not, i.e., it is only that its structure is analyzed to determine what it would do when it ran. Therefore, if the reverser program is analyzed by program A, it (the reverser program) would also not be running (only its structure analyzed).
5. The reverser program is “available” to accommodate an analysis (which again, would not come) of either halt or continue by means of its structure. Therefore, if program A analyzes the reverser program, there would be no output of program A, which is the input of the reverser program, by which the reverser program would either incline to halt or continue on in opposition.
6. Even if we ignore that the reverser program would not be running, it would only be able to perform that function “after the fact” of the analysis and finding of program A (for it requires an output from program A as its input). It would be a step 2 in a sequence of two steps and therefore could only be considered logically disconnected, a link in a chain as it were, with program A. The effect of the reverser program does not then indict program A.
7. Given that there can be no output of program A that would act as input to the reverser program that would demonstrate its inclination toward halt or continue on, were the system of program A analyzing the reverser program fed to itself as a program to be analyzed, this system into which it was fed could also not then reverse the finding of the former first, for there would be none and second, for the reverser program of the latter would also not be running.
I could go on for several pages but I am trying to be succinct. These videos trying to explain Turings scheme do not make any sense and I have seen nothing that is logical that could be said to validate what Turing purportedly claimed.
What do you think?
@@jamestagge3429 ok i now understand that you're not directly opposing the proof itself, but rather the way videos explain it (tho im still not exactly sure in what way)
nothing wrong with 1 and 2
"The point of the reverser program is to introduce a contradiction into the scheme, which we were promised Turing did NOT do".
im not sure what you mean by what Turing promised.
"What is the point of the reverser program if program A has already determined whether a program it is analyzing would halt or continue on?"
the halting problem is a proof by contradiction, where we assume program A exists, then show that we can create a machine using A that causes A to always be wrong, therefore A cannot exist. it doesn't matter how we create the paradox (as long as we use logical steps), we just need at least 1 example of a situation where A is wrong.
i agree with you on 4
"Therefore, if program A analyzes the reverser program, there would be no output of program A"
we define program A at the start to ALWAYS give a correct boolean output, so "no output" isn't an option. when program A is given the reverser program, we don't know what it'll do with it, we just know that A will either output 'halts' or 'loops forever', since that's how we defined A.
"The effect of the reverser program does not then indict program A."
program A is inside the reverser program, and the reverser program does the opposite of A's output. if A thinks the reverser will halt, it will loop forever, if A thinks it'll loop forever, it'll halt. the programs being disconnected doesn't change the fact that A is always wrong in this case.
it took me a while to actually understand this problem too, so i understand your position. personally the video made by "udiprod" was the one that got me to actually understand why the proof works.
@@Aagames_ Again, thanks for responding...............So, the problem is that Turing claimed or perhaps others did, that he essentially invented the computer and authored these schemes to show how a material operation could be shown to be a contradiction. This is pure sophistry. IF program A (the halting program) were defined as such and had to function (as is claimed, to analyze another program) then its operation, its ability to function and analyze what another program would do IF that other program were to run, it could only analyze that other program as per its structure or architecture as to whether it would output halt or continue on given a particular input. However, in all of these schemes, that is glaringly contradicted. That the reverser program was defined as it was, means that it could not be analyzed by program A. By definition, the reverser program requires an input which can only be the output of program A. Yet the reverser program is not inclined by means of its structure alone to either halt or continue on absent an output from program A to be its input. So the entire scenario fails and proves absolutely nothing but the intended deception the presented scheme. If the reverser program requires an output from program A as an input, and the reverser program cannot run for there is no output of program A to be its input so that it has something for which to do the opposite, there is no means for program A to find either halt or continue on. Also, consider, if you ignore that above for the sake of my following point, the reverser program can only act “after the fact” of the output of program A, again, that output providing the reverser program’s input. This points to the fact that program A did its job and was not wrong, but that its output was corrupted by the addition of a program which reversed the output of its analysis. This would be akin to the arithmetic of adding 2 + 2 and having it equal 4 but then adding an additional value to the 4 and claiming that the arithmetic cannot be correct. Program A is thus NOT found to be wrong but that the reverser program, a meaningless function in the scheme was added quite literally to corrupt. The entire analogy is a fraud.
Go back to Quine’s ridiculous liar paradox, apparently so admired by Turing and Goedell. In it, i.e., “this statement is false”, the term “statement” is the subject noun, but also a set definition, in this case with no members, i.e., there is no reference object, forcing the listener to understand it as self-referencing. Were it, “this statement, that the sky is green, is false”, it would be logical and legitimate. But statement in this case is not a noun like rock or rabbit where the meaning is “self-contained” so to speak. If a researcher were to state to his underling absent any prior utterance, “use that definition” but without any reference to any particular definition, his response would be, “what definition?” Quine’s paradox was piffle and not a paradox at all. It is like stating that “your idea is too heavy”. It is meaningless. Yet one purported to be so brilliant such as Turing or even Goedell admired it immensely, as I understand it. Doesn’t compute for me. Quine’s liar paradox violates the law of non-contradiction and has no semantic value whatsoever. If one were to claim that it does, he would be then stating in extension of his defense of it that there can be no set theory or set definitions of any meaning and turn that particular field of study on its head. It just makes no sense. Most, though not all, self-referencing statements are meaningless.
As to my comment on Turing having promised not to introduce into his field any contradictions, I somehow got my critique of the videos on Goedell with Turing. Sorry about that.
So, what do you think?
@@jamestagge3429
it seems you think the reverser program can’t run because program A can’t analyze it.
I don’t see why it can’t, plenty of irl examples of programs being able to analyze itself exist, plus we define A to be able to take in any program.
you seem to think that since the reverser program adds extra code to program A, that program A is not wrong, but the reverser program.
the problem with that idea is that program A is in the reverser program to begin with.
imagine someone, Hank, claims to be able to answer every yes or no question asked to him with “yes” or “no”, and he will always be correct, aka be able to see the future.
To disprove his claim, i ask him “will i ask you another question?”. regardless of if he says yes or no, i simply do the opposite of what he claims.
there’s nothing paradoxical about my actions specifically. Hank + me is essentially the reverser program in this scenario. the reverser program is a paradox, that doesn’t mean Hank isn’t the problem.
Since I found at least 1 question i can ask Hank, and have him always be wrong, that automatically disproves his claim of answering every question correctly.
as for the whole liar paradox debunk, while i do agree with you, i don’t see its relevance to this problem (i misspoke on a previous comment).
if A thinks reverser will halt, it will loop, if A thinks reverser will loop, it will halt. that’s effectively the proof.
again, i recommend watching udiprod’s video on it, there’s also a link in its description containing several faq’s about it
I love your animations. Teach me pleaseee
Could you solve the halting problem as long as you don't feed it a logical paradox?
Yes, you can. But it cannot work for all programs (or might itself get stuck forever when it is attempting to solve for them). There is little use to such a program. Of course it's better than nothing for cases when it can say "it halts", or "it loops forever". But you don't even know if itself will ever halt. It's not reliable enough.
Great video, thank you!
This could be dumb, but, can't you just check if the program gave a output (meaning it ended/returned), or if it executed the same code over and over again? Wouldn't that solve the halting problem? If it returned, then it halted, if it did the same thing for a bit, it looped (I'm not saying check if the vars are the same thou, what if it was finding primes?).
Fun. Well just use an answer with a given time
add more to the oracle, make it have a different answer like "no"
Love your works. Just change major to cs, this helps alot!
If inside that loop i am not doing anything to indentier which keeps the condition true, then it will be infinite loop.
so dont write programs which have other programs as input and create the oracle which could be used for everything else?
This seems as if a judge in a court is going to kill himself if the suspect is innocent. I don't understand why such a problem should be solved like this? why not analyze the code instead and just predict if it halts or not.
This lecture has a big Halting Problem
the real problem is
wtf does it means "it halts?"
A program halts if it stops and returns an answer to a problem(as opposed to running forever without finding one).
You would get a stack overflow and halt ;D
Mindblowed.
Whilst I completely accept the validity of Turing's proof, I still can't help wondering how I've been able to write programs for the last 40 years which don't get stuck in loops (after suitable debugging, of course).
Boah this channel is amazing, you have an incredible ability to explain things clearly while avoiding oversimplification. I'm sure that if you keep on going you will eventually get the number of suscribers you deserve.
awesome dude
very good
did anyone else notice Oolong from Dragon Ball?
Thank God I finally passed my NP test on my 3rd attempt with the help of Mr DAVID, I used his preparation tips. just 3 days of working with him and I passed. I was referred to him by a friend before my exams. Please friends I recommend you to mr DAVID. The man has the key to getting your exam.
I will recommend working with him, get his infos from my channel
I don't think your diagonalization technique proofed that agent smith doesn't exist. I think what you proved is that an uncountable infinite number of programs exist.
Why are we giving Smith to Smith? We assumed that Oracle was the program which could predict the halt. Shouldn't we give Smith to Oracle and not smith to smith!!
cantor's diagonal argument is contested by some mathematicians
the problem is, that neigther the human can solve the problem, if also limited to a binary awnser.
as long as the oracle doesnt say anything she will be always right becaus its then 50/50 if loop or halt and 50/50 if me smith halt or loop
I still don't get it.
loveeee it (cs student)