TOC-Undecidability and Reducibility

Halting Problem

Formally , Mr. Naive wants to design a TM to decide ( not recognize ) the language.

However, this is only Mr. Naive’s daydreaming. This problem is mission impossible.

Theorem

HALT is undecidable.

The sketch of the proof is as follows.

  • Assume is decidable.
  • Thus, there is a TM decides .
  • Construct a string in such that
    • accepts only if rejects , and
    • rejects only if accepts ;
      which is a contradiction.

Reduction

To prove “a language is undecidable” is not easy at all.

The idea of reduction is rather simple. It is used to prove one problem (deciding a language ) is no easier than another problem.

Assume we want to reduce problem to problem .
First, we assume is "solvable". Then, there must be a machine to solve .
Next, we try to construct a machine to solve by making function calls to .
Those function calls are like an oracle in a blackbox.
In consequence, if solves , then solves .
The conclusion will be "if B is solvable, then so is A".
Intuitively, problem is no easier than .
And we denote .

Table Of Contents
TOC-Undecidability and Reducibility
Halting Problem
Reduction