Decidability

Table of Contents

Regular < Context-Free < REC < RE

R(real number) is uncountable

  1. list every pair of (1, r1), (2, r2), …
  2. construct a R: 第一位和r1不一样，第二位和r2不一样，。。。

1 Cardinality argument

  • There're uncountably many languages.
  • There're only countably many RE
  • There're only countably many co-RE

languages are uncountable

Sequence of binary of uncountable. The same as R. Then for every language A: 

all string={x, 0, 1, 00, 01, 10, ...}
A         ={   0,    00,     10, ...}
output    ={0, 1, 0, 1,  0,  1,  ...}

So the language is converted to a binary sequence.

TMs are countable

all strings are countable: we can write down string in standard order.

A TM can encode into a string.

some language is not RE

Because there're uncountable languages, but countable TMs.

2 An undecidable language: ATM

Suppose it is decidable. H decides it. 

D=On input <M>:
  1. Run H on <M, <M> >
  2. Output opposite.

Run D on <D> will get contradiction.

REC <=> RE and co-RE

  • =>: easy
  • <=: run M1 M2 on w in parallel

To prove co-RE: prove not REC and is RE.

3 Rice's theorem

Let P be any non-trival property of language. Prove that determining a language has in P is undecidable.

  1. Assume R decide P
  2. P is non-trival, we can assume `\( \in P\)`(`\(L_{T0} = \phi\)`).

Otherwise we take `\(P^c\)` into consideration.

  1. There exists a `\( \in P\)` while `\( \not\in P\)`.
  2. Construct a TM to decide `\(A_{TM}\)`:
On input <M,w>:
  M' = on input x:
    M(x) reject => reject;
    M(x) accept => act like T
    M(x) loop => loop
  run R on <M'>. If accept, accept. Otherwise reject.
  • if M(w) accept, M' is the same as T, the TM accept.
  • if M(w) reject, M' is empty(`\(\)`), the TM reject.

Thus the TM can decide whether M accept w, which is `\(A_{TM}\)`. And `\(A_{TM}\)` is undecidable.

4 Problems

A is RE: {<M1>,<M2>,…}. Every Mi is decider. Prove that some decider D is not in any of Mi

We need to construct D to differ from every Mi. 

On input w:
  The index i of w in standard string order.
  run Mi on w, if accept, reject. Otherwise accept.

> L separates (A,B) is `\(A \subset L\)` and `\(B \subset L^c\)`. > Let `\(A,B \in co-RE\)` be two disjoint languages. > Show that there is a decidable language separate (A,B).

`\(A \in co-RE\)` => `\(A^c = L(M_1)\)`

A,B disjoint => no string w both in A and B

Run M1, M2 on w in parallel, see which one halts first. Then do something. One of them must halt.

> Prove that K in RE <=> there exists L in REC s.t. K={x | exists y s.t. <x,y> in L}

  • =>: on input <x,y>, convert y into a index t, run Mk on x for t steps.
  • <=: E enumerates <x,y> in y's standard order. Run Ml on <x,yi>