Since the dawn of a new generation; my generation, the pioneering technology has escalated to heights resulting in advancements that the great civilizations of antiquity could have only dreamt of. Advancements include – the formulation of AI, cloud computation, and augmented reality, things which may be SO perplexing if probed deeper. However, the roots originate back to algorithms, and programs for these successful endeavors. In this stage of life, computers can drivecars, land a rover on Mars, and whatnot. It seems that the computer might be the ‘know it all’ after all. And that’s where the Halting problem comes in.
The Halting problem asks whether there exists a specific algorithm that, given a set of instructions as input for any computer program, can accurately determine whether the program will halt or run indefinitely. The Halting problem is not a statement about intelligence (human or artificial), it is a statement about the limits of mathematics. In 1936, the brilliant mathematician and code breaker Alan Turing proved that the halting problem over Turing machines is undecidable using a Turing machine; that is, no Turing machine can decide correctly (terminate and produce the correct answer) for all possible program/input pairs.
Now this may not seem of much great significance, however, Jade Tan-Holmes gives a fascinating example of Goldbach’s conjecture to explain the importance of the Halting Problem.
Goldbach’s conjecture states that each even number greater than 2 can be represented as the sum of two primes.
4=2+2, 6=3+3, 8=3+5, and so on…
Let’s consider a program (P) with an input (I) that starts inspecting every even number and verifying that it is the sum of two prime numbers. If it ever finds one that is not, it just halts and returns that number. If it never finds one, it hangs and runs forever. We can then simply ask whether P halts. If so, Goldbach’s conjecture couldn’t be any further away from the truth otherwise Goldbach’s conjecture is true.
So?
So solving the Halting Problem would give us solutions to lots of problems that have stumped the world’s greatest mathematicians for decades, but despite that, this is not proof that we cannot solve the Halting Problem, it just provides some intuition that we may not be able to do so, or at the very least, doing so would be extremely hard to do. To use an analogy by Scott Aaronson, “If you bet a friend that your watch will never stop ticking, when could you declare victory?”
Such paradigms are historical rarities, whose solution one couldn’t possibly comprehend or should I say ‘AI’ couldn’t possibly comprehend. Who knows what the future holds? Since AI’s cognitive capabilities are ascending at an exponential rate, it might not seem impossible after all in the later centuries to devise a meticulous conclusion for the Halting problem.
Author – VARYA AGGARWAL
