A QUESTION THAT COMPUTERS CAN NEVER ANSWER: THE HALTING PROBLEM

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Education Latest

Anand Kumar’s Bold Move: Online Education for India’s Underprivileged

Anand Kumar, the visionary behind Super 30 and renowned mathematician, is embarking on a new journey that promises to reshape the future for underprivileged students across India. In a groundbreaking announcement at the ‘2024 Kellogg India Business Conference’ organized by Kellogg School of Management, Northwestern University, Kumar unveiled plans for an online educational platform tailored […]

Read More
Education Latest

NLSIU Receives JSW Grant for Academic Block Redevelopment

  The National Law School of India University (NLSIU) has secured a significant grant from the JSW Group for the extensive redevelopment and expansion of its core Academic Block and Precinct. This grant will primarily focus on revamping the New Academic Block (NAB) situated in the southern area of NLSIU’s campus in Nagarabhavi, Bengaluru. Originally […]

Read More
Education Latest

CBSE Introduces Exam Format Changes for Classes 11 and 12 from 2024-25 Academic Year

  The Central Board of Secondary Education (CBSE) has made a significant announcement regarding changes in the examination format for Classes 11 and 12, effective from the academic year 2024-25. The move aims to overhaul the traditional examination system and align it with the objectives outlined in the National Education Policy, 2020. According to the […]

Read More