I watched videos and read about it but I still don’t understand why is important and proof of it. Can you please explain me what it is?
Thanks
In: 60
Imagine a computer program that prints out all the digits of Pi then stops. We know that Pi goes on forever, so this program will never stop.
But imagine we have a number that we don’t know if it goes on forever. If you had a program that prints all the digits we wouldn’t know if it would keep going or eventually stop. You could leave it running 100 years but still wouldn’t know if it would stop the next day.
That’s what the halting problem is about, it’s a proof that you can make a computer program that you can’t know if it’ll run forever or stop.
Why it’s important is it leads on to other proofs that we can’t know the complexity of all algorithms and that some algorithms probably don’t have simple answers (eg. Traveling salesman problem)
Looks like we can add ‘predicting the future’ to the list of things computers are terrible at.
Guess I’ll just stick to making programs that never end. In a way, they already solve the halting problem.
As @ruidh explains, it is considered to be important because it supposedly answered a really important question concerning the fundamental nature of mathematics. Not only that, but it gave us an imaginary model of computing, the ‘Turing machine’, that was supposedly the only model of a computer that would ever be needed by mathematics. Furthermore, it could be argued that this was a momentous event in the history of computing as there were no electronic computers at the time and Alan Turing himself went on to develop computers during the second world war.
In reality it is a monumental mistake and an example of very bad logic!
As for watching videos and reading about it, I recommend that you try this: https://www.reddit.com/r/AdvertiseYourVideos/comments/14dl5ee/about_the_what_computers_cant_do_argument/
Alan Turing’s halting problem proof is a clever trick in the same way that the barber paradox is a trick. In the barber paradox it is claimed that the barber is the “one who shaves all those, and those only, who do not shave themselves”. This creates the apparent paradox of who shaves the barber… does he shave himself or not? Either answer seems to result in a contradiction. The trick is that the two categories, ‘shave themselves’ and ‘shaved by the barber’ appear to be mutually exclusive and cover all possibilities when in reality they don’t. When we consider the barber himself it becomes clear that the two categories are not mutually exclusive.
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 we have a strong similarity to the barber paradox because in the halting problem we are given two apparently mutually exclusive categories : ‘finish running’ and ‘continue to run forever’ which are usually described as ‘halt’ and ‘loop’ (or even ‘halt’ and ‘does not halt’). Then the proof (of undecidability) creates a scenario where there are two choices that both lead to contradiction, just like the barber paradox.
The trick is hidden in our interpretation of the word ‘halt’. We all know that ‘halt’ means ‘stop’ but are we talking about stopping the machine (e.g. via a ‘shutdown’ instruction), 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 assumes that ‘halt’ only means the third of these options. Worryingly the proof does not work when we take the other possible meanings of ‘halt’ into consideration.
However, nobody noticed this issue with the meaning of ‘halt’ and so the people in positions of academic authority decided that this proof was a valid proof. Once a decision like this has been decided by the experts then it becomes almost impossible to overturn. Anyone who points out any flaw will be told that they don’t understand the problem. They might be told, for example, that they are not adhering to the original specification and if they did then they would realise that the proof is flawless.
But the original proof (together with its imaginary so-called ‘Turing Machine’) is neither use nor ornament if it can’t be used in relation to real world computation tasks. To that end, it is 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. This is a false claim because the proof is invalid.
When the halting problem was first devised (in 1936) they could not easily relate the problem to a real world electronic computer because such things did not exist. Compared to the lay person descriptions that we see in today’s videos, the original proof was quite complicated and was more closely related to finite state machines than today’s high-level computer programs. So it was quite easy for the mathematicians of those times to miss the fact that an ‘instruction set’ might include instructions such as ‘stop the program’ or ‘stop the machine’. And if the imaginary Turing machine is incapable of doing these types of instruction then it does appear that the halting problem proof is correct for Turing machines. But real world computers CAN do things like a machine ‘shutdown’ via software instructions. This means that real world computers cannot be modelled by imaginary Turing machines. It also means that the halting problem proof does not work when applied to real world computers.
The ‘experts’ have fooled themselves through their acceptance of the logic of an argument about ‘halting’ without first having a clear understanding of what ‘halt’ actually means in the real world. In mathematics, they often work with symbols that, they claim, might have no real world meaning and this is why it is very easy for mathematicians to fool themselves in this way.
Latest Answers