## [ITOC-ch5] REDUCIBILITY

If A reduces to B

• we can use a solution to B to solve A
• solving A is no harder than solving B

$A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable)$

$A \ (undecidable) \longrightarrow B \Rightarrow B \ (undecidable)$

### 5.1 UNDECIDABLE PROBLEMS FROM LANGUAGE THEORY

General Idea

• Contradiction on $A \longrightarrow B \ (decidable) \Rightarrow A \ (decidable)$

• If we have a TM R that decides $HALT_{TM}$ ( or sth ).

• Then we can use R to construct a TM S that decides $A_{TM}$

• thus obtain a contradiction.

$A_ {TM} ≤_m HALT_{TM}$

$HALT_{TM} = \{ < M, w> \ | \ M \ is \ a \ TM \ and \ M \ halts \ on \ input \ w \}.$

Proof

If M loop on w, we can use R to reject.

S = “On input $<M, w>$, an encoding of a TM M and a string w:

1. Run TM R on input $<M, w>$.
2. If R rejects, reject .
3. If R accepts, simulate M on w until it halts.
4. If M has accepted, accept ; if M has rejected, reject .”

$A_ {TM} ≤_m E_{TM}$

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

Proof

If $L (M_1)$ is empty, than M accept w

S = “On input $<M, w>$, an encoding of a TM M and a string w:

1. Construct $M_1$ = “On input x:
2. If $x \neq w$, reject .
3. If $x = w$, run M on input w and accept if M does.”
4. Run R on input $< M_1 >$.
5. If R accepts, reject ; if R rejects, accept .”

$A_ {TM} ≤_m REGULAR_{TM}$

$REGULAR_{TM} = \{ < M >| \ M \ is \ a \ TM \ and \ L(M) \ is \ a \ regular \ language \}.$

Proof

If $L(M_2)$ is regular, than M accept w

If M does not accept w

• $M_2$ recognize $\{0^n 1^n \ | \ n ≥ 0 \}$ which is nonregular

If M accepts w

• $M_2$ recognize all strings $Σ^ *$ ( including $0^n 1^n$) which is regular

S = “On input $<M, w>$, where M is a TM and w is a string:

1. Construct the following TM $M_2$ .
$M_2$ = “On input x:
• If x has the form $0^n 1^n$ , accept .
• If x does not have this form, run M on input w and accept if M accepts w.”
1. Run R on input $<M_2 >$.
2. If R accepts, accept; if R rejects, reject .”

Rice’s theorem

• determining any property of the languages recognized by Turing machines is undecidable.

$E_ {TM} ≤_m EQ_{TM}$

$EQ_{TM} = \{ < M_1 , M_2 > | \ M_1 \ and \ M_2 \ are \ TMs \ and \ L(M_1) = L(M_2) \}.$

Proof

$M_1$ is a TM that rejects all inputs.

If $L(M) = L(M_1)$, than $L(M) = ∅$

REDUCTIONS VIA COMPUTATION HISTORIES

computation history

• the sequence of configurations that the machine goes through as it processes the input
• Finite sequences. If M doesn’t halt on w, no accepting or rejecting computation history exists for M on w.

Linear bounded automaton

• the amount of memory is limited and linear in input size n

decidable

$A_{LBA} = \{ < M, w>| \ M \ is \ an \ LBA \ that \ accepts \ string \ w \}.$

LEMMA 5.8

• If a LBA has q states and g symbols with tape length n.
• There are exactly $qng^n$ distinct configurations.

Proof

• reject after $qng^n$ steps because M is looping

$A_ {TM} ≤_m E_{LBA}$

$E_{LBA} = \{ < M >| \ M \ is \ an \ LBA \ where \ L(M) = ∅ \}.$

Proof

If $L(B) \neq ∅$ = { all accepting computation histories for M on w }, than M accepts w.

Construct B to generate all strings that

1. $C_1$ is the start configuration for M on w.
2. $C_l$ is an accepting configuration for M .
3. Each $C_{i+1}$ legally follows from $C_i$ .

$A_ {TM} ≤_m ALL_{LBA}$

$ALL_{CFG} = \{ < G >| \ G \ is \ a \ CFG \ and \ L(G) = Σ ^ ∗ \}.$

Proof

If $L(G) \neq Σ ^ ∗$ = { all strings except all computation histories for M on w }, than M accepts w.

Construct G to generate all strings that

1. do not start with $C_1$
2. do not end with an accepting configuration
3. some $C_i$ does not properly yield $C_{i+1}$ under the rules of M

### 5.2 A SIMPLE UNDECIDABLE PROBLEM

an example of an undecidable problem not concerning automaton

Post Correspondence Problem

• determine that a collection of dominos has a match (repetitions permitted).

$A_ {TM} ≤_m PCP$

$PCP = \{ < P >| \ P \ is \ an \ instance \ of \ the \ Post \ Correspondence \ Problem \ with \ a \ match\}.$

Proof

If the P we construct has a match, than M accepts w

Construct P

• let P be an instance of MPCP that starting matching with the first domino.

• begins with configuration $C_1$

• Head motions to right and left

• Other tape alphabet surrounded the head

• Separation of the configuration

• pseudo-steps after accept, head eat adjacent symbols.

• Final alignment

• add * symbol so that the only possible match is start with the first domino. ( change MPCP into PCP )

### 5.3 MAPPING REDUCIBILITY

formalize the notion of mapping reducibility

COMPUTABLE FUNCTIONS

f == TM

FORMAL DEFINITION OF MAPPING REDUCIBILITY

mapping reducibility

If $A ≤_m B$ and B is decidable, then A is decidable.

Proof

construct A’s decider N = “On input w:

1. Compute f (w).
2. Run M on input f (w) and output whatever M outputs.”

If $A ≤_m B$ and A is undecidable, then B is undecidable.

$A \ (undecidable) \longrightarrow B \Rightarrow B \ (undecidable)$

Example of computable function

• Input $< M,w >$ while output $<M’,w’>$
• $< M, w > ∈ A_{TM}$ if and only if $<M’ , w’ > ∈ HALT_{TM}$.

(5.1中,在每个S里构造的机器就是这里的reduce function)

If $A ≤_m B$ and B is Turing-recognizable, then A is Turing-recognizable.

If $A ≤_m B$ and A is not Turing-recognizable, then B is not Turing-recognizable.

if $A_{TM} ≤_m \overline{B}$ then $\overline{A_{TM}} ≤_m B$ therefore B isn’t recognizable.

$EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.

Proofed by corollary above.