Turing & The Halting Problem - Computerphile
ฝัง
- เผยแพร่เมื่อ 20 ส.ค. 2014
- Alan Turing almost accidentally created the blueprint for the modern day digital computer. Here Mark Jago takes us through The Halting Problem.
Turing Machines Explained: • Turing Machines Explai...
Busy Beaver: • Busy Beaver Turing Mac...
VR Simulator: • The (pink) VR Simulato...
What on Earth is Recursion?: • What on Earth is Recur...
Thanks to Assistant Professor Mark Jago of the University of Nottingham.
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
Deepest V neck of all time.
And potentially the worst tupé ever :P
+CatnamedMittens “Michael Bialas”
limit x → ∞ : V neck = 11
Sgt Jupiter I don't know what this means.
+Sgt Jupiter true, but I think you were a bit off, V neck = 12, rounded up rather than down
+CatnamedMittens (Michael Bialas) wtf this isnt a thorin video
I think some people who aren't understanding the problem. The problem isn't "Can I write a program that will halt every time I run it?" or "Can I determine if my specific program X comes to a halt?" (trivial examples are easy to come by). The question people were considering at the time was, "If we could create Turing machines (you can read "computer" for "Turing Machine" in most senses) which accept an input and give an output, will they be able to solve any problem put them, or will there be problems which the machine will not be able to solve?" It needs to be understood that if your hypothesis is that "ALL problems given to the Turing Machine can be solved by the Turing Machine", then to disprove this hypothesis, you only have to come up with ONE counterexample. To demonstrate that there are SOME problems that a Turing Machine will not be able to solve, he created the halting problem. Somewhat trivial examples are being used to demonstrate that a contradiction occurs and the program would never halt (and therefore never return an answer to the problem), but the halting problem is a specific problem that cannot be solved. Basically, the point is that for the halting problem, for any given halting program of any complexity, an input can always be devised such that you can cause a halting program to eat itself and go into an infinite loop. As you only need one counter-example to prove that a Turing Machine cannot solve ALL problems, this is considered a proof that there are limitations to what can be proven in any formalized system, such as a Turing Machine, or as with Gödel's Theorem, arithmetic with natural numbers.
Many thanks!
Thanks. I finally understand it
Nicely put.
Why is it specific to halting? Can't one use the same trick on say return or output value? "Oracle said I'll return x. So I'll return x+1". What's so specially about "halting"?
thank you
I did a depth-first search on this page, it returned his V-neck.
What's also interesting is if you could build an "oracle" (ie a machine that solves the halting problem), you could use it to immediately solve many unsolved mathematical problems, such as the Goldbach conjecture or the Twin Prime conjecture. Simply make a program that starts looping integers and halts if it finds an integer where the conjecture doesn't hold. Normally doing this would be useless since you'd have to run it forever, but if you had an oracle you could simply input into the oracle and it'd immediately tell you if it ever halted and if it did, conjecture is false; otherwise it's true.
Clever! Thank you for sharing!
Incredibly put!
Would it need to be "immediate"? What if it took 1 mllion years to run?
Nice! Yes for Goldbach's, but not for twin primes. You can't write a program that checks if integer has no twin primes after it without checking all primes bigger than it so it will loop forever whether twin prime conjecture is true or not.
@@rupen42 no this isn’t a machine you can actual use or build the same way you could a TM. In essence, oracle machines provide a way of comparing harder problems to each to see if they are in the same class. While this machine could “solve” the halting problem for Turing Machines, there now introduces a halting problem for Oracle Machines which is basically just as hard as the regular halting problem if not “harder”
2:38 when he said "Think about your computer running", my network froze and started buffering the video!! Thought it was some kind of joke!! Computerphile never fails to make me smirk
I think there's a little misunderstanding here, the Halting problem asks if there can be ONE GENERAL algorithm that can ALWAYS decide if a program A (whatever it may be), given an input B (whatever it ma be), will terminate or not. Turing, and this demonstration, show that such an algorithm cannot exist, because there is at least ONE CASE when such a program would not give you any answer. In other words: such an algorithm cannot exist because there is one particular case that we can make up when it does not work, and that case we can make up is not a logical fallacy.
On a closing note: there are a lot of comments about Zeno's paradox. Zeno's paradox is not really a paradox, in the sense that we can solve it (not by simply observe of the phenomenon). We can logically demonstrate that an infinite sum of numbers can give you a finite answer.
Best explanation! yes, the whole point people, it to show that it cannot exist, since there is going to be at least one case where it does not work properly, meaning it's not perfect and cannot detect HALT. Which means no machine can exist that does it.
Thank you so much for explaining this! I couldn't figure out what the purpose of H+ was, but in that context it makes much more sense.
Turing's argument is bollocks and doesnt prove anything.
Nope because he creates a contradiction in the first place in order to prove something. What kind of proof is that?
But you see that the contradictory machine itself is bogus? You can't really determine the 2 outputs. Looping forever and stopping at some point in the future are not different. Because the stopping could take place in billions of years. If you fed the program into it, you would never be able to determine whether it loops or stops.
I love how there's tea and cups behind him :D
What would happen if pinocchio said: My nose will grow
Gregory Reis yes
+wingsandstache It would not grow because he was telling the truth.
***** You got it right.
***** Then riddle me this, if a bat and a ball cost $1.10 and the bat is one dollar more than the ball, how much does the ball cost?
Right, then if 5 machines make 5 things in 5 min, how long would it take 100 machines to make 100 things?
What if it simultaneously halts and doesn't halt until it is observed?
i see what you did there ...... but this is no quantum computer
Oh for Christ's sake Schrodinger, get off of youtube.
HumanRights4Everyone pilot wave interpretation FTW!
Schrodingers computer.
Then you train a semi-existent cat to go in and repair it.
I have noticed, as both a computer scientist and amateur mathematician, that logical systems seem to break down quite readily when we allow self reference. Case in point, the Incompleteness theorem
Same with sets
When someone asks whether h+ halts or not:
Well yes, but actually, no.
But also actually no.
nes? or yo?
The 3rd layer of H+ has no input so the programm cant run
After listening to this, my brain halted :P
H+ instead of H'. I'm concerned
*>furry weaboo*
When H+ is fed back in (to the H+) as the program to which we give input H+, there aren't enough inputs (for that H+) as it needs two inputs to give the answer (halting or not halting) and its only receiving one - previously called i.
I asked exactly the same thing, it would be great if someone addressed this issue.
I'm also not sure I really understand how we're proving anything either. The paradox described feels like it implies that that having this specific input ran through the machine would result in looping, but we can't know if that would even be the case? The question was never about whether H+ could exist but whether H could exist. Is it because H is a product of H+ that it implies failure? I don't think it is valid to say 'your machine with 100% success rate in deducing if carrots are peeled or not is foiled because I added extra machines at the end of it that peels the carrot if it is deemed peeled'.
That can easily be solved by turning the input of H and H+ into a single input that describes both the turing machine and its own input to be tested. That way everything is receiving the correct number of inputs and the paradox still happens.
@@Outwardpd You see, the problem is that your peeled-carrots-detector example does not create a paradox, so there's no problem. A proof by contradiction starts out assuming something that you don't know is true (or exists) is (or does). Then it shows that, if that is true, than something completly absurd and impossible would also be true, automatically. Therefore, what you assumed to be true cannot be, in any way, shape or form.
The halting problem assumes a turing machine that solves it exists. Then, using some simple steps, creates a set of inputs that makes it not work. Therefore it couldn't exist, at least not as described. There's no program that can determine if any problem halts, because we just showed how to create a program that wouldn't work, using itself. A contradiction. Contradictions cannot be true, so your assumption can't be either.
Basically if A, then B. If B then not A. Therefore, A can't be true.
@@eac-ox2ly Awesome. Thank you!
Thank you so much for this video! I was starting to worry I wasn't every going to get this and with an assignment deadline dawning I was dreading having to send it in knowing that it was going to be wrong. The way you have described it has made it very clear to me.
As a child I always thought about something someone once told me. They asked me what would happen if Pinocchio said: "this statement is a lie". Would his nose grow?
Pinocchio's nose is a decision machine: given the input (something Pinocchio says), is the statement a lie? Yes, (nose grows), no (nose stays the same).
I had no idea that this conundrum is exactly what Turing saw in the decision problem.
Turing was a goddamn brainy bastard.
George Edwards His nose would not grow. Paradoxes are not lies.
***** if it would not grow then he must have said the truth. The sentence "This statement is a lie" must be true. But then if he said a lie his nose should have grown.
No, his nose only grows when he lies; you can say something that is neither a lie nor a truth. For example, I could say "Zerg is the best race" and, as it would be an opinion, it cannot be true or false.
***** I understand what you mean; please consider that I don't deal with coding or computer programming at all.
I see that the output (the nose growing) depends on the fact what is correct (true) or not. The problem comes when you use the statement as the argument of the statement itself. So when the statement is true, then "This statement is a lie" is true, which means actually the statement is a lie, but if he said a lie, then "This statement is a lie" is not a lie, which means he said the truth... You see? The process never ends.
+BroadcastBro Think I got it... I couldn't understand why they were reversing the output.
But could you possibly explain with the example of H+?
Because if you feed H+ into itself, well H+ cannot solve H+ right? Which makes it a No, which halts the machine.
So that stops it. Which means H inside H+ was right.
Yes exactly. He is purposefully doing something to reach a contradiction, and that's fine. Why?
Think of it like this. We want to prove H does not exist, but we're having a hard time doing that, so we assume it DOES exist. Using H, it is very easy and possible to construct H+ as they said in the video. So far we know, if H exists, then H+ exists. Agree? Continue reading if you do.
Now using H+ we arrived at the contradiction, showing that H+ cannot exist. But how is that if we showed how to make H+ using H in a valid logical way? That must mean our original assumption was incorrect, in that H can indeed not exist.
Hope that made things clearer.
wow thank you
You just repeated what he said in the video.
@@kanekeylewer5704 because some people have problem understanding what proof by contradiction means
@@sayanghosh6996 gang gang you amazing
that's a great explanation, thanks!
Turing is a true genius. I read a bit about him in Simon Singh's Code Books. I hope the movie with Benedict Cumberbatch will represent him in a good way.
Can't remember the last time i was confused this much.But your explanation is better than the other guys so cheers!
I’d just like to say: The dramatic close-up when you say “it’s a paradox.”? Very Nice
It's the little details
*****:
1. Regarding the multiple simultaneous clips at the end, have you though of using a black 50% alpha mask to subdue the clips whose audio is muted? It might increase the visual appeal of those clips sections.
2. What are the applications that you use to create the phosphor green animations? I don't care so much about the color, of course, but the animations are quite well done and I'm curious about the tools.
Think of H+ as a program. It's a program that takes _any_ program as input, determines if that program halts, and then gives an output in the form of halting (if the input loops forever), or looping forever (if the input halts). In order for H+ to exist, then it must also be able to take H+ as an input, determine if H+ halts or not, and output accordingly. Remember we must assume that H+ is solvable, and therefore must output either by halting or looping forever. So let's say that H+ halts. If we give H+ as input to H+, the machine determines that it halts, and then loops forever. Vice versa applies too, so let's say H+ loops forever. If we give H+ as input to H+, the machine determines that it loops forever and then halts. This is the contradiction - the machine gives contradictory outputs for itself.
This contradiction means that the assumption was wrong, meaning that there _cannot_ possibly exist such a program that can take _any_ program as input and then determine whether or not it halts.
I cant seem to understand the part "If we give H+ ad input to H+, the machine determines that it halts, and then loops forever."
Why does it loop on forever after determining that it holds?
Why doesnt it just determine that it halts and then halts?
@@paulvorderegger1522 It loops forever because that's what H+ has been designed to do. If you feed it a program that halts, then it will loop forever. If it did anything else, then it wouldn't be H+. If you gave H+ an input program that halts, and H+ cannot loop forever, then this would also imply that H+ can't exist.
@@gordonfreeman5958 Ok I finally understood this after seeing the following pseudo code:
def thisFunction ( ):
if halts(thisFunction):
loop_forever( );
This was a brilliant explanation of the halting problem! Thanks!
I enjoyed this video. I appreciated the deliberate pacing of your explanation.
Turing didn't invent a computer program to demonstrate that a particular something was impossible, he invented the entire idea of computers and programs for the purpose of showing that this something was impossible. Think about that for a moment.
What makes the 'machine looping forever when reaching a yes' upgrade count as being relevant to the original question?
Is it because the machine is suppose to account for all programs in a form of universal sets, including the added upgrade?
+Roman
He's proved that the existence of H will lead to paradoxes, so therefore H can't exist.
He proves asking that type of question about anything is absurd. look up Proof By Contradiction. He says that if it WERE possible, something else would happen that we know to be false. and since the rest of his arguments are valid, the premise must be absurd.
fk u all
Thanks, big help! I was confused about this topic for my discrete math class, you saved me.
I was waiting for a video about this!
I like the idea of a machine with a billion binary inputs and tons of layers hidden inside and a single binary output.
***** FYI: This almost 1 year old video misses links to promised videos at the end.
Florian H. thanks for the spot - fixed now >Sean
+Computerphile You fixed the halting problem, add links !
Wouldn't that just be a superposition of halting and non halting? so your answer is both?
I had to watch this video twice trying to understand it. Great one!
I can design a program to determine whether a closed loop program (I.e. one that doesn't have any inputs) repeats forever. It executes that program and examines the memory allocated to it, and as soon as it sees a repetition in the memory, it terminates that program and outputs yes, that program repeats forever. It avoids the halting problem because it requires an input, rendering it incompatible as an input.
I've always sort of understood this as a more general proof that any algorithm which analyzes algorithms can never be fully generalizable. If it could, then it could analyze itself and respond to the result by contradicting that result.
When feeding (H+, H+) into H, we get "Does H+ halt on input H+?" But H+ needs 2 inputs, not just 1, so what happens?
That confused me too, because the video glosses over technicalities. But I realised it looks like this:
bool h(alg, param) {
if(halt(alg, param)) {
return true;
} else {
return false;
}
}
void h_plus(input) {
if (h(input, input)) {
while(true) ;
} else {
return;
}
}
i.e. h_plus() has a single input which it duplicates when it calls h().
@@TheCriticsAreRaving but what paramilitaries will the program have ?
If h processes h+ which has different parameters than the h+ which is processing wouldn't that make it so that h+es are different thus they wouldn't do the same thing . so if it loops it isn't a contradiction anymore because it is processing different parameters
@@sababugs1125 no there is no problem here
h_plus simply uses h as black box.
h should work for all inputs including once tha have the first and second argument the same.
@@sababugs1125 i mean in his algorithm
when you pass h_plus(h_plus)
you get:
h_plus(h_plus)=>h(p_plus,h_plus)=>h_plus(h_plus) => ...
basically its an infinite loop, but tho you have no idea what h does,
as h might "look into the future"
without actually running h_plus on h_plus return some answer.
but then no matter what h will say it is always wrong.
Amazingly well done! Bravo *claps like a gentlemen*
A minor problem, the description actually given won't create the paradox. H+ needs a front end as well as a back end. What you have in your example is that you are feeding H+(H+) to H and asking if it halts and finding that H+(H+(H+)) exhibits opposite behavior, which may be unusual bot not impossible.the fron end needs to do a small conversion so that x(y) is changed to x(y(y)). This is actually an important consideration. Languages which cannot expand their inputs are always decidable. But expanding the inputs allows the creation of self-denying statements.
I have a question!!
When I took Philosophy courses years ago, I was taught that adding self-assumed premises to the given question is not allowed. I have watched a few explanatory videos regarding Halting Problem on TH-cam, and all of them involves adding extra logic gates or machine components on the original "machine H." Isn't this kind of like adding self-assumed premise to the original question, since the original questions is about whether Machine H will halt, not Machine H+?
This is because the proof is very simplified. The original proof (not going into details) was like: i have an algorithm h wich will decide whether an algorithm x will stop. Then we put ALL possible Algorithms combined with all possible input in a numbered map (each column/row has a unique number). You can now choose algorithms and inputs (e.g. algorithm number 4 with the input 10). We can some really crazy math with an alter every row, EVERY row from 0 to infinity is still unique, but now you have a new row with instructions not found in the table. You can define this row as the algorithm h+ (uses h) (actually the algorithm used is different from h+, but for a simple explanation you have to change it) and if you feed the algorithm with an input z (z is the number for the input), it will print out a different result that the algorithm in the row z for the input z. Since you have this cool table with every possible algorithm, you can find the algorithm h+ with a number x. But you proved that h+ will give you a different result than algorithm z for the input z and input x must exist. So h+ must print a different result for the input x than algorithm x (which is h+) for the input x? This is a contradiction! But this case MUST (this is the big point) exist if our assumption is true.
the problem is that the proof is extremely fundamental and very, very important, but also very hard to explain or understand. I altered the proof heavily. To explain it in a simple way you have to make a sacrifice, and you spotted a consequence of one sacrifice.
LeanderK Your explanation makes much more sense than the video to me, thank you.
However, in the video I can't quite grasp why the loop and halt extra boxes should be added to the outputs, because if that's the case wouldn't the h+ that is being used as an input not halt at all?
And if loop is added when output is yes, then halt is added when output is no, then why bother feeding h+ into itself? Pretty much all machine as an input will get the contradiction because we set the h+ like so.
I don't really understand philosophy and proper logic, so please enlighten me :D
Dennis Samuel "All algorithms" would by definition include a modified original algorithm. A modified (as described in the proof) algorithm is part of the set that includes all algorithms.
Gran Cero No because the problem is respect to ALL machines. adding stuff onto an existing machine only creates a new machine which also has to obey the assumption proposed.
Well, I didn't understood the proof for the same reason Gran said...
I thought I had addressed this before but I could find my response. The Halting problem paradox (at least as described here) is wrong.
It's impossible for H+ to self reference since it requires 2 inputs (the 2nd being in input to the machine to test) but this requires infinite recursion to set up to self reference even if you fix H+ to take multiple required inputs as a series (or by any other method) into the 2nd slot.
burstofsanity late to the party, but fwiw you don’t need this problematic self-reference: the “computer” input I.e. the “top” input, is just a representation of the program, like its source code (or Gödel number), not its state with respect to a given input.
I'd like to hear more of this guy!
Good to see a video about Alan Turing
I think it is a little confusing when you feed H+ to itself, H+ should be fed to H.
H is the machine that you assumed will solve the problem. If you end up in a paradox on your assumption then the assumption will be falsified.
By feeding H+ to H+ nothing will happen to the original assumption, because you basically are not touching H.
If you feed H+ to H, then if H+ halts, H will say it doesn't and if H+ doesn't halt, H will say it does. Here is the contradiction so the assumption is incorrect.
H is part of H+
It’s the same thing you are feeding it into yourself
The problem isn't really feeding H+ into H+, but there is a problem with the explanation. I don't know how exactly Turing wrote his proof since I didn't read his paper, but the way every single youtube channel is explaining it is simply wrong.
The input to H+ is a tuple (P: Program, i: InputToProgramP). The whole thing is the input
So when you feed H+ an input (P=H+, i=H+), you are basically asking "does program H+ halt when it receives input H+?". The problem is, the input to H+ is a pair (P, i). So you can't just feed it P, you are missing i. It's like you are feeding it (P=H+, i=).
To fix that, you'd have to feed H+ an input (P=H+, i=(P=H+, i=H+)). But you end up with the same issue. So you'd change the input to be (P=H+, i=(P=H+, i=(P=H+, i=H+))) to try to fix it, and so on, forever. You can't ever feed it itself.
@@rafaelclpTHANK YOU, I WAS THINKING THE EXACT SAME.
You formullated that pretty damn well and I fully agree with you.
Im just wondering wether or not you can still prove it by induction, but i dont think there is even a base case, so not sure about that
This comment section needs to take more math classes.
dork I understand all of this more pristinely than most people who have a degree in physics. I barely use the language of math.
Your opinion doesn't matter.
+dork "More" is a comparative term. More than zero? More than one? Five? Ten? Twenty?
@@Agent1W he meant "more meth"..
@@DrBrainTickler Living example of the dunning-kruger effect.
What does it have to do with math?
Thank You So much for this great explanation.
Turing's 'decision problem' is related to Godel's problem of 'undecidable', in which an algorithm of finite axioms leads to undecidable conclusion, while an algorithm of infinite axioms leads to a decidable conclusion.
+Naimul Haq Don't forget that Turing spent time at Princeton. Although he worked with Church and Von Neumann, he knew Kurt Godel and if I recall Andrew Hodges bio they had some discussions and were well aware of each others work.
Peter Walker
I am sure they were. Einstein took great interest in Godel's work.
It reminds me of the book "Goedel, Escher, Bach".
i watched 2 videos so far , inclusing this , still dont understand the halting problem because , why would you put and loop when it give a yes answer ? it it halts let it just halts and its done ? why forcing it loop ?
looping forever is the opposite of halting, meaning it doesn't halt
I can't remember, but I think we used an induction proof by contradiction on a test once for this problem. It's been a minute but I loved studying formal languages in college.
this was brilliant. helped me. thanks dude
Wouldn't this imply that it is impossible to fully simulate a universe? Because you have to use a computer to simulate a computer created in that universe, and then simulate if it will halt or not. So we are back where we began.
It's not necessary to simulate it in real time.
You don't need to simulate if it will halt or not. You just need to simulate the next step in accordance with the next step of the universe. It doesn't matter if it would never stop. You're running the program anyway.
You dont have to simulate if it will halt or not because the simulation will NEVER have an infinite amount of time.
Pardon me for so saying, but it appears that: This entire presentation (and argument) is itself a general algorithm that in fact does decide a whether a program will always terminate or not. This presentation demonstrates an answer to the presented dilemma. Given the recursive, self-referential nature of the proof presented, I think it only fair to consider the proof itself as part of an algorithm that does in fact solve the issue at hand, thus this ONE CASE presented actually shows that there is an answer. After all, you've given the answer in the form of a proof, no less!
If you consider your own thoughts as part of the algorithm inside the "machine" then you are the solution, since you can ALWAYS decide if a program will terminate (by recognizing an apparent paradox).
Thoughts on this?
@@ZandarKoad I agree, and cannot find a proper example/explanation anywhere.
"The Halting Problem" is a problem specifically for Turing Machines, or any other equivalent formal system (first order logic, the lamda calculus, etc.). Once you step outside those systems, "The Halting Problem" is not defined.
For people in comment that want an example of a really simple algorithm yet very hard to tell if it will finish or not is Collatz conjecture.
It goes like given an input x if it is odd triple it and add 1, and if it is even, half it. Keep doing it until you reach 1.
Fun fact is that there is no way to tell how many steps it will take for any X without carrying out the algorithm.
NOTE this has nothing to do with the halting problem. This is just a fun contrast to other common algorithms which we can easily tell if they would halt just by inspecting them.
in the final example we are feeding H+[1] the input "H+[2] evaluating input [H+3]", however, h+ needs both the program and it's input to determine if it's going to halt.
what is the input into H+[3]?
there's a minor mistake in the presentation: the definition of H+ was "take inputs a program P and a set of inputs I. if H(p,i) then loop forever, otherwise halt". This simply doesn't work, you can't apply H+ to H+ and H+, since you're implying that H+ both takes 2 inputs and 1 input.
The correct definition for H+ is
"take a set of inputs i. if H(H+,i) then loop forever, otherwise halt"
This way, H+ is a one-argument function (just the i), and you can apply H+ to itself to get the required contradictions.
Thank you. It makes perfect sense now. I couldn't understand how H+ could take an input of just itself.
Either I didn't get the Halting Problem in university or Mark describes it incorrectly. He says at 03:35 "...whether a given machine with a given input will halt or not." Shouldn't it be "any machine with any input", any as in an arbitrary? Because surely you can built a machine that can determine the Halting Problem for "some" machine with "some" input, but the point is you can't do it for every/any/arbitrary machine. Or maybe I just got lost in translation? (I'm not a native english speaker)
His description is ok because he doesn't claim you that this program is in some kind of set, he's saying "given program" which actually means that this program could be any program. The same goes with inputs
This video helped me pass an exam :P Thanks!
I think this explanation is wrong because H+ with two H+' as imput is different from H+ with one or zero H+' as imput so the second one can halt while the first can loop and there wouldn't be any paradox. Correct me if I'm wrong.
Error: H+ cannot be converted to type Input for parameter 'i' at line 4:40.
H+ is a program, not a program and input pair, which is the input required for H+ p.
I saw a comment who fixed that error by letting H+ have a single input P and send to H and of course do the if halt loop and if loop halt at the end. When it is done like this, if you give H+ the single input H+ you'll find that if H+ halts on H+, H will have determined H+ shouldn't have halted in the process, and if H+ doesn't halt on H+, H will have determined H+ should halt on H+ during that process.
The comment didn't bring up this, but I realize that not all programs can accept themselves as inputs. I imagine we can also extend H such that no will be the answer if the input is not allowed (because it should halt with an error)
but maybe there can be a program that solves the halting problem for all programs except itself !
It's not for itself, h solves the halting problem not h+.
But H+ is constructed using H. Maybe let me refine Kot_Robot's comment:
Maybe there can be a Turing machine S that solves the halting problem for all programs except those that reference a Turing machine capable of solving the halting problem to the extend in which S itself is capable of solving the halting problem.
I intuitively think self-reference is key to both the logical contradiction ( like the liar's paradox aka. "this statement is false" ) as well as to the way to solve it ( think through the Turing machine S I constructed up there ).
@@greencoder1594 Sorry to disappoint you, but that is not possible. This is a really simplified version of the proof and i understand that it may hold this implication if you aren´t invested in theoretical computer science (formally it´s usually prooven via diagonalization, which is much less intuitive). It actually turns out that even the BTHP is undecidable (blank tape halting problem -> given a turing machine M, does M halt on an empty input?).
Great video, easily really helped me understand. Also, cute teacups.
Thanks for this explanation. Just the use of the H+ terminology makes this much clearer than many variants of this I've seen. Personally, I find the computer graphics redundant, compared to the simple diagram on printout paper. Impressive teaching skill. Also, making explicit that 2 copies of H+ are fed in 'in parallel' allows the analogy with H to be made explicitly.
just like the pinocchio problem: what if he says: my nose will grow.
his nose will explode
Nothing happens. Pinnochio's statement is a prediction, not a statement of truth, he is wrong, not a liar.
If he says My nose will grow, will result in his nose growing. Why? Because the statement will only become a true statement when his knows actually starts growing. Until then, the statement is a lie, since it's true that his nose will grow but since the statement is true, he is thereby lying about his nose growing, because it wouldn't grow. Therefore, it grows. It's not impossible to solve a paradox such as this, one just has to consider the fact that the output does not alter the inputs. Once you have the output, that's it. The rest of the statement is left behind. Just like Pinocchio, his statement only becomes true when his nose starts growing, but by then it's too late. In the moment that he'd said it, it was a lie.
+Mourad Qqch But if his nose explodes, Geppetto could just whittle out a new one and graft it in Pinocchio's face, and the new nose might not even retain its previous function.
This really got me thinking.
I'm not clear on how the behavior of H+ shows anything about the behavior of H. The two machines are not the same, so why would you expect the same (i.e. correct) output. By this logic I can ask whether it is possible to build a vehicle that can move down a road. Suppose there is such a vehicle, let's call it CAR. CAR can't possibly exist because I can attach a module called NOGAS that removes its motive force, so it can't go down the road. Since CAR+ can't go down the road, no such vehicle can exist. QED.
If you're going to add parts that break things, why pretend that you're still dealing with the same program?
+Jason Patterson Yep there is no such vehicle CAR+, that can drive because CAR+ = CAR + NOGAS. There is no fuel powered car that can drive without fuel.
The missing part from your example is a contradiction. CAR+ can't go down the road while CAR can, and that's it. If you somehow reached a contradiction using CAR+, then indeed CAR could not exist. Both CAR and CAR+ can exist here fine.
What happened in the proof in the video is that using H, he constructed H+, and showed that H+ is impossible to exist. So essentially we've arrived at two conclusions at the same time, H+ can exist using H, but at the same time H+ can't exist from the way he described in the video. That's a contradiction, so the assumption that H exists was wrong. Hope that made things clearer.
@@Kalernor Does not make sense "using H, he constructed H+, and showed that H+". Meaning it is possible to put anything as an addition to H, and then say:"look, just because I added some impossible things to H+ it means that H, my base, is also impossible.".
very good explanation in a historical context
The flavor of Turing's argument reminds me Gödel's Incompleteness theorem. Both seem to be taking a system of axioms and breaking them, proving they're "too good" to be complete and solve every problem. Is there a relationship there?
Apparently there is. After doing some reading I've come to the understanding that Turing's work on halting was an extension of Godel's work on first-order logic. Apparently lambda calculus was invented for the same reason. Lisp is based on lambda calculus, right? And basically every other language is based on Turing machines?
wait, from the introduction it looked like P and I are different in nature, like different data types, but then you feed H+ on both? not clear
'p' never changes in type, it's always some kind of program. However, 'i' the input, can change. eg you make a program p that multiplies a number you give it by 2, then you test it with the h machine, and you can check whether p will halt or not given input of type integer, then string, or even of input program or 'p' (feed it some Java or something eh?) you see what I'm getting at here?
I appreciate what you are saying but your answer doesn't solve the formal problem I am posing. If you want to feed H+ as the 'p' to H+ you need to formulate it correctly as a program/machine that takes an input. Now, H+ must be viewed as a machine that takes a pair (p, i) as input. So the final test would be with H+ and (p,i) fed into H+.
what's the difference between a formal problem and an informal one? ^_^ Anyway, when you approach this theoretical machine thinking like that, you quickly end up with infinite recursion, can you see how? besides it defeats the simplicity of the system to start worrying about data types, when you get onto larger programs, you expect this machine to be formatted to take all 1000 of the programs variables and inputs as the 'i'? if anything like this could ever be made, the team behind it would be smart enough to ensure it only ever needed two inputs, P and i, because there's zero upside to any other approach, wouldn't you agree?
Well formally, everything is just numbers. There is a 1:1 mapping between programs and numbers, for example by taking the program's code in binary and reading out the whole sequence as a single number. So it's perfectly valid to use the same number as both a program and as an input to a program.
I feel like I finally began to understand some of these issues after spending way too much time on it. Basically the idea is that whether the input type is valid or not the program still runs with that input. For example, if you built a rudimentary calculator and then you feed it a string input, if your program isn't able to handle that string input it can either throw and error and stop (halt) or it can loop infinitely due to invalid input (loop forever). So the input types don't necessarily matter because a program will still result one of those two actions, and when you're feeding a program/algorithm as the input itself to be analyzed by the program it will still do either of those two actions, regardless of whether it is a valid type.
I was lost already at 1:14 when he said: "can we automatically test whether the premises entail conclusion"
I would appreciate any comments on the following thoughts...
To my current understanding Godel established a more general theorem in his famous incompleteness theorem. Given a set of transformation rules (ie. a program specification) and a set of axioms (ie. program input) he showed that it's not possible to determine, in a general case, if such program will reach a certain state S.
Can the halting problem be reduced to Godels by saying the state S of interest is the halt state?
To further clarify, I define a "program" as a sequence of states, given it's initial state, which is described by the transformation rules of the program (state transitions). So program is a living entity.
4:42 but doesnt H+ expect two inputs? the description of H+ is "given the following input, will this code half or not" so when we give H+ itself as the "input" input, we need to actually give it something else, because the H+ in the "code" input expects two inputs??
i hope this makes sense
Question
H+ named 0
H+ named 1
H+ named 2
0 runs, checking whether 1 will halt or not halt if 1 is given 2.
Wouldn't there be an error, since 1 is only being given one input, rather than two which it is designed to take, and 2 is not being given any inputs at all?
***** So
H++ named 0
H++ named 1
Virtual H++ named 2
Virtual H++ named 3
Virtual H+ named 4
0 runs, taking 1. 4 takes 2 and 3 as inputs. 2 runs with 3 as input. 3 still lacks the one input it needs to run. Wouldn't there still be an error?
I'm still confused. What alternative is there to thinking of them as something besides different machines?
*****
You're missing the point, because the paradox would still be encountered within your H+ machine. It doesn't matter at all what the inputs are - the paradox will still arise.
Or do you actually think you've figured out something in a youtube comment that mathematicians have missed for the better part of a century?
No, I'm just confused. I don't think that the proof is wrong or that I'm particularly more intelligent than anyone else, quite the opposite, I don't understand the explanation, and am attempting to identify where my misunderstanding is coming from.
Is it necessary to take such an aggressive stance?
Was actually responding to SBareSSomErMig and eir fairly flippant 'That's a little mistake in this video' comment. The video's fine, eir logic is faulty. You're good for asking questions. :) The system is designed so that the entire machine is fed back into itself as both inputs, not just one. So the system has the correct initial inputs, but will still result in a paradox as explained in the video.
you should feed h+ to h not h+ to h+ because h+ is a modified machine to reverse the output real meaning.
Yes exactly. He is purposefully doing something to reach a contradiction, and that's fine. Why?
Think of it like this. We want to prove H does not exist, but we're having a hard time doing that, so we assume it DOES exist. Using H, it is very easy and possible to construct H+ as they said in the video. So far we know, if H exists, then H+ exists. Agree? Continue reading if you do.
Now using H+ we arrived at the contradiction, showing that H+ cannot exist. But how is that if we showed how to make H+ using H in a valid logical way? That must mean our original assumption was incorrect, in that H can indeed not exist.
Hope that made things clearer.
Hmm the idea comes into a bit better focus like that. But why do these machines need two inputs?
@@foreverseethe It takes the machine and the input that the machine would be given. It's possible for a machine to loop forever on one input but halt on another.
In practice a real machine has a finite number of states. So we can just write a program that checks if the machine visits a state that it's been to before (in which case it loops forever).
Though this program can't exist on the same machine since by definition it would need more memory than is available on the machine to keep track of visited machine states.
This problem is like connecting two not gates to each other: the output of the first to the input of the last and the output of the last to the input of the first. The whole halting thing is just a more sophisticated way to put it.
I get the idea here, but it seems to me, once you've added on extra workings to the halt detector, it is no longer the halt detector, and has become a different machine. The example seems a bit off too, pretend this machine works, now we change it, it doesn't work, thus proving something about the world. Logic is a great tool, just the use perhaps in this situation isn't making sense to me.
"Can you build a machine, that can tell you whether or not ANY given machine with ANY given input will eventually halt?"
No you can't, because you can always create a machine, that will never halt. (Overly simplified.)
The key here is the created paradoxon, that if the machine should halt it doesn't and if it doesn't halt, it does.
He tried to simplify the solution, you can actually prove the same thing with no modifications to the H machine.
The idea here is that if such a general purpose halt-detector H exists, then from it we can build the impossible machine H+. Since H+ is impossible, then H cannot possibly exist.
Given H, H+ is the machine that takes as input a set A, and does the following with it: "what is the result of H applied to inputs H+ and A? If yes, then loop forever, otherwise, halt"
now, to show that H+ is indeed an impossible machine, feed H+ to itself (that is, substitute H+ for A in the above sentence)
this gives us "what is the result of H applied to inputs H+ and H+? if yes, then loop forever, otherwise, halt". We'll call this H+(H+)
now, H+(H+) either halts or not. If it does halt, then it didn't loop forever. This means that H applied to inputs H+ and H+ gives us a "no" answer. Wait a minute, from the definition of H, this means that H+(H+) does not halt. This is a contradiction, which means we cannot assume that H+(H+) does halt.
okay, so that doesn't work, this must mean that H+(H+) does not halt, right?
Well, in that case, since H always halts, then H+ must have gotten stuck in the "loop forever" part. But in that case, then H applied to H+ and H+ gives us a "yes" answer. From the definition of H, this means that H+(H+) does halt. We got ourselves a contradiction again.
We exhausted all possibilities of H+(H+) halting or not, and none make any sense. This means that H+ is an impossible machine to begin with. Since the way we modified H to make H+ is completely valid, then H must be impossible.
Ricardo Amendoeira Ah okay, with the modifications, it seemed to me something was wrong, as the add on part would be constantly flip flopping itself, just to fool the H part. Does bring up some interesting thoughts though, for it to work, H would have to be lying... and thinking ahead.
There are 3 machines: H, G and H+
H is the halt detector. The point is to figure out whether it can exist.
G is a machine that loops infinitely if given the input "yes", but not if given the input no. We know that such a machine can exist.
H+ is what you get when you combine them.
If both H and G exist, then H+ must exist as well. This is equivalent to saying that if H+ doesn't exist, then H and G can't both exist. The video shows that H+ doesn't exist, so, as I said, either H or G must be impossible as well. However, we know that G can exist, meaning H (the initial halt detector) can't exist.
The mistake in this video is that the box in the machine asks, does program p with input i halt? However you cannot feed in H+ to this machine because H+ takes 2 inputs instead of 1.
You could fix this by adding a new component to the front of H+ that only takes 1 input and copies it into 2 for the inner machine. Now H+ takes only one input and the argument works just as explained.
Great Explanation!
4:14 This is where the flaw in the logic starts. You stick extra bits on the end of the halting machine, by doing so, no matter what the bits are, this is no longer the halting machine. But you continue to treat it like the halting machine and expect it to function normally. The worst part is that those extra bits are analogous to a "not gate", basically just inverting your answer. This is exactly the same as the "This statement is false" paradox.
You created a new machine that literally inverts it's outputs and then expect it to work like an untampered halting machine and conclude it to be a paradox.
By no means do I think Alan Turing didn't know what he was doing/talking about, but I've never understood this line of reasoning in this specific case.
The reasoning is tricky but fair. The question is “can a perfect halting solver that can solve ANY halting decision problem exist”. This definition includes self-referential machines, so we’re allowed to demand that the machine get the right answer on these cases where it’s inside something else too. “If it’s perfect, then it’s also not perfect” isn’t allowed, so we can deny its existence.
Of course you can say “what about a solver that detects specific unfair combinations and rejects them” but… consider a machine A (a halting pathological machine that we want to reject) and a family of machines FA that all claim to do the same thing as A, but can be as unnecessarily complex as we want. In order to prove that everything in FA does the same thing as A, we have to prove that they halt since A halts which… we can’t do perfectly. So even though the halting paradox seems specific and unfair, it extends very far to the point that we can’t even perfectly compare arbitrary machines.
Why is the transformation from h to h+ valid? Isn't h the one machine that solves the problem?
What would happen if you give h+, h+ inputs to another h machine?
I'm not saying you cannot make h+. I'm asking why can you expect it to solve the same problem that h can. It just sort of feels like attaching a shredder to a printer and saying printers can't exist.
I'm not really program-savvy but I'd like to understand and not just take somebody's word for it...
OK I see what you mean. You're completely right that H+ doesn't do the same thing as H. But it doesn't need to. The idea is, if H is valid, then H+ should also do *something* reasonable. It doesn't matter what that something is, but at the very least it shouldn't result in a living contradiction.
With your printer analogy, imagine if you attached a shredder to a printer and got confetti that is both all black and all white at the same time. It's a contradiction, and you know your shredder can't be responsible. So something must be wrong with the printer.
Ahh that makes more sense to me now. Thank you
could he be more abstract ?!
Star billions of programs all doing different things based on the same logic. abstract is the only way to learn the wide view instead of per program.
Very interesting! Good video.
If you pass H+ to it self, what input does it get? Or would it just loop forever waiting for input?
5:18 Aren't you just asking the wrong question?
"Does the first iteration of H+ Halt?" would be a better one...
Also, doesn't that mean the machine could be the human brain...so...we couldn't do this? Yet...we can?
Also, how does that fact that putting H+ into H+ break means that H normal can't solve it?
actually a human couldn't solve the halting problem because humans are at most turing complete
+lolzomgz1337 I could have sworn I hade a reply to this comment. And I got anotification when +Jahaal Mordeth posted. But my comment isn't here :(
Simon Lindgren
Damn. :(
+lolzomgz1337 This is a vulgarization of a problem that is actually harder to prove than this so you have to give some leeway.
Philippe Carphin Okay, fair enough.
man I love turing machines.
When we did that stuff in uni, man I adored it so much
wish i had someone like you to teach me this stuff >.
+Computerphile At 3:58, Mr. Jago says that the blackbox will output "Yes" if the program halts, but "No" if the program never halts (a.k.a loops forever). But how does the program know that it will loop forever, since with every iterating loop it has the potential to halt?
- An Engineering Physics student, and Physics student in California
It doesn't even matter how such a machine works because it cannot exist. He even says "Don't worry about how it works, just assume it does."
amazing explanation!
My peasant mind needs more or better explanation. Because to me it just sounds like the paradox problem has nothing to do with machine h but you just added the h+ onto it to force a paradox out of it breaking machine h
The point is that H+ is so easy to add, if you had H then you could instantly make H+, but if H+ cannot exist then there's no way H could exist, because if H exists then H+ can easily be made from it.
Like if there were such thing as indestructible bread, I'd easily be able to make a indestructible sandwich by slapping 2 pieces of bread together, but if I can prove that indestructible sandwiches cannot exist, then either sandwiches are not made of two pieces of bread or there's no such thing as indestructible bread.
NoRotation
I still don't quite get it.
Let me explain: There are three parts to this: a detector H, a program to be tested P and an input i.
We assume that H(P(i)) will give a meaningful result.
We then build H+. H+(P(i)) will not necessarily give a meaningful result - when it terminates, you have an answer, and that's great, but before it does, you don't know if that's because it's takes a long time and isn't done yet or because it found the answer and is looping to show it to you. H+ is not a functioning detector - unless you have another detector H that can determine if it is "looping as output" or still evaluating input arguments.
So what about H+(H+) (presumably with some other input just to get it started, so it's actually H+(H+(P(i))))?
H+(P(i)) is the input, and that's fine. It may be a rubbish program, but there's no rule against that. But the "other" H+, the one that actually does the evaluation, is an unfit-for-purpose program, so it won't give us a useful answer.
So what will H(H+(H+(P(i)))) say? It will not be undetermined, it will say "loop infinitely". It looks at the whole thing - and will detect that at least one part of it (either the inner or the outer H+) will loop.
So to me, H+ seems not impossible, just not terribly useful. I can add perfectly valid code to almost any program that would ruin them beyond recognition (trust me), but that doesn't prove that they couldn't exist to begin with.
Snagabott You're not thinking in the ideal setting, this machine takes no time to run, it instantly returns an answer, so you know whether or not it's looping. Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration to show that an essentially functionally identical machine cannot exist.
NoRotation
"Also the point is not that you add code that ruins the functionality of H, but you make a trivial alteration."
It's not trivial at all. The output is radically altered. Output is ultimately what matters, not what happens inside - you can have the most beautifully complex and advanced bit of code in the world, but if you add another bit of code that intercepts and scrambles all output from it, it becomes worthless.
Snagabott Except this doesn't scramble it, it's still completely unambiguous what the output is. Furthermore the algorithm that is suppose to check the programs has not changed except for the output stage, however the alteration to the output demonstrates that the algorithm cannot possibly reach a valid output and therefore the algorithm has failed.
Am i missing something here? So we assume that H solves the halting problem, and we then proceed to show a contradiction by showing that H+ doesn't solve the halting problem when you feed H+ into itself. How does this contradict the assumption that H solves the halting problem. We only showed that a modified version of H, namely H+ doesn't work.
it's not that H+´doesn't solve the problem, H+ doesn't even try to
it's that H, as PART of H+, fails to predict H´+'s result
For any machine H that claims to solve the halting problem, you can create a machine H+ for which it gives the wrong result, thus showing that H doesn't work for any machine
you can imagine H and H+ next to eachother, feed H+/H+ into H first, then into H+
No combinations of the two possible results of each machine give you a logically consistent result - thus there exists no H that can predict a H+
***** Upon further reflection it makes perfect sense to me now, there must have been something in his explanation that just didn't sit right with me at first.
Hey Mike LaValley
I seem to be in your former position. I can't quite wrap my head around his explanation.
H can tell whether any program P will halt or not on any argument I.
H+ does the SAME, it just also does the opposite afterwards.
So he says he’s feeding H+ into itself, why can’t H handle that?:
H is to examine H+(1) and H+(1) figures out another H+(2) system will halt (because the H part of H+(2) said it wouldn’t halt), H+(1) won't halt (again because H+(2) did halt) and H will say no, which is correct.
And vice versa.
but H+(1) and H+(2) are the same machines that get the same input.., if they get different results that means the machines don't work
(which they don't, they can't, there's no such H that works for any machine)
H+ get's the wrong answer because they are faulty, but H isn't.
From the description of H+ it would appear to me that it doesn't have an output at all. If it loops forever then it clearly does't have an output, but if it halts, it halts. From the diagram of the machine Mark drew, it doesn't seem that H+ should give any output when it halts.
Wait. I remember thinking about asking Computerphile about the Busy Beaver like a week ago. Did you read that and did a Turing machine video because of that?
Or did I forget about posting it and this is coincidence? :D
Doesn't this proof just show that the transformation from H to H+ was a bad decision? I mean, theoretically I could use H to test H+ and see if it will halt or not. I don't necessarily have to use H+ to test H+, right?
Can someone please explain this to me?
When proving something by contradiction, you start from an initial assumption (which you want to prove wrong) and then reason upon it until you arrive at a contradiction. Since all the reasoning steps between the assumption and the contradiction are legal (consistent), the only possible explanation for the contradiction is that the assumption was wrong - so the opposite must be true.
The wrong assumption here is "there exists a machine H which solves the halting problem", and we use a "bad decision" (a legal transformation from H to H+ and a legal execution of H+ on itself) to end up with a contradiction. This proves that the opposite is true, so we conclude "there is no machine that solves the halting problem". Sure, running H on input H+ might not lead to a contradiction, but that simply means it's not useful as part of the proof. The goal is to make the "right" bad decisions in order to end up with a contradiction.
If you feed H+ as the program and H+ as that program's input to the normal H machine it will give the wrong answer.
The strategy in the proof is to show that if such a working H machine exists, then we can build a machine H+ that contradicts its own existence. Since you can never build such an H+ machine in any way, then it must be impossible to build the H machine to begin with.
This is not the correct proof, as in the described system it is invalid to give the pair (H+, H+) as input to H+.
Why? Because the second element of this pair is not a valid input to the first element.
There's probably an additional assumption that would make this work, but its missing from the video, which drives people mad in the comments.
+poliklosio
when we give H+ to H, we actually give a blueprint of H+, that specifies how exactly H+ works.
that is, essentially, a bunch of characters, so you can look at it as an input to another machine, regardless of what the characters actually mean
+inon star Yeah, I know that, just not from this video.
+poliklosio All programs can take all inputs. This is a fundamental requirement from a program. If the input is invalid, or it can't process the input, the program either halts or not. But which is it? That's the million dollar question.
+Aman Singh I disagree. A program is not necessarily well defined for all inputs. There is no reason for every program to accept any-length stream of arbitrary bytes. Author of a program is free to describe any preconditions about the inputs to the program. If input data doesn't follow the preconditions, it doesn't make sense to consider behavior of the program in such case.
It's like considering what happens when you divide by 0. The answer is the question itself is incorrectly formulated because division is not defined for this case.
The program doesn't even have to have means to accept the bytes. How do you feed stuff to "Hello world!" program? Assuming it has the means to accept your bytes, of course you can try feed incorrect values to it, but it is not really interesting what happens in such case, as you are deliberately breaking laws of mathematics. The program doesn't even have to check for input correctness in order to be correct itself (although sometimes it may be desirable to do so).
I have to make it clear again that the model you describe IS used in the original proof about the halting problem, its just that the video doesn't say it.
poliklosio Well, this is a video on Theoretical computer science, so it should be assumed, along with many more assumptions. For example, infinite tape of the Turing machine. This is the reason size or format of the input doesn't matter. The state machine of the Turing machine will either halt sometime or not, regardless of the "format" (using multiple tapes for writing any "special character") or size of the input (obviously, infinite tape).
if i'm not misunderstanding it, is one example of a halting feature a bit of software that checks for bugs when developing software?
I'm getting flashback of theory of computation courses. nicely explained.
This comment has nothing to do with the subject matter at hand. But seriously: you got a deep V there, bro. Like, if that V were any deeper, it would be teaching transcendental literature at Berkeley University. Really deep V...
Daniel Rogness - are you seven ? What an infantile remark .
isn't this essentially how a NOT gate works? given an input "1" it gives an output "0."
Not really.
The machine is the contradiction of itself.
Consider these statements:
The following sentence is definitely wrong
The previous sentence is definitely correct
So, if you assume sentence 1 to be correct, it means sentence 2 is wrong, which in turn means sentence 1 is wrong, which contradicts the previous assumption.
idk why i'm having so much trouble grasping this concept lol
it is a hard concept to get, I don't think many people can get their heads around it
sooooo.... H is the one that has to decide wether a given thing terminates or not... the given thing is itself with an extra. take a look at it: it only terminates (H+) if there is the 'yes' in the output. when will this happen? only if H says "no - it wont terminate. so if H says, it won't terminate... it'll terminate... and... H knows that... so it says.. NO- it won't terminate... but in this case it terminates.. so H could say it terminates, but in this case it won't... so H will say "no, it won't terminate" but than it will. and so forth... it can't decide. like... "this sentence is a lie" if it is... it's not. and if it's not... it is...
if it decides, that decision will be the wrong decision - in any case. but if H knows that it will change it's decision... wich will be the wrong, too.
the question was: "could there be an algorithm or machine, wich can ALWAYS decide, wether a given algorithm will terminate or not? so we concider it to exist. and bring up a situation wich brings it to a contradiction - it can't always decide. the conclusion is: there can't be a thing like this.
NokiStrawby in just wanted to break it down for the other guy ;)
The more interesting question is, could there be an algorithm that solves the halting problem for all but a few classes of programs? For example if we rule out feeding a modified version of the algorithm to itself (as the proof does), could there be an algorithm that solves the problem for all other cases?
but a few classes of programs? If you consider an infinite amount of programs as a few, then yes.
But that is like saying "Can pigs fly if we dont look at the pigs that can not fly".
@@Schnorzel1337 Not really.
When Gödel published his Incompleteness Theorems, they also relied on some self-reflexivity trick to prove.
Only when Cohen proved the Continuum Hypothesis is undecidable, it became clear that important real-world issues may exceed the limits of ZFC.
I have a point of disagreement/confusion. In the final problem you presented that causes the contradiction, H+ takes as an input two instances of H+, but loops on forever iff H+ halts on a single input instance of H+, and halts iff H+ does not halt on a single input of H+. So what's actually happening is that H+ is running forever on two inputs H+ and H+ when H+ halts on a single input H+, and vice versa. No two opposite things are occurring at the same time, so no contradiction so far.
Obviously this can easily be amended by changing H+ to take only a single input, and then feeding those two inputs into its built in machine H.
Just yesterday I went to work in my girlfriends top, happens to the best of us.
I don't get the joke "halting is good"... anyone care to explain?
Normally if something breaks down (Eg a car) it halts... >Sean
if you could wait for the eternity you could eventually (maybe) get the answer, yes or no
but no one got time for dat
better to stop the thingie before it so we might even get an answer another way or to another broblem
What i'm failing to understand is what is the input to the H+ being used as the input of P? And would this make a difference?
Do a video on the relation of the Halting problem and the Gödel's Incompleteness themorems!