**Unsolvability of The Halting Problem**

Assume that * P* is a Turing
machine that takes as input the encoding

0 |
if T does not halt on
input t |

1 |
if T halts on input t. |

Use * ***P** to build
a Turing machine * ***Q** that takes as input the encoding **T*******
of a Turing machine * ***T** and an input * ***t** for that
Turing machine and that halts exactly when * ***P** outputs a 0.
the result of executing * ***Q** is:

halts |
if T does not halt on
input t |

fails to halt |
if T halts on input t. |

halts |
if T does not halt
on input T* |

fails to halts |
if T halts on input
T* |

What happens when

is givenSas input?S*

haltsifSdoes not halt on inputS*fails to haltsifShalts on inputS*

This table embodies a contradiction.

The whole proof is a variant on the old Liar's Paradox:

**I am (always) a liar. **

**Is this statement true
or false?**

CS1104 Main Page

Last Updated 01/05/2000

© L.Heath, 2000