## [ITOC-ch4] DECIDABILITY

Recall:

**Recognizer**

- if $ w∈L $, than M must accept w.
- if $ w∉L $, than M may loop when input w.

**Decider**

- if $ w∈L $, than M must accept w.
- if $ w∉L $, than M must reject w.

### 4.1 DECIDABLE LANGUAGES

**DECIDABLE PROBLEMS CONCERNING REGULAR LANGUAGES**

$ A_{DFA} = \{ \ <B,w> \ | \ B \ is \ a \ DFA \ that \ accepts \ input \ string \ w \} $.

Proof that it’s a decidable language by designing a decider

- M = “On input <B, w>, where B is a DFA and w is a string:
- Simulate B on input w.
- If the simulation ends in an accept state, accept . If it ends in a nonaccepting state, reject .”

$ A_{NFA} = \{ \ <B, w> \ | \ B \ is \ an \ NFA \ that \ accepts \ input \ string \ w \} $.

Proof

- Convert NFA to DFA

$ A_{REX} = \{ \ <R, w> \ | \ R \ is \ a \ regular \ expression \ that \ generates \ string \ w \}$.

Proof

- Convert RE to NFA

$ E_{DFA} = \{ \ < A > | \ A \ is \ a \ DFA \ and \ L(A) = ∅ \} $.

Proof

- Mark all states reachable from start state. accept if no accept state is marked

$ EQ_{DFA} = \{ \ <A, B> \ | \ A \ and \ B \ are \ DFA \ s \ and \ L(A) = L(B) \} $.

Proof

- Construct L( C ) = L( A ) xor L( B ), test if L( C ) $ \in E_{DFA} $

**DECIDABLE PROBLEMS CONCERNING CONTEXT-FREE LANGUAGES**

$ A_{CFG} = \{ \ <G, w> \ | \ G \ is \ a \ CFG \ that \ generates \ string \ w \} $

*if G were in Chomsky normal form, any derivation of w has 2n − 1 steps, where n is the length of w.*

Proof

- List all derivations with 2n − 1 steps, check if w is in them

$ E_{CFG} = \{ \ < G > | \ G \ is \ a \ CFG \ and \ L(G) = ∅ \} $.

Proof

- Mark all terminal symbols and Mark all variables that can derive into marked symbols

$ EQ_{CFG} = \{ \ <G, H> \ | \ G \ and \ H \ are \ CFG \ s \ and \ L(G) = L(H) \} $.

Not decidable (P226)

Every context-free language is decidable.

Proof:

Use TM S that decide $ A_{CFG} $ ( if w is generated by G )

Let G be a CFG for the CFL A we want to decide

- Run S on <G,w>, if accept, means that $ w \in G $ therefore $ w \in A $, accept

### 4.2 UNDECIDABILITY

$ A_{TM} = \{ \ <M, w> \ | \ M \ is \ a \ TM \ and \ M \ accepts \ w \} $.

**THE DIAGONALIZATION METHOD**

**same size**

- Set A and set B are the same size if there is a correspondence f : A→B.

**countable**

Ex: $ Q = \{ \frac{m}{n} | m, n ∈ N \} $ is countable

**uncountable**

Ex: the set of real numbers $ R $ is uncountable

*using diagonalization method*

ensure that $ x \neq f (n) $ for any n, therefore the correspondence to $ N $ failed

**Some languages are not Turing-recognizable.**

Proof

Set of all Turing machines $ M $ is

**countable**(图灵机的个数 == 图灵机识别的语言的个数 == 自然数的个数)

each TM M has an encoding into a string \

- and set of all strings $ Σ^ ∗ $is countable ( set of
*finite length*strings )

Set of all languages $ L $ is

**uncountable**(所有语言的个数 == 实数的个数)

$ B $, the set of all

*infinite length*binary sequence, is uncountable as $ R $- $ L $, the set of all languages over alphabet $ Σ $, have a correspondence with $ B $
- Each language $ A ∈ L $ has a unique sequence in $ B $.

therefore $ L $ is larger than $ L_{TM}$

**AN UNDECIDABLE LANGUAGE**

$ A_{TM} = \{ \ <M, w> \ | \ M \ is \ a \ TM \ and \ M \ accepts \ w \} $.

$ A_{TM} $ **is Turing-recognizable**

- Simulate M on w
- If M ever enters its accept state, accept ; if M ever enters its reject state, reject ; If M loops, loop.

$ A_{TM} $ **is undecidable**

Proof

- Assume we have the decider $ H $ to decide whether M accept w

- construct a new TM $ D $ with $ H $ as a subroutine

- Contradiction when we run D with its own description \
as input

diagnolization in the proof

- first list the table of whether $ M_i $ accepts $ <M_j> $
- construct $ H $ so that $ H $ reject when $ M_i $ doesn’t accept $ <M_j> $
- Finally the contradiction in $ D $

**A TURING-UNRECOGNIZABLE LANGUAGE**

**A language is decidable iff it is Turing-recognizable and co-Turing recognizable.**

Proof

if $ A $ decidable, $ \bar A$ is decidable, therefore both are recognizable

if both recognizable, we can construct decider for $ A $, therefore $ A $ is decidable

Run their recognizer $ M_1 $ and $ M_2 $ simultaneously. If $ M_1 $ accepts, accept ; if $ M_2 $ accepts, reject.

$ \overline { A_{TM} } $ is not Turing-recognizable.