Turing & The Halting Problem - Computerphile

[@joebrooks370Z]

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.

[@jordanthedove]

Many thanks!

[@rengsn4655]

Thanks. I finally understand it

[@FlyingTriX]

Nicely put.

[@MaxLohMusic]

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"?

[@geraldine-211]

thank you

[@CatnamedMittens]

Deepest V neck of all time.

[@TheRealFallingFist]

And potentially the worst tupé ever :P

[@frankenshizzle]

+CatnamedMittens “Michael Bialas” limit x → ∞ : V neck = 11

[@CatnamedMittens]

Sgt Jupiter I don't know what this means.

[@Minty1337]

+Sgt Jupiter true, but I think you were a bit off, V neck = 12, rounded up rather than down

[@IIIIIIIIIIIllllllIIIIIIIIIII]

+CatnamedMittens (Michael Bialas) wtf this isnt a thorin video

[@grinofthegrimreaper]

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.

[@bradleyberthold4606]

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.

[@heek40]

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.

[@PauloConstantino167]

Turing's argument is bollocks and doesnt prove anything.

[@PauloConstantino167]

Nope because he creates a contradiction in the first place in order to prove something. What kind of proof is that?

[@PauloConstantino167]

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.

[@Yaxqb]

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

[@msironen]

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.

[@matanshtepel1230]

Clever! Thank you for sharing!

[@eac-ox2ly]

Incredibly put!

[@rupen42]

Would it need to be "immediate"? What if it took 1 mllion years to run?

[@janPeja]

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.

[@avramcs]

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

[@HumanRights4Everyone]

What if it simultaneously halts and doesn't halt until it is observed?

[@maikio2729]

i see what you did there ...... but this is no quantum computer

[@vivivizion]

Oh for Christ's sake Schrodinger, get off of youtube.

[@bobsaggat]

HumanRights4Everyone pilot wave interpretation FTW!

[@TheSnowmason]

Schrodingers computer.

[@JasonMasters]

Then you train a semi-existent cat to go in and repair it.

[@wingsandstache]

What would happen if pinocchio said: My nose will grow

[@wingsandstache]

Gregory Reis yes

[@jonesgerard]

+wingsandstache It would not grow because he was telling the truth.

[@wingsandstache]

***** You got it right.

[@wingsandstache]

***** 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?

[@wingsandstache]

Right, then if 5 machines make 5 things in 5 min, how long would it take 100 machines to make 100 things?

[@Xefox]

H+ instead of H'. I'm concerned

[@robertkiestov3734]

*>furry weaboo*

[@robrick9361]

I did a depth-first search on this page, it returned his V-neck.

[@Kalernor]

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.

[@gonfreecs1335]

wow thank you

[@kanekeylewer5704]

You just repeated what he said in the video.

[@sayanghosh6996]

@@kanekeylewer5704 because some people have problem understanding what proof by contradiction means

[@shuaibmohammed4293]

@@sayanghosh6996 gang gang you amazing

[@matamorosa]

that's a great explanation, thanks!

[@arnoclaude317]

When someone asks whether h+ halts or not: Well yes, but actually, no.

[@ahobimo732]

But also actually no.

[@bbrraayy]

nes? or yo?

[@herscher1297]

The 3rd layer of H+ has no input so the programm cant run

[@ChaosPootato]

I love how there's tea and cups behind him :D

[@trudyandgeorge]

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.

[@murphy54000]

George Edwards His nose would not grow. Paradoxes are not lies.

[@BroadcastBro]

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

[@murphy54000]

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.

[@BroadcastBro]

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

[@migueld7916]

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

[@gordonfreeman5958]

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.

[@paulvorderegger1522]

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?

[@gordonfreeman5958]

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

[@paulvorderegger1522]

@@gordonfreeman5958 Ok I finally understood this after seeing the following pseudo code: def thisFunction ( ): if halts(thisFunction): loop_forever( );

[@mthai66]

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.

[@karlkastor]

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.

[@archidsouza]

After listening to this, my brain halted :P

[@Twisted_Code]

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

[@yousorooo]

Same with sets

[@flo0778]

@MrBigbanan imagine you are trying to actually learn something and you ask a very hard question to your computer. If it "runs forever" you will never be sure that its a no, maybe its just slow and it will eventually say yes. And you cannot ask another computer to tell you if it will run forever...

[@flo0778]

there is not really any self referencing here, H+ is defined without H+, same for H. Imagine H+ is some actual .exe file that needs a file as an input, you are allowed in the real world to give the .exe file to your .exe program.

[@98Vuk]

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.

[@javierfernandez1126]

I asked exactly the same thing, it would be great if someone addressed this issue.

[@Outwardpd]

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

[@eac-ox2ly]

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.

[@eac-ox2ly]

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

[@maxinelyu2693]

@@eac-ox2ly Awesome. Thank you!

[@Kat-qk5ob]

I’d just like to say: The dramatic close-up when you say “it’s a paradox.”? Very Nice

[@fridaaa0]

It's the little details

[@okboing]

I like the idea of a machine with a billion binary inputs and tons of layers hidden inside and a single binary output.

[@TheKseth]

Can't remember the last time i was confused this much.But your explanation is better than the other guys so cheers!

[@florianh.6256]

***** FYI: This almost 1 year old video misses links to promised videos at the end.

[@Computerphile]

Florian H. thanks for the spot - fixed now >Sean

[@jonesgerard]

+Computerphile You fixed the halting problem, add links !

[@johnsherfey3675]

Wouldn't that just be a superposition of halting and non halting? so your answer is both?

[@sayamqazi]

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.

[@Roman-ey3yi]

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?

[@WaffleAbuser]

+Roman He's proved that the existence of H will lead to paradoxes, so therefore H can't exist.

[@ximbabwe0228]

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.

[@TheVMDC]

fk u all

[@IoriTatsuguchi]

@@ximbabwe0228I understand that it doesn’t matter in the end, but this unexplained noise is so jarring. If it doesn’t matter if it halts or not, when the answer of the machine h was an “yes”, then it’ll be far nicer if he just said “this doesn’t matter in the end but let’s say it just doesn’t halt, just loops.” rather than just giving me the definition as if it’s logically meaningful role. My wrong assumption was that the output supposed to try to give an answer to the original problem because the no leading to halt sounds like an intuitive upgrade to give an answer to the original problem.

[@Holobrine]

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.

[@IceMetalPunk]

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.

[@naimulhaq9626]

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.

[@PeterWalkerHP16c]

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

[@naimulhaq9626]

Peter Walker I am sure they were. Einstein took great interest in Godel's work.

[@hanugn]

It reminds me of the book "Goedel, Escher, Bach".

[@SternKylar]

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.

[@akn4336]

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.

[@softwarelivre2389]

H is part of H+

[@logankeeton3931]

It’s the same thing you are feeding it into yourself

[@rafaelclp]

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.

[@ramos_4892]

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

[@sully9937]

I've been reading the comments for a while and I think I get it. H is a computer system that can solve the halting problem of any algorithm, however from H, we see that H+ can conceivably exist. H+ contradicts itself. Now forget the link between H and H+ for a minute and see H as simply representing the ability to solve anything. Since H+ cannot be solved as it's paradoxical, H can't exist because H is predicated on the ability to solve everything. The impossibility of H existing means there cannot be a machine that solves all algorithms, because that's what H is literally supposed to be. Consider this a logical problem rather than a material one above all, and it makes more sense.

[@paulvorderegger1522]

The following 3 lines helped me understand it: def thisFunction ( ): if halts(thisFunction): loop_forever( );

[@ZandarKoad]

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

[@ZandarKoad]

Thoughts on this?

[@blablabla1044]

@@ZandarKoad I agree, and cannot find a proper example/explanation anywhere.

[@DannyPhantumm]

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

[@TmoVie93]

I had to watch this video twice trying to understand it. Great one!

[@PhyloGenesis]

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.

[@bartholomewhalliburton9854]

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.

[@bartholomewhalliburton9854]

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)

[@yunochill9304]

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.

[@cktken3336]

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.

[@burstofsanity]

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.

[@TheDrugOfTheNation]

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.

[@PvblivsAelivs]

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.

[@theatheistpaladin]

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.

[@WofWca]

It's not necessary to simulate it in real time.

[@dragon-xt4vw]

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.

[@paulvorderegger1522]

You dont have to simulate if it will halt or not because the simulation will NEVER have an infinite amount of time.

[@nugget4814]

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.

[@kot_robot8205]

but maybe there can be a program that solves the halting problem for all programs except itself !

[@tomerwolberg37]

It's not for itself, h solves the halting problem not h+.

[@greencoder1594]

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

[@drprofex]

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

[@alandouglas2789]

Good to see a video about Alan Turing

[@fadibitz]

*****: 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.

[@quanahcruz9296]

I don' t have that much context on the Halting Problem, but at a glance i want to argue that this proves two possibilities: either H is not possible, or H+ is not possible. I know that the idea is that we know it's possible to make an algorithm loop, but the whole basis of this thought experiment is that we don't yet know what parameters H consist of. It seems totally possible that this theoretical H machine could not be combined with the "+" looping algorithm. You have to first prove that it is possible to combine a theoretical, as-yet nonexistent machine with an infinite loop.

[@kristiansmurds2067]

I was lost already at 1:14 when he said: "can we automatically test whether the premises entail conclusion"

[@Shu8i]

This was a brilliant explanation of the halting problem! Thanks!

[@ZantierTasa]

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?

[@TheCriticsAreRaving]

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().

[@sababugs1125]

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

[@mike_o7874]

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

[@mike_o7874]

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

[@laymer7]

Teacups and tea in the background contribute to making this footage as british as can be

[@Vulcapyro]

This comment section needs to take more math classes.

[@DrBrainTickler]

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.

[@Agent1W]

+dork "More" is a comparative term. More than zero? More than one? Five? Ten? Twenty?

[@CZRaS]

@@Agent1W he meant "more meth"..

[@DonVigaDeFierro]

@@DrBrainTickler Living example of the dunning-kruger effect.

[@SilisAlin]

What does it have to do with math?

[@floppy-disko2378]

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.

[@FortoFight]

Star Trek would still make a device like a "halting compensator" or something to sort this mess out.

[@EtzEchad]

The halting problem was interesting, but more importantly to solve that problem, Turing had to prove that his idea of a digital computer was equivalent to first-order logic. The proof that 1st order logic was not decidable is just a footnote in mathematics, but the TURING machine changed the world.

[@danielemessina1979]

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

[@kaiufkdlsmf]

'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?

[@danielemessina1979]

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

[@kaiufkdlsmf]

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?

[@letao12]

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.

[@Outwardpd]

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.

[@TheRiverNyle]

I think it’s best to understand Diagonalization before The Halting Problem, it would make a lot more sense then

[@granceroblast]

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 KZbin, 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+?

[@LeanderKu]

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.

[@idsamuel]

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

[@42adb]

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.

[@dreadrocksean]

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.

[@Ultimanimes]

Well, I didn't understood the proof for the same reason Gran said...

[@178890905]

Thanks, big help! I was confused about this topic for my discrete math class, you saved me.

[@GtaRockt]

man I love turing machines. When we did that stuff in uni, man I adored it so much

[@tanya-pp2jt]

wish i had someone like you to teach me this stuff >.

[@Andrew-bf2oj]

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.

[@hamza-trabelsi]

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 ?

[@LuizDahoraavida]

looping forever is the opposite of halting, meaning it doesn't halt

[@Kalernor]

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.

[@tubebrocoli]

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.

[@Yizak]

Thank you. It makes perfect sense now. I couldn't understand how H+ could take an input of just itself.

[@GokutheBlack]

Here is the problem.The machine that is pieced onto H is designed specifically to give no answer in the event that the answer it is given is a positive one.Because it is contained within its very design that "it will halt",in a sense,it doesn't halt.Halting is a response to its input and it is therefore an output,even if it is not observable.Logically,it does not halt because of a malfunction or because it cannot solve the problem,it has already solved it,and the answer to it causes the machine to stop working."Halting" is an answer and machine H is still correct and it has solved the problem.No contradiction exists.

[@MrTStat]

could he be more abstract ?!

[@mattg6728]

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.

[@anaraug]

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?

[@anaraug]

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?

[@JasonPruitt]

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.

[@Celrador]

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

[@ricardoamendoeira3800]

He tried to simplify the solution, you can actually prove the same thing with no modifications to the H machine.

[@tubebrocoli]

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.

[@JasonPruitt]

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.

[@PJoelJ]

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.

[@jyrikgauldurson8169]

this paradox is like russel's paradox and it has to do with self-reference again. MAN!

[@ShinyVeggie]

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.

[@DaFish1337]

His accent is just a pleasure to listen to!

[@jasonpatterson8091]

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?

[@walde3329]

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

[@Kalernor]

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.

[@blablabla1044]

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

[@shmeleu]

Damn, read a dozen of articles on the halt problem and this video was the only one that I understood at last. Others simply state - we got a paradox ))) but do not say what the paradox is.

[@queendaisy4528]

Consider the following: "This statement is false". "Does the set of all sets who do not contain themselves contain itself?" In both cases, you get paradoxes; if it's true then it must be false then it must be true and so on forever... And likewise, if it contains itself and only contains things that do not contain themselves then it should not contain itself which means it should contain itself and so on. My point is this; if ever you try and do logic on a statement or question whose answer depends on the result of said logic, it's easy to produce a paradox. That doesn't mean that your assumption that such a form of logic can exist is invalid- only that you can't apply it to itself in a particular way; it would be easy to produce a program who responds to "All cats have seven legs" with "That statement is false" or one who responds to being asked "Does the group of all groups whose name contains the letter 'e' contain itself?" with "Yes".

[@Niki_0001]

I'd like to hear more of this guy!

[@luckygozer]

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

[@NoRotation]

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.

[@Snagabott]

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.

[@NoRotation]

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.

[@Snagabott]

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.

[@NoRotation]

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.

[@nixalot9065]

So long as we cannot ever solve a logical paradox, a machine cannot solve the logical paradox.

[@lolzomgz1337]

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?

[@flagman57]

actually a human couldn't solve the halting problem because humans are at most turing complete

[@simon7719]

+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 :(

[@lolzomgz1337]

Simon Lindgren Damn. :(

[@PhilippeCarphin]

+lolzomgz1337 This is a vulgarization of a problem that is actually harder to prove than this so you have to give some leeway.

[@lolzomgz1337]

Philippe Carphin Okay, fair enough.

[@heaslyben]

I enjoyed this video. I appreciated the deliberate pacing of your explanation.

[@piotrarturklos]

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.

[@TheInonstar]

+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

[@piotrarturklos]

+inon star Yeah, I know that, just not from this video.

[@preacher066]

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

[@piotrarturklos]

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

[@preacher066]

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

[@lixincwru]

very good explanation in a historical context

[@TheSalaho1]

you should feed h+ to h not h+ to h+ because h+ is a modified machine to reverse the output real meaning.

[@Kalernor]

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.

[@foreverseethe]

Hmm the idea comes into a bit better focus like that. But why do these machines need two inputs?

[@alureon1]

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

[@NottoriousGG]

I wager this is solvable in superimposed first order logic for a Quantum Turing Machine.

[@Ricardo0125]

just like the pinocchio problem: what if he says: my nose will grow.

[@mouradqqch1767]

his nose will explode

[@peterwright5311]

Nothing happens. Pinnochio's statement is a prediction, not a statement of truth, he is wrong, not a liar.

[@romali593]

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.

[@Agent1W]

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

[@pkgamma]

This really got me thinking.

[@nirnayrath9828]

As a child I was told about this problem where a crocodile takes a fisherman's son away. He then places a condition before the fisherman that if he predicts what he was going to do with his son correctly, he'll get his son back. And the fisherman says that the crocodile will not give the son back. What does the crocodile do now? This problem was called the Crocodile's Dilemma.

[@SodaliteSabre]

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?

[@SodaliteSabre]

***** 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?

[@SodaliteSabre]

I'm still confused. What alternative is there to thinking of them as something besides different machines?

[@Dandelion_Stitches]

***** 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?

[@SodaliteSabre]

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?

[@Dandelion_Stitches]

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.

[@wwm8795]

+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

[@spendle]

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

[@mjlavall]

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.

[@mart3323]

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+

[@mjlavall]

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

[@Contradel]

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.

[@mart3323]

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)

[@Contradel]

H+ get's the wrong answer because they are faulty, but H isn't.

[@elliottmcollins]

***** This is excellent! Computerphile is at its best when it's talking about computer science rather than nifty toys. A Numberphile for computer science. Love it.

[@Paxsali]

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)

[@quasa0]

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

[@herrfz]

I don't get the joke "halting is good"... anyone care to explain?

[@Computerphile]

Normally if something breaks down (Eg a car) it halts... >Sean

[@EpicFishStudio]

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

[@thealterego1777]

This problem can be easily solved when the computer is quantum in nature. A quantum computer returns an output that has a superposition of states, and can deliver an answer when it's measured. In this case, the probability of getting a 'yes' or a 'no' is exactly 50-50, but before the answer is figured out by this computer, it has to be built. Since it is a quantum computer we are considering, we might as well ask a human being what the answer would be in terms of 'yes' or 'no'. The correct answer must be a superposition of both, which is the correct justification in this case because the machine is designed to be paradoxical, whose output is not logical. This is why the halting problem and its implications are not limited to the binary space, but it extends to the quantum space as well.

[@thealterego1777]

The other solution is to alter the problem so that it can be solved, because the problem exists either because it does, or because it was thought of. If it exists because it is, then there must be some solution beyond our understanding. If it's the latter, it can be changed so that the computer can compute.

[@Schnorzel1337]

You make absolutely no sense. Quantum computers are not magic, there are problems that require more space than atoms in the universe, or more calculation time then the universe will last. Simply put how would a quantum computer print every digit of pi then stop?

[@KaiserSpherical]

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

[@007KayElleKay]

Daniel Rogness - are you seven ? What an infantile remark .

[@MPSpecial]

I'm still not exactly convinced by this proof, because we didn't really proved H couldn't solve the halting problem, we proved H+ could not when fed with itself. But many functions can behave oddly when fed with their own identities or their outputs as inputs. Maybe somebody can enlighten me on this point 🤔

[@TimVerweij]

4:30 About feeding H+ into H+: Since H+ requires 2 inputs, this would require a recursively defined input, right? p = H+ and i = (p, i) Edit: Ok, many people commented this already, of course. :-D

[@herscher1297]

Is there an answer?

[@sababugs1125]

Computer scientist destroys super Turing machine using facts and logic

[@JahMusicTube]

I'd like to suggest to everybody on this comment section the reading of "Goedel, Escher, Bach: An Eternal Golden Braid" by Douglas Hofstadter. Great book very funny and interesting.

[@imnotrich12321]

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.

[@jagmeetsingh9812]

kzbin.info/www/bejne/o5LGfpKDqbiSrZY Here, why is he making the machine loop forever if answer is yes?

[@Sebastian-hg3xc]

He's creating a contradiction. He originally started with the proposition that there is a program H that can solve the Halting problem. Using only valid transformations he created a new program H+ that if run on itself has a contradictory output like "If H+ halts then it doesn't halt. If H+ doesn't halt then it halts" (in both cases H+ both halts and doesn't halt at the same time). Such a program cannot exist. This means something we did must be wrong. Since the transformations are all correct the problem must be our original proposition that there is a program H then can solve the Halting problem. So the conclusion is that our proposition is false and there cannot exist such a program H that solves the Halting problem. This method is called proof by contradiction. To prove a statement you first propose the opposite. Then you try to construct a contradiction like "1=0" or "A and not A". If you are able to construct a contradiction with only valid transformations you have proven that your proposition is false. If your proposition is proven false then your original statement is proven true.

[@katelyn3047]

I understand why the output at the end is contradictory, but I don't understand why the transformations that he made in the beginning (i.e. turning H into H+) are considered vaild. I'd really appreciate it if anyone could try to explain this to me! I really want to understand what I'm missing in my understanding! Perhaps my inability to grasp the validity of the transformation made to turn H into H+ is due to my weak background in mathemtics; thanks for your help!

[@letao12]

Basically anything you can construct is valid. Take a real world analogy. Imagine if you give me an engine "E" of some kind which you say runs fine. Then all I do is add a couple of gears and brakes without modifying what's inside E. It's "valid" in the sense that there's no logical reason why I shouldn't be able to do that. I call the whole thing "E+". However when I turn on E+, I get something that both runs and stops at the same time. The logic is, since I haven't done anything that could possibly be a contradiction (adding gears and brakes can't create contradictions), then something must be wrong with your E to start with.

[@TheInevitableHulk]

What I don't understand is how H+ can even be called in the first place. H+ requires a program and an input. H+ refers to itself as the program but it's output as its input. Neither of H+'s outputs produces a valid input. Loop forever will never return a value, and Halt would immediately end the program, neither resulting in a valid input. Also, H+ needs to take in a program and an input, but its input is a program and its input which is a program and its input? It seems like the H+ paradox itself cannot even exist because the conditions that create the paradox cannot even be started.

[@MrOzzblizzard]

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?

[@MrOzzblizzard]

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

[@letao12]

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.

[@MrOzzblizzard]

Ahh that makes more sense to me now. Thank you

[@auntiecarol]

And then Wolfram comes in with his irreducible computationality (shades of Hitchhikers Guide to the Galaxy?): we won't know if something is decideable (or not), until the universe has run its course. At which point we won't be around to evaluate the truth statement anyway. Mind-bending stuff.

[@JelloPuddingMaster]

4:59 h+ will not give an answer because of infinite recursion (Will h+ halt given will h+ halt given...) thus the paradox never exists.