Turing & The Halting Problem - Computerphile

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/nottscom...
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradycha...

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

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

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

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

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

[@archidsouza]

After listening to this, my brain halted :P

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

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

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

[@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( );

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

[@MrBigbanan]

Why do we care that it "halts" when we should just count the lack of No as No ?

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

[@MrBigbanan]

@@flo0778 been there done that lol

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

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

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

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

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

[@wheezard]

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

[@okboing]

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

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

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

[@qwertyman1511]

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

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

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

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

[@SolomonUcko]

If you pass H+ to it self, what input does it get? Or would it just loop forever waiting for input?

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

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

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

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

[@TheKseth]

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

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

[@mgladders]

Sorry if it's been asked/answered before but I'm confused. Why must a 'yes' answer result in a loop? Why doesn't it just stop? And why not permit the 'No' answer to loop?

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

[@andrewporter1868]

There is an error in the "proof" (and while I'm at it, a paradox does not conclude that an argument is false or faulty). The premise of H is that it decides whether a program P halts on input I. We deduce from this premise that it is metaphysically impossible for H to loop forever as H must halt in order to give an answer. We then build H+ which has H, and another program we'll call ~H for "invert H". We will then attempt execution of H+' = H+(H+, H+). The arguer asserts H+' loops forever. If this is true, then the halting problem is decidable because you just proved it so algorithmically by simulating the process. If it doesn't loop forever, then the halting problem is decidable by the same assertion. The issue with this construction of H+, however, is that H+' is not H(H+, H+), and we've already determined that H must halt. This essentially means that the H+' that is being claimed here _cannot exist_, and that the H presented is a different H in substance than the H that does in fact halt to decide if P halts on input I. Now if we entertain the erroneous construction and pass H(H+, {H+, H+}), then as the arguer observes correctly according to the logic that he follows, so likewise, H here will halt and give the same result: that it will loop forever. I here give a counterproof against the halting problem proof by using Turing's proof itself: We presume that in order for H+' to be undecidable, the H+' construction itself must be undecidable, but if it is undecidable, then it is decidable: a paradox. This is a veridical paradox: if a thing has any definite answer within the context of decidability, then it is decided, therefore, if H+' is undecidable, it is decidable, and if it is decidable, then it is decidable. In both cases, we must, by metaphysical necessity, conclude that the halting problem (and all other questions about things that proceed from the natural order) is decidable since H+' being undecidable is a definite decision, and the H+' being decidable is a definite decision; since it cannot both be decidable and undecidable, it is therefore decidable. QED I would note that this "undecidable -> decidable, decidable -> decidable" lemma only applies to this type of question uniquely because of auto-decidability. Attempting to apply it elsewhere doesn't work, not even to the question, "is decidability decidable?" The simple reason is because the nature of Turing's proof's auto-decidability arises from an oversight in the definition and logical proceedings of H and its behavior within H+, the oversight being that H is capable of looping forever. Even if it were, the fact that the arguer can _logically_ deduce that H+' never halts implies there exists a deterministic H by the logical process employed, and that the H within H+ is therefore merely an imperfect subset of H. The universal that any thing with a definite answer is decided may be used to analyze The Liar's Paradox and have it be considered also as a veridical paradox. Gödel's Incompleteness Theorem is incomplete (lol). "This sentence is true" is easily analyzed and concluded to be true, but "this sentence is false" is commonly concluded to be indeterminate. In reality, what's going on here is similar to the issue of the halting problem, and since we are using subjective semantics in this sentence with no other context, the reality is that "this sentence is true" must _also_ be indeterminate, even if by default, we can _believe_ these two statements to be true according to the rule of charitable interpretation. If we choose to believe the two statements are true, then no contradiction can exist as we've created an objective context to interpret the subjective construct with: we have asserted that, objectively, they are true, therefore they are true; the simple fact of the matter is that "this statement is false" is asserting "the sentence, 'this sentence is false', is false" which is a valid equivalent construct to "this sentence is false". If we assert that they are objectively false, then they are both false, in which case "this sentence is true" becomes a lie which would concur with the objective assertion. This is all really just a simple matter of recognizing that some things have no meaningful answer _in themselves_ because it would then be like trying to make an H that accepts only P but has no I input to consider: they do not have the substance of a _definite question,_ we might call it, and because they are _indefinite_ questions (as their opposite), they cannot be answered until they are made to be definite. Thus, we can at best conclude an indefinite question about the truthiness of "this sentence is false/true" to answer with indeterminate which is in the implicit negative, not affirmative, in the same way that indifference or agnostic atheism are implicit negative for their respective questions. Thomistic philosophy is universal. Other philosophies are not. Modifications: improved clarity and wording.

[@pepijnstreng4643]

You're thinking of a scenario where there's a second H outside of H+, which will correctly predict H+. But the point of the proof is that I can always put H inside of H+ and make it be wrong. It was also not asserted that it loops forever; just that if it did, the H inside H+ would say that, but then the ~H would stop so it wouldn't loop forever, and vice versa. We can always build a machine around H that proves H can't always be right.

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

[@mike_o7874]

there is a small problem with this explanation, H+ has to have only 1 input and duplicate it, as if it gets 2 seperate inputs, its all breaks apart. for instance if we ask what would H+ asnwer on the qeustion is what would H answer when H+ gets the input . clearly H+ getting the input is not the same as H+ getting the input , hence this is where this schema breaks. solution: H+ only gets 1 input : then asks what H would answer on . then when we ask H+ what would you answer on we ask H what would H+ asnwer on here we have no problem as yes eveyrthing else you are saying works fine. maybe iam wrong with my claim above but it was always bugging me that the "recursion" didn't work.

[@bartholomewhalliburton9854]

THANK YOU! Oh my gosh I was confused by the video but this comment is exactly what my confusion was about and presents a plausible solution.

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

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

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

[@tomtinker8220]

if i'm not misunderstanding it, is one example of a halting feature a bit of software that checks for bugs when developing software?

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

[@eigenmishi_in_3d]

Just to clarify: the logic here is that if your conclusion is paradoxical, then the premises are necessarily incorrect? Is that always true? Or is it just true for stuff that we can or can't design?

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

[@AarshWankar]

4:22 Here, the H+ machine has two objects as input. So when (H+, H+) is fed as an input to H+, the input first goes through the machine H. The machine H answers the question of "Does the machine H+, when given H+ as an input, ever halt?". My confusion is in this question itself. How can the machine H+ accept just one object as input? It's designed to accept two, right?

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

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

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

[@deepakchandan8159]

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.

[@hanugn]

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

[@amras0000]

I'm a little bit confused, Jago started by talking about a very vague premise-conclusion problem and he wound up only proving that a halting machine could not exist. What relation does this have to premises/conclusions?

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

[@MisterF_1984]

H has two variables, P (program) and i (input). We want to know: does H+ halt given input H+? So we ask this question of H. i.e take P = H+ and i=H+. But your H+ machine needs two variables - P and i. We can't feed your H+ with just H+, it also needs an i.

I completely agree with you. I think there is something missing in the demonstration. It is not as simple as just feeding h+ to h+ as he said or (h+, h+) to h+ as he drew in the notebook. The second parameter should work as an input for the first one and as you said h+ requires 2 parameters

[@CertifiedDoc]

Mister F The input for H is also the input for P. If we had a simple adding machine, where P = Adder, the input would be an expression, such as i=2+2. If H is asked to evaluate itself, what are its P and i? P = H, because that's the program being evaluated. What values could you pass to i? Because H is designed to test whether programs produce output, you could pass any program in as i. In this case, i = H. H is being asked to recursively evaluate itself. This is also true when H+ is used in place of H.

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

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

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

[@kashyapthacker1214]

Excellent Explanation...!!! Just a doubt whether h+ can be fed as input in h+ necessarily requires input h+? Don't we require one machine an any input will work? A theoritical explanation on paper wouldn't be more appropriate?

[@Chruschtschowka]

This proof is maybe a bit too short to explain that question, but let me try to help you out: Let me introduce some variables: g and f. Let us assume f is the function which is calculated by h+ and g is a the function that calculates h. Some examples: f() = yes, f() = no answer (endless loop). g(, ) = yes /no g(h+, ) = yes /no Now we need come to the point with the input: f(x) prints yes or gets stuck. g(h+,x) prints yes or no. 1. Assume f(x) prints "yes": g(h+,x) gets stuck=> no paradox 2. Assume f(x) gets stuck: g(h+,x) just prints "yes" => also no paradox But now assume x = h+: 1. f(h+) prints "yes" (so it halts): g(h+,h+) negates that and gets stuck, *but f calculated that h+ halts, but h+ does not halt => paradox* 2. f(h+) prints no(so it gets stuck): g(h+,h+) negates that and prints "yes", *but f calculated that h+ gets stuck, but h+ does print "yes" => paradox* It is paradox because: we assume that h (function f) always prints the correct answer. With the feeding with the input h+ and the "negation" with machine h+, we always end in a situation where h+´s answer is not the same as the maschine h told us.

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

[@TmoVie93]

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

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

[@romanromi9624]

Correct me if I’m wrong but doesn’t this only proof that h+ cannot exist? Also isn’t one creating the contradiction by simply giving the machine and infinitely long input? This just show that an Algorithm can’t work if every input need another input but this input again needs and input and so on. So it could exist under the rule that an input has to finite.

[@MisterBrausepulver]

Why should H+ not exist? First of all we assume H exists. Then we could show that, if H exists, then H+ must also exist. Agree? When we run H+ with input H+, then either H+ does halt or H+ does not halt (either on MUST be true by the principles of logic). Let's look at the case where H+ halts, then we get: H+ halts -> H detects that H+ halts -> H+ loops forever (H gave the wrong answer) The other case (H+ does not halt): H+ halts not -> H detects that H+ does not halt -> H+ halts (H gave the wrong answer again) Let's recap: We started with the ASSUMPTION that such a Program/Machine H exists. From that we derived with simple logic that in a world where H exists, there must also exists H+. Then we found out that H+ behaves contradictory and in fact that means, H+ can not exist. But the contradiction remains because we can proof that H+ exists and we can proof that H+ doesn't exist. And finally this means that our assumption, the starting point of our whole argument, must be wrong. This is what's called "Reductio ad absurdum" or "Proof by contradiction", and is used all the time in mathematics and logic. If you wan't to proof something you assume the opposite is true and then show that your assumption leads to contradictions with no possible answer. To your second point: Programs in theoretical computer science are by definition finite in length. Just like the code of any normal computer program. In fact, an infinitely long computer program could never by written nor read by any machine. This would result in no machine halting on them, which would be uninteresting. This fact would also solve the halting problem for infinitely long programs (Think about it). I hope I could help you and answer your question. Feel free to ask if anything is still unclear.

[@FortoFight]

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

[@umangpandey1783]

What do you mean by the input h+? H+ can be fed as a program but how does one feed h+ as an input?

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

[@seanehle8323]

I am at a loss as to how you can give an arbitrary function an arbitrary number of inputs of arbitrary class. Many programs run without taking input, so how does that work? E.g. int main(){ int x(5); return x; } What does it mean to give this program itself as input?

[@JakeFace0]

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?

[@MattiasBuelens]

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.

[@ricardoamendoeira3800]

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.

[@tubebrocoli]

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.

[@girivkodur]

Hi, it may be very naive of me to ask this, but I have been thinking about this and I am not able to understand how exactly are the logical problem and halting problem the same? Could you help me out?

[@MisterBrausepulver]

One can show that a truing machine M solving the decision problem can be transformed into a machine M* (like H was transformed into H+) so that the new machine M* solves the halting problem. But the halting problem is undecidable, so M can't exist. The proof of this would reach lightyears beyond what one can fit in a youtube video and requires both a solid foundation in first-order logic and theoretical computer science.

[@kristiansmurds2067]

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

[@MrThumbsHD]

Why do you add the extra bits at the end? Halts = loop forever and doesn’t halt = halt. Can’t we just leave those out and the halting problem is solved?

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

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

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

[@IntarwebUser]

You've only disproved machines which are limited by the two inputs and one output as unable to solve the halthing problem. What if your halter determiner machine was able to take in more information than that? Such as, "Am I part of a larger machine?", or any other relevant information necessary to solve the problem?

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

[@sungboklee6790]

I don't get why he feeds h+ back into the h+. Is there a reason why, or can there be other inputs as well?

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

[@scoutdrago4]

I keep looking through proofs of this, but I am a little confused; it almost seems arbitrary that we say that if program P does halt on a given input of I, then we loop forever. Why would we assign "loop forever" to the output of yes ("it does halt")? If such a program could deduce that we halted, why would it then need to loop forever? Would it not just halt after producing the answer?

[@paulvorderegger1522]

The following 3 lines will clear things up: def thisFunction ( ): if halts(thisFunction): loop_forever( ); Now, if halts says "thisFunction" will halt, then "thisFunction" will start looping forever, therefore the answer was wrong

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

[@goplayer7]

I have a question to extend this, which I could not find asked below or online. Lets say you create a machine that you claim "this can solve the halting problem for any input that does not contain an attempt to solve the halting problem". So H, H+, this machine, and so on would all be considered input that you do not claim it solve the halting problem for. Lets say in this case it gives a 3rd output "Invalid Input" so it makes no attempt to give answer about it halting or not halting. Is it possible to show that this machine can give an incorrect answer as well?

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

[@justinth963]

I don't understand. Don't you need to define the program and it's input to determine if the machine will halt? The inverse halt machine has been inserted into itself with no input. In my mind, this would contain an empty program, which would halt. This means the input would inverse, and therefore not halt if ran with this input. The top level machine would inverse this, and then halt. Im assuming I'm missing something?

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

[@wasistderunterschied3273]

I'm a little stuck, maybe someone can help me: I think its pretty clear that determining if a programm halts or not without giving it the input is impossible. Now lets take H (not H+!) and feed it to itself as program("Hp") and input("Hi"). H will now try to find out if "Hp" halts on "Hi". But "Hi" itself has to contain 2 arguments "Hip" and "Hii" to be a valid argument. "Hii" in turn has to contain "Hiip" and "Hiii" etc. So the input is delegated to infinity. Hence it is not possible to ever create a valid "Hi" (for this example). Which essentially is the same as running "H" without an input, since you cant put an input at the most infinite recursion. So is there really not way to get "H" running when "Hi" is evaluatable? Im still curious - recursions are not very human friendly :D

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

[@Mushroomjump]

Its a dumb thing but if X=X+1 where X is the Output then the loop would make scene and X would be 1-∞ in a loop. But wouldn't you prove that that is correct. Although its somewhat illogical but start with X as an Int add 1 so the new output is X. So the Output is either right or wrong but if it loops ether way is an issue with the Coding. Am not sure I need help on this.

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

[@unit411]

is time the missing factor in the halting problem ? if it were to time out then the halting problem is solved ? maybe 555 timers were newer back then or it would be harder to limit the amount of operations per program.

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

[@klikkolee]

why does the background of binary digits during the title contain two letter f's(or at least, I see two)?

[@klikkolee]

***** I know, but if it were supposed to be a hexadecimal background, it would have more than one, zero, and f

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

[@memorablename5187]

Looking at this from a programmers perspective, if we add an additional parameter say T and T represents a given Time unit. What if we assign T to H and if T exceeds some Upper limit say 24 hours. We can say that this program is not computable, and if the program computes in a time Under T we can say that is computable. I understand in terms of Logic, this is not a True, because Time is conceptual and a program could theoretically run for longer than 24hours and yet we cannot determine if it will Halt. However in a real world solution, would this be valid. Thanks for any answer.

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

[@ChristiaanMeyer]

So I understand that feeding the machine into itself is one counterexample, i.e. you can't use the "halting problem calculator" machine to calculate its own halting ability. But: can it be used to calculate the halting ability everything (or almost everything) else?

[@FawfulDied]

It could calculate the halting ability of many problems correctly, but there's also an infinite number of inputs where it's wrong. So no, it cannot correctly calculate the halting ability of almost everything.