Many thanks to everyone that has taken the time to watch this video. Eric Hehner is arguably the world's leading expert on the halting problem. I am very pleased to say that there is now a link to my video from Eric Hehner's page of halting problem links. In one of Eric Hehner's many papers on the halting problem he poses the question of how can we know when a program, written in an undecipherable language, has terminated. He poses this thought experiment as a way to convince the reader that termination is not a visible event. He believes that we could have a model of computation in which a program explicitly stopping and a simple loop such as '10 goto 10' are effectively the same thing in terms of halting. We might infer that it suggests that if we have a machine (or model of computing) which lacks an explicit HALT command (e.g a machine 'shutdown' instruction), then we could possibly manufacture one by 'defining' a simple loop to be a HALT instruction. However, personally I don't like this approach. We already have a widespread meaning for halting that we would be abusing by 'defining' a loop to be a halt. Also even if it is difficult to distinguish between the two scenarios from an external perspective, internally there will still be energy being used on the activity of continually going around in the simple loop. And so I prefer to imagine a computing machine as consisting of moving parts, and where halting means that the parts stop. We could open the lid of the machine and look inside to check if the machine has halted or not. If it was doing a simple loop then we would see movement and so I would not classify this as halting. Whereas if the program has encountered an instruction that says "stop now, don't execute any more instructions" then I would classify that as halting. The third option is that the program simply reaches a point where there are no further instructions. Some people believe that this should be called halting but I disagree. I call this 'exiting', or at best an implied halt. This is because control is passed back to the machine itself which might have been designed to halt in such a scenario, or it might have been designed to restart from the first line of code. In other words, whether or not it halts or loops would be machine-specific rather than program-specific. Now if such a thing as a Turing machine could exist, and if it could do anything that a modern-day real world computer can do, then it would be able to do an explicit HALT. However, if it were to lack this capability, then it would be inferior to real world computers in many aspects, not least of which is that it would be defeated by the logic of the halting problem proof. And of course, it could not be considered to be the only model of computing that is required because it lacks this key feature (of an explicit halt) that is present in so many real world computers. A so-called 'Turing Machine' is neither use nor ornament if it can't be used in relation to real world computation tasks. It is often claimed that Turing's proof of undecidability tells us that it must be impossible to develop a halt/loop decider program on any real world computer. I hope this video has cast some doubt on the validity of that claim. So the specification of the halting problem is flawed if it does not cater for machine-level halt commands because many real computers can perform this type of operation. Therefore the objection that this 'explicit halt' argument does not follow the specification is a moot point. Nobody should be following the specification if the specification is flawed. A real computer can write its output to a text file (or a printer or whatever) and then halt the machine. What matters is that H produces the correct prediction, not whether or not it is capable of being called by another program or whether or not it can return a true/false value to a calling program. Note that that we can have very low-level languages that are so-called 'Turing complete' which do not inherently contain any mechanisms for defining procedures or functions or returning values from these things. These days we take it for granted that we can call functions and get values returned, but in relation to the simplest of instruction sets these are high-level mechanisms that might involve moving data around in various registers and to and from designated areas in memory that have been given specific names such as stacks and heaps etc. I expect that a machine-level halt command would be a very simple operation in comparison to these complicated mechanisms. Should the real program H ever exist, another program would be free to initiate it (or 'call' it). However, this would present a problem if the initiating program wanted to do something else afterwards, because the real program H will end with a machine-level halt (or at least it will if its input program tries to execute equivalent logic to real H). And so say that program Z invokes H(X, X), then, given that X tries to execute the logic of real H, functionality H(X, X) will decide "It will halt" and then it will do a machine-level halt. There is nothing to stop us from starting the machine up again, feeding the output produced by H into functionality Z and executing the rest of the logic Z so that it uses the decision made by the real H. Of course it would be very inconvenient to have to re-start the machine every time after H has run, and even more inconvenient to have to feed its result into another program rather than it all being done automatically. But H only needs to do a machine-level halt if its input tries to execute the logic of H. Also, the question that the halting problem asks, i.e. "does it halt", could be considered to be a very bad question if the type of halt it refers to is only the implied type of halt. Note that this is similar to the Barber paradox in that it appears that the two options on offer are mutually exclusive and cover all options, when in reality they don't. The barber himself is not catered for in the Barber paradox just as an explicit halt is not catered for in the halting problem logic. This is why the halting problem question is a bad question. Some people might still claim that the halting problem remains undecidable even with a real world machine equipped with the 'shutdown' instruction because, by definition, the program H could never use this instruction. However, I believe this is like saying it is impossible to switch on a real world computer because someone, a long time ago, wrote a specification that says you are not allowed to press a button that would switch on an imaginary computer. In other words, in my opinion it is not good logic.
It's a trick of language to say that a machine "might be designed to do such and such" and implying that's somehow *different* from a program instruction in any practical sense. You can quibble over the origin of the instructions, but fact is, whether a machine is looping, halting or "exiting" - it is following some instruction. If the machine halts, then the action of halting is the last instruction it will perform. That's how halting is / should be defined. Any other definition is sophistry.
@Fictional_Name Many thanks for taking an interest in my video :) You said: It's a trick of language to say that a machine "might be designed to do such and such" and implying that's somehow different from a program instruction in any practical sense. I'm glad you made this point as it made me really think about what a program actually is. It provided me with an opportunity to clarify my position on this matter. Here are my thoughts... I've tried to imagine how your claim might be realised in a 'practical sense' as you say. I suppose rather than having a distinction between program statements and a physical machine upon which it runs we could just have a single physical machine for each individual instruction. Then we could connect several of these machines together in order to make one big machine which would be analogous to a hard-coded program. In this sense it can appear that the 'program' and the 'machine' are one and the same thing. So when we focus on what a machine actually does, it can appear that the two concepts of 'machine' and 'program' are one and the same thing. However, if we focus on what a 'program' really means then we might reach a different conclusion. If we think of a program instruction as being something physical (such as a punched card), which is interpreted by the machine and so on, then it is effectively an integral part of the physical mechanism. And so yet again your claim would appear to be correct. However, if we use a more dubious definition for the word 'program' then we might be able to draw a distinction between the two concepts. For example, we might describe it as a formal description of the operations performed by the machine. With this interpretation we have a clear distinction between the two concepts; one is a physical machine and the other is a formal (i.e. well-defined and thus unambiguous) description of the operation of the machine. If you reject this definition of a 'program' then wherever I have used this word you might replace it with 'description of operation'. I believe my argument would then still hold. After all, the one thing that we can't escape from is the necessity for a physical machine to exist. Even when someone dry-runs an algorithm in their head, the hardware and wetware of their brain will form the physical machine. And so the need for there to be a physical machine is a practical necessity in all cases of computation. With the apparent 'abstract' nature of Turing Machines people might imagine that programs (or 'descriptions of machine operations') can somehow be thought of as being able to execute all by themselves. They might believe that there is no need to include a device that processes the instructions and hence no need for a 'machine halt' instruction. But program instructions (or 'descriptions of operation') don't just work by magic. And so when we relate the halting problem proof to a real-world computing scenario we could deduce that there is a clear distinction between the 'descriptions of operation' and the physical machine. You said: If the machine halts, then the action of halting is the last instruction it will perform. That's how halting is / should be defined. Any other definition is sophistry. I'm not sure I understand you. Your definition of halting seems to include the word 'halts' and I'm struggling to understand what this means in a real-world scenario. Do you mean that if the machine stops executing instructions then we can say it has halted? If so then I completely agree with you. So if it 'exits' one section of code and proceeds to execute instructions in another section of code then it has not halted. I make this point in the video. Note that this does not prevent the existence of a type of instruction of the form "stop now and do not perform any further instructions" (i.e. a 'machine halt' instruction). If this type of instruction is allowed then my argument still holds; the halting problem proof is not a valid proof.
@@KarmaPeny Well I'm happy my comment could help you clear your thoughts more on the matter, that's rare these days. I agree with all you had to say about programs and machines executing them requiring a physical manifestation. A curious consequence of this picture though, is that no machine truly "loops" forever, since the universe has a finite amount of energy. But that's just a fun sidetrack. What I take issue with, is that you categorise "exiting" as a form of halting. When really you don't know if the new instruction will end up in a loop, or a traditional "stop" halt. If the new instruction were to end up in a loop, why wouldn't you categorise it as such? This just makes no sense in my view. It's violating the spirit of what it means to halt. To not execute further instructions. You can't simply define a new instruction set for the machine to execute, and say that because it's no longer executing the old instructions, therefore it has "halted" in some new fashion you call exiting. The machine does not know what it does. It does not know what instructions it executed in the past, or the future. It cannot distinguish between instructions and their source. (Be it inputs or part of the machine's "design" as you call it) It can either read the instruction and execute it succesfully, or not. Its parts (the turing head in particular in the case of Turing machines) are either moving, or they're stationary. I'd like us to define a machine as halted, if it is stationary. Or if that's too strict, an alternative definition such as "the absence of instruction-caused motion" is fine with me as well. But I cannot allow you to define a type of halting where the machine continues executing programs, that, to me, is absurd. Now, you mention that we could think of each program instruction as its own machine, and that's all well and good, but I am not sure how it helps your case. Each machine needs to have an input before it can execute any program. If one machine halts, then the other machines in the chain won't receive their inputs. It does not matter what you want the machine to do, or how confident you are it does it, once you feed it some input or program, *if the machine never receives said input* . Somehow, some way, that input (which contains information about itself) has to be physically transmitted to itself, from itself. And it cannot have that information without running the program first, so it halts. And using my definition for halting, it by definition cannot transmit information about its state to other machines, including itself. And if we assume it somehow doesn't halt, and loops instead, what good does that do? Arguably if it is looping infinitely, then much like we never reach the final digit of an infinite series, we never reach the end of the loop, we never get an output from the machine to use as input. It's in this sense I understand that mathematicians (which I know you aren't fond of) have come to the understanding that it is undeterminable, whether machine H will halt or not. You should be wary of your contrarianism. Being a dogmatic sheep that believes the consensus opinion because they trust the experts, is of course flawed. But it is equally flawed to be a dogmatic black sheep that disbelieves the consensus opinion because they distrust the experts. Both are two sides of the same coin. Let the arguments speak for themselves, don't be swayed either way by the popularity or acceptance of said arguments. I'll end by saying the halting problem is not unique. It's part of a class of problems in mathematics that all stem from self-referential statements. It is well known these types of statements result in paradoxes.
@Fictional_Name You said: What I take issue with, is that you categorise "exiting" as a form of halting. I don't want to; I prefer to have the three categories of 'loop', 'halt' and 'exit'. When I include it as a type of halting I'm just trying to sympathise with the viewpoint that the halting problem question is mutually exclusive and covers all possibilities. Decision problems should be mutually exclusive and cover all possibilities, and so if the two options are 'loop' and 'halt' then in order for these to cover all possibilities the best we can do is pretend that 'exit' is another category of halting. But I don't really believe it should be categorised as halting. I'm just trying to help the opposing viewpoint so as to be extra critical of my argument. You said: When really you don't know if the new instruction will end up in a loop, or a traditional "stop" halt. If the new instruction were to end up in a loop, why wouldn't you categorise it as such? This just makes no sense in my view. My three categories of 'loop', 'halt' or 'exit' apply to a specified section of code, not to any subsequent section of code (or machine functionality). If the first section of code goes to a 'loop' or 'halt' state then the processing will never reach any subsequent section of code. If processing exits the first section of code then the status of 'exit' applies to that first section of code regardless of what any subsequent section of code does. Don't forget that the halting problem proof requires us to take the halt/loop decider, H (which we might call our 1st section of code) and use it in a program X by adding a section of code to run after the first section of code (which will try to contradict the output of H). So if H ends by stopping the machine, then it will prevent the subsequent section of code from executing - and so X cannot contradict H. You said: You can't simply define a new instruction set for the machine to execute, and say that because it's no longer executing the old instructions, therefore it has "halted" in some new fashion you call exiting. I'm not inventing any new instructions. I don't understand why you think I am. You said: The machine does not know what it does. It does not know what instructions it executed in the past, or the future. I've never claimed anything like the machine 'knowing' such things. You said: It can either read the instruction and execute it succesfully, or not. Its parts (the turing head in particular in the case of Turing machines) are either moving, or they're stationary. I'd like us to define a machine as halted, if it is stationary. Or if that's too strict, an alternative definition such as "the absence of instruction-caused motion" is fine with me as well. But I cannot allow you to define a type of halting where the machine continues executing programs, that, to me, is absurd. Again, I agree that existing a section of code should not be called halting. We agree on this point. I agree that halting should mean stopping. We are in complete agreement on this. I was only trying to play devil’s advocate in order to help those people who still think the halting problem proof is valid. You said: Now, you mention that we could think of each program instruction as its own machine, and that's all well and good, but I am not sure how it helps your case. Each machine needs to have an input before it can execute any program. If one machine halts, then the other machines in the chain won't receive their inputs. It does not matter what you want the machine to do, or how confident you are it does it, once you feed it some input or program, if the machine never receives said input . We are in complete agreement on this. I don't know why you think we differ. You said: Somehow, some way, that input (which contains information about itself) has to be physically transmitted to itself, from itself. And it cannot have that information without running the program first, so it halts. As I say in the video, most people believe this kind of self-reference results in a type of looping. But should a halt/loop decider program exist then it should never go into a loop itself. Therefore it would need to analyse its input data in order to determine if it contains this type of self-reference, then it could print "It will halt" and then do a machine halt. You said: And using my definition for halting, it by definition cannot transmit information about its state to other machines, including itself. I agree that if program instructions are no different to physical machines (that execute instructions) then the matter of 'input data' becomes problematic. However, if we allow my dubious definition by which a program is a formal description of what the machine does, then this description could be fed into a machine as input data. You said: You should be wary of your contrarianism. Being a dogmatic sheep that believes the consensus opinion because they trust the experts, is of course flawed. But it is equally flawed to be a dogmatic black sheep that disbelieves the consensus opinion because they distrust the experts. Both are two sides of the same coin. Let the arguments speak for themselves, don't be swayed either way by the popularity or acceptance of said arguments. I always justify my arguments with what I consider to be good reasoning. I never claim that the consensus opinion is wrong on the basis that we should distrust the experts. I completely agree that we should not be swayed by the popularity of any particular viewpoint. You said: I'll end by saying the halting problem is not unique. It's part of a class of problems in mathematics that all stem from self-referential statements. It is well known these types of statements result in paradoxes. Yes, but the apparent paradoxes are only paradoxical due to the belief in non-physical mathematical existence, which itself is an absurdity in my opinion, or by tricks of logic where mathematicians have unwittingly managed to fool themselves. For example, consider the infamous liar's paradox which is the sentence "this sentence is a lie". The argument goes like this... If the sentence were true, it would be a lie. But if it were a lie, it would be true. This is a logical inconsistency. The problem here is what does the sentence "this sentence is a lie" really mean; what does it mean to say that a particular sentence is a lie? Let's consider a different sentence... Consider the statement "Bishop Stubbs was hanged for murder". If we consider this sentence as making an assertion about something in the real world, then we can examine the evidence to determine if this assertion is true or false. But the sentence itself is just a sentence, it has no truth property. Since the only real-world reference in "this sentence is a lie" is a self-reference to the sentence itself which has no intrinsic true or false (i.e. lie) property, we can only conclude that the sentence is intelligible. A statement would have to be comprehensible for it to be deemed to convey an inconsistency. And so the problem specification gives the impression that the two options of 'true' or 'lie' cover all possibilities when the reality is they don’t. The option of 'sentence is incoherent' is not supplied and yet it is the only applicable option out of the three. Another problem similar to the halting problem is the Barber paradox, where it is the specification of the problem that is the very thing that causes the problem. The specification says we must choose between 'shave themselves' and 'shaved by the barber'. These two options appear to be mutually exclusive and cover all possibilities. The trick is one of wordplay because the specification doesn't allow us the third option of saying 'do both by being the actual barber'. When we hear the logic of the Halting Problem proof it sounds like a sneaky trick. Indeed, it sounds very much of the same nature as the Barber paradox trick and the liar's paradox. It makes it sound like the two options that it specifies are mutually exclusive and cover all possibilities when in reality they don't cover all posibilities. In this respect the Barber paradox, the liar's paradox, and the Halting Problem are all just variations of the same underlying logic trick.
WHY THE RE-RELEASE???? I'm sorry, but I made a typo in the original that was really bugging me. At 7:16 which is at the end of my explanation of the original proof, the last line of the proof changes from "exist" to "exit" (in the original), which of course it shouldn't do!
Interesting vid. When do you think you'll have another video put out? I'm curious if you have thought of more stuff concerning .999... since your last video about it.
I plan to work on some more videos in the two to three months. Sadly no matter how many videos I produce about 0.999... they seem to have little impact. So I'm thinking that I need to make less subtle points about the foundational problems in future videos. For example, we can't 'imagine' an 'infinitely thin' line; an unending sequence of non-zero digits can never become a constant, and so on.
It might be decidable, it might not be. But the core logic of the halting problem proof is that it doesn't matter if you can detect that H logic is being used since X can always do the opposite of what H says. And so whether or not "Does it execute an accurate version of my functionality" is decidable is not relevant to whether or not the logic of the halting problem proof is correct. The Wikipedia page on the halting problem says: "...the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program-input pairs." And so in the halting problem we are given two apparently mutually exclusive categories: 'finish running' and 'continue to run forever'. If we use the categories 'halt' and 'does not halt' then it seems obvious that these must be mutually exclusive. But could it be that hidden in our interpretation of the word 'halt' we are not covering all possibilities? We all know that 'halt' means 'stop' but are we talking about stopping the machine, stopping the program, or even just exiting from the program (& thus implying that processing stops)? Here we have three different possible interpretations of what 'halt' might mean. The halting problem proof seems to assume that 'halt' only means the third of these options. It seems to me that the core argument of the proof would not work if we took the other possible meanings of 'halt' into consideration. To relate this back to what the halting problem was meant to address, David Hilbert's question of "is mathematics decidable", we might consider that "mathematics" and "a Turing-complete computer programming language (i.e. a demonstrably well-defined formal language)" are interchangeable. We might also take into account that the halting problem proof is a proof by contradiction, which means that it highlights a problem, but does not identify what that problem is. Then we could argue that the proof highlights that there are problems which cannot be solved by programming languages that lack the ability to perform halt instructions such as 'stop the machine' and 'stop the program'. But the logic of the halting problem proof does not prove that there are undeniably unsolvable problems.
Many thanks to everyone that has taken the time to watch this video.
Eric Hehner is arguably the world's leading expert on the halting problem. I am very pleased to say that there is now a link to my video from Eric Hehner's page of halting problem links.
In one of Eric Hehner's many papers on the halting problem he poses the question of how can we know when a program, written in an undecipherable language, has terminated. He poses this thought experiment as a way to convince the reader that termination is not a visible event. He believes that we could have a model of computation in which a program explicitly stopping and a simple loop such as '10 goto 10' are effectively the same thing in terms of halting. We might infer that it suggests that if we have a machine (or model of computing) which lacks an explicit HALT command (e.g a machine 'shutdown' instruction), then we could possibly manufacture one by 'defining' a simple loop to be a HALT instruction.
However, personally I don't like this approach. We already have a widespread meaning for halting that we would be abusing by 'defining' a loop to be a halt. Also even if it is difficult to distinguish between the two scenarios from an external perspective, internally there will still be energy being used on the activity of continually going around in the simple loop.
And so I prefer to imagine a computing machine as consisting of moving parts, and where halting means that the parts stop. We could open the lid of the machine and look inside to check if the machine has halted or not. If it was doing a simple loop then we would see movement and so I would not classify this as halting. Whereas if the program has encountered an instruction that says "stop now, don't execute any more instructions" then I would classify that as halting. The third option is that the program simply reaches a point where there are no further instructions. Some people believe that this should be called halting but I disagree. I call this 'exiting', or at best an implied halt. This is because control is passed back to the machine itself which might have been designed to halt in such a scenario, or it might have been designed to restart from the first line of code. In other words, whether or not it halts or loops would be machine-specific rather than program-specific.
Now if such a thing as a Turing machine could exist, and if it could do anything that a modern-day real world computer can do, then it would be able to do an explicit HALT. However, if it were to lack this capability, then it would be inferior to real world computers in many aspects, not least of which is that it would be defeated by the logic of the halting problem proof. And of course, it could not be considered to be the only model of computing that is required because it lacks this key feature (of an explicit halt) that is present in so many real world computers.
A so-called 'Turing Machine' is neither use nor ornament if it can't be used in relation to real world computation tasks. It is often claimed that Turing's proof of undecidability tells us that it must be impossible to develop a halt/loop decider program on any real world computer. I hope this video has cast some doubt on the validity of that claim.
So the specification of the halting problem is flawed if it does not cater for machine-level halt commands because many real computers can perform this type of operation. Therefore the objection that this 'explicit halt' argument does not follow the specification is a moot point. Nobody should be following the specification if the specification is flawed. A real computer can write its output to a text file (or a printer or whatever) and then halt the machine.
What matters is that H produces the correct prediction, not whether or not it is capable of being called by another program or whether or not it can return a true/false value to a calling program.
Note that that we can have very low-level languages that are so-called 'Turing complete' which do not inherently contain any mechanisms for defining procedures or functions or returning values from these things. These days we take it for granted that we can call functions and get values returned, but in relation to the simplest of instruction sets these are high-level mechanisms that might involve moving data around in various registers and to and from designated areas in memory that have been given specific names such as stacks and heaps etc. I expect that a machine-level halt command would be a very simple operation in comparison to these complicated mechanisms.
Should the real program H ever exist, another program would be free to initiate it (or 'call' it). However, this would present a problem if the initiating program wanted to do something else afterwards, because the real program H will end with a machine-level halt (or at least it will if its input program tries to execute equivalent logic to real H).
And so say that program Z invokes H(X, X), then, given that X tries to execute the logic of real H, functionality H(X, X) will decide "It will halt" and then it will do a machine-level halt. There is nothing to stop us from starting the machine up again, feeding the output produced by H into functionality Z and executing the rest of the logic Z so that it uses the decision made by the real H.
Of course it would be very inconvenient to have to re-start the machine every time after H has run, and even more inconvenient to have to feed its result into another program rather than it all being done automatically. But H only needs to do a machine-level halt if its input tries to execute the logic of H. Also, the question that the halting problem asks, i.e. "does it halt", could be considered to be a very bad question if the type of halt it refers to is only the implied type of halt.
Note that this is similar to the Barber paradox in that it appears that the two options on offer are mutually exclusive and cover all options, when in reality they don't. The barber himself is not catered for in the Barber paradox just as an explicit halt is not catered for in the halting problem logic. This is why the halting problem question is a bad question.
Some people might still claim that the halting problem remains undecidable even with a real world machine equipped with the 'shutdown' instruction because, by definition, the program H could never use this instruction. However, I believe this is like saying it is impossible to switch on a real world computer because someone, a long time ago, wrote a specification that says you are not allowed to press a button that would switch on an imaginary computer. In other words, in my opinion it is not good logic.
It's a trick of language to say that a machine "might be designed to do such and such" and implying that's somehow *different* from a program instruction in any practical sense. You can quibble over the origin of the instructions, but fact is, whether a machine is looping, halting or "exiting" - it is following some instruction.
If the machine halts, then the action of halting is the last instruction it will perform. That's how halting is / should be defined. Any other definition is sophistry.
@Fictional_Name Many thanks for taking an interest in my video :)
You said:
It's a trick of language to say that a machine "might be designed to do such and such" and implying that's somehow different from a program instruction in any practical sense.
I'm glad you made this point as it made me really think about what a program actually is. It provided me with an opportunity to clarify my position on this matter. Here are my thoughts...
I've tried to imagine how your claim might be realised in a 'practical sense' as you say. I suppose rather than having a distinction between program statements and a physical machine upon which it runs we could just have a single physical machine for each individual instruction. Then we could connect several of these machines together in order to make one big machine which would be analogous to a hard-coded program. In this sense it can appear that the 'program' and the 'machine' are one and the same thing.
So when we focus on what a machine actually does, it can appear that the two concepts of 'machine' and 'program' are one and the same thing. However, if we focus on what a 'program' really means then we might reach a different conclusion.
If we think of a program instruction as being something physical (such as a punched card), which is interpreted by the machine and so on, then it is effectively an integral part of the physical mechanism. And so yet again your claim would appear to be correct.
However, if we use a more dubious definition for the word 'program' then we might be able to draw a distinction between the two concepts. For example, we might describe it as a formal description of the operations performed by the machine. With this interpretation we have a clear distinction between the two concepts; one is a physical machine and the other is a formal (i.e. well-defined and thus unambiguous) description of the operation of the machine.
If you reject this definition of a 'program' then wherever I have used this word you might replace it with 'description of operation'. I believe my argument would then still hold. After all, the one thing that we can't escape from is the necessity for a physical machine to exist. Even when someone dry-runs an algorithm in their head, the hardware and wetware of their brain will form the physical machine. And so the need for there to be a physical machine is a practical necessity in all cases of computation.
With the apparent 'abstract' nature of Turing Machines people might imagine that programs (or 'descriptions of machine operations') can somehow be thought of as being able to execute all by themselves. They might believe that there is no need to include a device that processes the instructions and hence no need for a 'machine halt' instruction. But program instructions (or 'descriptions of operation') don't just work by magic. And so when we relate the halting problem proof to a real-world computing scenario we could deduce that there is a clear distinction between the 'descriptions of operation' and the physical machine.
You said:
If the machine halts, then the action of halting is the last instruction it will perform. That's how halting is / should be defined. Any other definition is sophistry.
I'm not sure I understand you. Your definition of halting seems to include the word 'halts' and I'm struggling to understand what this means in a real-world scenario. Do you mean that if the machine stops executing instructions then we can say it has halted? If so then I completely agree with you. So if it 'exits' one section of code and proceeds to execute instructions in another section of code then it has not halted. I make this point in the video.
Note that this does not prevent the existence of a type of instruction of the form "stop now and do not perform any further instructions" (i.e. a 'machine halt' instruction). If this type of instruction is allowed then my argument still holds; the halting problem proof is not a valid proof.
@@KarmaPeny Well I'm happy my comment could help you clear your thoughts more on the matter, that's rare these days.
I agree with all you had to say about programs and machines executing them requiring a physical manifestation. A curious consequence of this picture though, is that no machine truly "loops" forever, since the universe has a finite amount of energy. But that's just a fun sidetrack.
What I take issue with, is that you categorise "exiting" as a form of halting. When really you don't know if the new instruction will end up in a loop, or a traditional "stop" halt. If the new instruction were to end up in a loop, why wouldn't you categorise it as such? This just makes no sense in my view. It's violating the spirit of what it means to halt. To not execute further instructions. You can't simply define a new instruction set for the machine to execute, and say that because it's no longer executing the old instructions, therefore it has "halted" in some new fashion you call exiting.
The machine does not know what it does. It does not know what instructions it executed in the past, or the future. It cannot distinguish between instructions and their source. (Be it inputs or part of the machine's "design" as you call it)
It can either read the instruction and execute it succesfully, or not. Its parts (the turing head in particular in the case of Turing machines) are either moving, or they're stationary. I'd like us to define a machine as halted, if it is stationary. Or if that's too strict, an alternative definition such as "the absence of instruction-caused motion" is fine with me as well. But I cannot allow you to define a type of halting where the machine continues executing programs, that, to me, is absurd.
Now, you mention that we could think of each program instruction as its own machine, and that's all well and good, but I am not sure how it helps your case. Each machine needs to have an input before it can execute any program. If one machine halts, then the other machines in the chain won't receive their inputs. It does not matter what you want the machine to do, or how confident you are it does it, once you feed it some input or program, *if the machine never receives said input* .
Somehow, some way, that input (which contains information about itself) has to be physically transmitted to itself, from itself. And it cannot have that information without running the program first, so it halts. And using my definition for halting, it by definition cannot transmit information about its state to other machines, including itself. And if we assume it somehow doesn't halt, and loops instead, what good does that do? Arguably if it is looping infinitely, then much like we never reach the final digit of an infinite series, we never reach the end of the loop, we never get an output from the machine to use as input.
It's in this sense I understand that mathematicians (which I know you aren't fond of) have come to the understanding that it is undeterminable, whether machine H will halt or not. You should be wary of your contrarianism. Being a dogmatic sheep that believes the consensus opinion because they trust the experts, is of course flawed. But it is equally flawed to be a dogmatic black sheep that disbelieves the consensus opinion because they distrust the experts. Both are two sides of the same coin. Let the arguments speak for themselves, don't be swayed either way by the popularity or acceptance of said arguments.
I'll end by saying the halting problem is not unique. It's part of a class of problems in mathematics that all stem from self-referential statements. It is well known these types of statements result in paradoxes.
@Fictional_Name
You said:
What I take issue with, is that you categorise "exiting" as a form of halting.
I don't want to; I prefer to have the three categories of 'loop', 'halt' and 'exit'. When I include it as a type of halting I'm just trying to sympathise with the viewpoint that the halting problem question is mutually exclusive and covers all possibilities.
Decision problems should be mutually exclusive and cover all possibilities, and so if the two options are 'loop' and 'halt' then in order for these to cover all possibilities the best we can do is pretend that 'exit' is another category of halting. But I don't really believe it should be categorised as halting. I'm just trying to help the opposing viewpoint so as to be extra critical of my argument.
You said:
When really you don't know if the new instruction will end up in a loop, or a traditional "stop" halt. If the new instruction were to end up in a loop, why wouldn't you categorise it as such? This just makes no sense in my view.
My three categories of 'loop', 'halt' or 'exit' apply to a specified section of code, not to any subsequent section of code (or machine functionality). If the first section of code goes to a 'loop' or 'halt' state then the processing will never reach any subsequent section of code. If processing exits the first section of code then the status of 'exit' applies to that first section of code regardless of what any subsequent section of code does.
Don't forget that the halting problem proof requires us to take the halt/loop decider, H (which we might call our 1st section of code) and use it in a program X by adding a section of code to run after the first section of code (which will try to contradict the output of H).
So if H ends by stopping the machine, then it will prevent the subsequent section of code from executing - and so X cannot contradict H.
You said:
You can't simply define a new instruction set for the machine to execute, and say that because it's no longer executing the old instructions, therefore it has "halted" in some new fashion you call exiting.
I'm not inventing any new instructions. I don't understand why you think I am.
You said:
The machine does not know what it does. It does not know what instructions it executed in the past, or the future.
I've never claimed anything like the machine 'knowing' such things.
You said:
It can either read the instruction and execute it succesfully, or not. Its parts (the turing head in particular in the case of Turing machines) are either moving, or they're stationary. I'd like us to define a machine as halted, if it is stationary. Or if that's too strict, an alternative definition such as "the absence of instruction-caused motion" is fine with me as well. But I cannot allow you to define a type of halting where the machine continues executing programs, that, to me, is absurd.
Again, I agree that existing a section of code should not be called halting. We agree on this point. I agree that halting should mean stopping. We are in complete agreement on this. I was only trying to play devil’s advocate in order to help those people who still think the halting problem proof is valid.
You said:
Now, you mention that we could think of each program instruction as its own machine, and that's all well and good, but I am not sure how it helps your case. Each machine needs to have an input before it can execute any program. If one machine halts, then the other machines in the chain won't receive their inputs. It does not matter what you want the machine to do, or how confident you are it does it, once you feed it some input or program, if the machine never receives said input .
We are in complete agreement on this. I don't know why you think we differ.
You said:
Somehow, some way, that input (which contains information about itself) has to be physically transmitted to itself, from itself. And it cannot have that information without running the program first, so it halts.
As I say in the video, most people believe this kind of self-reference results in a type of looping. But should a halt/loop decider program exist then it should never go into a loop itself. Therefore it would need to analyse its input data in order to determine if it contains this type of self-reference, then it could print "It will halt" and then do a machine halt.
You said:
And using my definition for halting, it by definition cannot transmit information about its state to other machines, including itself.
I agree that if program instructions are no different to physical machines (that execute instructions) then the matter of 'input data' becomes problematic. However, if we allow my dubious definition by which a program is a formal description of what the machine does, then this description could be fed into a machine as input data.
You said:
You should be wary of your contrarianism. Being a dogmatic sheep that believes the consensus opinion because they trust the experts, is of course flawed. But it is equally flawed to be a dogmatic black sheep that disbelieves the consensus opinion because they distrust the experts. Both are two sides of the same coin. Let the arguments speak for themselves, don't be swayed either way by the popularity or acceptance of said arguments.
I always justify my arguments with what I consider to be good reasoning. I never claim that the consensus opinion is wrong on the basis that we should distrust the experts. I completely agree that we should not be swayed by the popularity of any particular viewpoint.
You said:
I'll end by saying the halting problem is not unique. It's part of a class of problems in mathematics that all stem from self-referential statements. It is well known these types of statements result in paradoxes.
Yes, but the apparent paradoxes are only paradoxical due to the belief in non-physical mathematical existence, which itself is an absurdity in my opinion, or by tricks of logic where mathematicians have unwittingly managed to fool themselves.
For example, consider the infamous liar's paradox which is the sentence "this sentence is a lie". The argument goes like this... If the sentence were true, it would be a lie. But if it were a lie, it would be true. This is a logical inconsistency.
The problem here is what does the sentence "this sentence is a lie" really mean; what does it mean to say that a particular sentence is a lie? Let's consider a different sentence...
Consider the statement "Bishop Stubbs was hanged for murder". If we consider this sentence as making an assertion about something in the real world, then we can examine the evidence to determine if this assertion is true or false. But the sentence itself is just a sentence, it has no truth property.
Since the only real-world reference in "this sentence is a lie" is a self-reference to the sentence itself which has no intrinsic true or false (i.e. lie) property, we can only conclude that the sentence is intelligible. A statement would have to be comprehensible for it to be deemed to convey an inconsistency.
And so the problem specification gives the impression that the two options of 'true' or 'lie' cover all possibilities when the reality is they don’t. The option of 'sentence is incoherent' is not supplied and yet it is the only applicable option out of the three.
Another problem similar to the halting problem is the Barber paradox, where it is the specification of the problem that is the very thing that causes the problem. The specification says we must choose between 'shave themselves' and 'shaved by the barber'. These two options appear to be mutually exclusive and cover all possibilities. The trick is one of wordplay because the specification doesn't allow us the third option of saying 'do both by being the actual barber'.
When we hear the logic of the Halting Problem proof it sounds like a sneaky trick. Indeed, it sounds very much of the same nature as the Barber paradox trick and the liar's paradox. It makes it sound like the two options that it specifies are mutually exclusive and cover all possibilities when in reality they don't cover all posibilities. In this respect the Barber paradox, the liar's paradox, and the Halting Problem are all just variations of the same underlying logic trick.
WHY THE RE-RELEASE????
I'm sorry, but I made a typo in the original that was really bugging me. At 7:16 which is at the end of my explanation of the original proof, the last line of the proof changes from "exist" to "exit" (in the original), which of course it shouldn't do!
Interesting vid.
When do you think you'll have another video put out? I'm curious if you have thought of more stuff concerning .999... since your last video about it.
I plan to work on some more videos in the two to three months. Sadly no matter how many videos I produce about 0.999... they seem to have little impact. So I'm thinking that I need to make less subtle points about the foundational problems in future videos. For example, we can't 'imagine' an 'infinitely thin' line; an unending sequence of non-zero digits can never become a constant, and so on.
Ok 👍
"Does it execute an accurate version of my functionality" seems very likely to be undecidable?
It might be decidable, it might not be. But the core logic of the halting problem proof is that it doesn't matter if you can detect that H logic is being used since X can always do the opposite of what H says. And so whether or not "Does it execute an accurate version of my functionality" is decidable is not relevant to whether or not the logic of the halting problem proof is correct.
The Wikipedia page on the halting problem says:
"...the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program-input pairs."
And so in the halting problem we are given two apparently mutually exclusive categories: 'finish running' and 'continue to run forever'. If we use the categories 'halt' and 'does not halt' then it seems obvious that these must be mutually exclusive. But could it be that hidden in our interpretation of the word 'halt' we are not covering all possibilities?
We all know that 'halt' means 'stop' but are we talking about stopping the machine, stopping the program, or even just exiting from the program (& thus implying that processing stops)? Here we have three different possible interpretations of what 'halt' might mean. The halting problem proof seems to assume that 'halt' only means the third of these options. It seems to me that the core argument of the proof would not work if we took the other possible meanings of 'halt' into consideration.
To relate this back to what the halting problem was meant to address, David Hilbert's question of "is mathematics decidable", we might consider that "mathematics" and "a Turing-complete computer programming language (i.e. a demonstrably well-defined formal language)" are interchangeable. We might also take into account that the halting problem proof is a proof by contradiction, which means that it highlights a problem, but does not identify what that problem is.
Then we could argue that the proof highlights that there are problems which cannot be solved by programming languages that lack the ability to perform halt instructions such as 'stop the machine' and 'stop the program'. But the logic of the halting problem proof does not prove that there are undeniably unsolvable problems.
Worth more than one watch, for sure!
More videos please thank you
That's my objective, but they can take some time.