PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q14(a)

Theory of Computation · 1 marks

Open in the Padhaiko app

Topic: Church–Turing Thesis, Universal TM & the Halting Problem

Question

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.

All past exam questions for Theory of Computation