19. Undecidable Problems

Mar 8, 2022

Undecidable language $L$ : there is no TM that accepts $L$ and halts on every input
- it may halt and decide for some inputs
For an undecidable language, the corresponding problem is undecidable (unsolvable):
- there is no TM (algorithm) that gives and answer (y/n) for every input instance
- answer may be given for some inputs.
We will show that two particular problems are unsolvable: membership problem and halting problem.

Membership problem

Input: Turing machine $M$ and string $w$ => Does $M$ accept $w$ , i.e. $w \in L (M)$ ?

Corresponding language: $A_{T M}$ = { $< M, w >$ where M is a TM that accepts string $w$ }.

Theorem: A $_{T M}$ is undecidable => membership problem is undecidable.

Proof. Basic idea: we will assume $A_{T M}$ is decidable. We will then prove that every Turing-acceptable language is also decidable => a contradiction.

Suppose $A_{T M}$ is decidable. Input string: $< M, w >$ , we have some decider $H$ for $A_{T M}$ , if the output is yes, $M$ accepts $w$ . If output is no, $M$ rejects $w$ :

input <M, w>
               A_TM decider
      <M> ---> |=========|---> yes  M accepts w
               |    H    |
        w ---> |=========|---> no   M rejects w

Let $L$ be a Turing-acceptable language and let $M_{L}$ be the Turing machine that accepts $L$ . We will prove that $L$ is also decidable by building a decider for $L$ . Building such decider means $L$ is decidable.

       ╭ String description of M_L:
       | this is hardwired and copied to the tape next to
       | input string s, and then the pair <M_L, s> is input to H
       |
       |     Decider for L
    |==|==========================|
    |  |                          |
    | <M_L> --> |=========|- yes ---->  M accepts w (and halt)
    |           |    H    |       |
s  -----------> |=========|- no ----->  M rejects w (and halt)
    |                             |
    |=============================|

Since $L$ was chosen arbitrarily, every Turing-acceptable language is decidable. But there exists a Turing-acceptable language that is undecidable => contradiction.

A $_{T M}$ is undecidable

By construction, A $_{T M}$ is also Turing-acceptable. Design a TM that accepts it: For input $< M, w >$ run $M$ on input $w$ . If $M$ accepts then accept $< M, w >$ .

Halting problem

Input: Turing machine $M$ and string $w$ => Does $M$ halt while processing input string $w$ ?

Corresponding language: Halt $_{T M}$ = { $< M, w >: M$ is a TM that halts on input string $w$ }.

Theorem: Halt $_{T M}$ is undecidable => halting problem is undecidable.

Proof 1

(This proof relies on there exists a Turing-acceptable language that is undecidable)

Basic idea: Suppose that Halt $_{T M}$ is decidable; we will prove that every Turing-acceptable language is also decidable => a contradiction.

Support that Halt $_{T M}$ is decidable. Then for input string $< M, w >$ there exists a decider for Halt $_{T M}$ . If decider outputs yes, $M$ halts on input $w$ . If decider outputs no, $M$ does not halt on input $w$ :

input <M, w>

      <M> ---> |=========|---> yes  M halts on w
               |  HALT   |
               | decider |
        w ---> |=========|---> no   M does not halt on w

Let $L$ be a Turing-acceptable language and let $M_{L}$ be the Turing machine that accepts $L$ . We will prove that $L$ is also decidable by building a decider for $L$ :

            Decider for L
    |==============================|
    |                              |
    |           |===========|      |
    | <M_L> --> | M_L halts |- no --------> reject s and halt
s  -----------> | on s?     |      |
    |           |===========|- yes |
    |                             |       |
    |          ╭————————————————╯      |
    |          |                   |
    |    |=====|====|              | 
    |    | Run M_L  |- acc + halts -------> accept s and halt  
    |    | with s   |              |
    |    |==========|- rej + halts -------> reject s and halt
    |                              |    
    |==============================|

Therefore L is decidable. Since L was chosen arbitrarily, every Turing-acceptable language is decidable. But there is a Turing-acceptable language that is undecidable => contradiction.

Proof 2

(This is a self-contained, alternative proof)

Basic idea: assume for contradiction that the halting problem is decidable. We will obtain a contradiction using diagonilization technique.

Suppose Halt $_{T M}$ is decidable and there exists a decider $H$ for Halt $_{T M}$ .

input <M, w>
             Decider for Halt
      <M> ---> |=========|---> yes  M halts on w
               |    H    |
        w ---> |=========|---> no   M does not halt on w

Look inside $H$ : input string $< M, w >$ in H has paths to accept and reject states.

            Decider for Halt
        ===================================
        | H                               |
        |    ╭----------- q_accept (yes)  |
        |    |                            |
<M, w> --->  Q0    M halts on w?          |
        |    |                            |
        |    ╰----------- q_reject (no)   |
        |                                 |
        ===================================

Construct machine $H^{'}$ : If $M$ halts on input $w$ , then loop forever, else halt.

           ========================================================
           | H'                                                   |
           |     ===================================     loop     |
           |     | H                               |    forever   |
           |     |    ╭----------- q_accept (yes) ---- qa <--> qb |
           |     |    |                            |              |
<M, w> ------------>  Q0    M halts on w?          |              |
           |     |    |                            |              |
           |     |    ╰----------- q_reject (no)   |              |
           |     |                                 |              |
           |     ===================================              |
           ========================================================

Construct machine $F$ that takes as input $M$ , copies $M$ on tape, and $< M, M >$ is given as input to $H^{'}$ . If $M$ halts on $< M >$ then loop forever, else halt.

        =======================================
        | F                                   |
        |  ============             ======    |
        |  | Copy <M> |   <M, M>    | H' |    |
<M> -----> | on tape  | ----------> |    |    |
        |  ============             ======    |
        =======================================

Now run $F$ on input itself:

        =======================================
        | F                                   |
        |  ============             ======    |
        |  | Copy <F> |   <F, F>    | H' |    |
<F> -----> | on tape  | ----------> |    |    |
        |  ============             ======    |
        =======================================

If $F$ halts on input $< F >$ then $F$ loops forever on input $< F >$ , else $F$ halts on input $< F >$ => contradiction.

Halt $_{T M}$ is undecidable.

Halt $_{T M}$ is also Turing-acceptable by construction. Create a machine that accepts Halt $_{T M}$ : Run $M$ on $w$ . If $M$ accepts $w$ then accept $< M, w >$ .