Past exam question: 2082 Chaitra (Regular), Q14(a)
Open in the Padhaiko appQuestion
State halting problem.
Solution
Formal Statement of the Halting Problem: The Halting Problem is the decision problem of determining, given an arbitrary Turing Machine and an input string , whether will eventually halt (either by accepting or rejecting) when run with input , or will run forever in an infinite loop.
As a formal language:
Alan Turing proved in 1936 that the Halting Problem is undecidable: there cannot exist any general algorithm or Turing Machine that correctly decides for all possible machine-input pairs .
Answer:
The Halting Problem asks whether an arbitrary Turing Machine halts on input . It is proven to be undecidable, meaning no general algorithm exists that can solve it for all pairs.