0
State and prove the halting problem

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015

0
0

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.

0