Skip to content

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_{TM}\) = {\(<M,w>\) where M is a TM that accepts string \(w\)}.

Theorem: A\(_{TM}\) is undecidable => membership problem is undecidable.

Proof. Basic idea: we will assume \(A_{TM}\) is decidable. We will then prove that every Turing-acceptable language is also decidable => a contradiction.

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

1
2
3
4
5
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. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
       ╭ 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\(_{TM}\) is undecidable

By construction, A\(_{TM}\) 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\(_{TM}\) = { \(<M,w> : M\) is a TM that halts on input string \(w\) }.

Theorem: Halt\(_{TM}\) 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\(_{TM}\) is decidable; we will prove that every Turing-acceptable language is also decidable => a contradiction.

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

1
2
3
4
5
6
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\):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
            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\(_{TM}\) is decidable and there exists a decider \(H\) for Halt\(_{TM}\). 

1
2
3
4
5
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. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
            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. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
           ========================================================
           | 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. 

1
2
3
4
5
6
7
        =======================================
        | F                                   |
        |  ============             ======    |
        |  | Copy <M> |   <M, M>    | H' |    |
<M> -----> | on tape  | ----------> |    |    |
        |  ============             ======    |
        =======================================

Now run \(F\) on input itself:

1
2
3
4
5
6
7
        =======================================
        | 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\(_{TM}\) is undecidable.

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