State and prove the halting problem

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015


For a given configuration of a TM two cases arise:

  • The machine starting at this configuration will halt after a finite number of steps .

  • The machine starting at this configuration never halts no matter how long it runs .

Given any TM ,the problem of determining whether it halts or not, is called halting problem.

To solve the halting problem, we should have some mechanism such that for any given configuration of a TM, we should be able to determine whether the machine will ever halt or not .In reality, one cannot solve the halting problem. The halting problem is unsolvable .This means there exists no TM which can determine whether the given TM 'T' will ever halt or not .

Consequences of halting problem:

  • It cannot be decided whether a TM ever print a given symbol of its alphabet. This is also unsolvable.

  • Two TMs with the same alphabet cannot be checked for equivalence or inequivalence by an algorithm i.e. there is no effective general way to decide whether a given computational process will ever terminate or whether two given processes are equivalent. This is also another unsolvable problem.

  • Blank-tape theorem: There exists a TM which when started on a blank tape, can write its own description . This is of interest in constructing self-reproducing machine.

Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.


Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More