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)
Latest Answers