CS代考 COMP3630/6360: Theory of Computation Semester 1, 2022

COMP3630/6360: Theory of Computation Semester 1, 2022
The Australian National University
Decidability

This lecture covers Chapter 9 of HMU: Decidability and Undecidability
∠ Preliminary Ideas
∠ Example of a non-RE language
∠ Recursive languages
∠ Universal Language
∠ Reductions of Problems
∠ Rice’s Theorem
∠ Post’s Correspondence Problem
∠ Undecidable Problems about CFGs
Additional Reading: Chapter 9 of HMU.

Preliminary Ideas
Preliminary Ideas

Preliminary Ideas
Enumeration of (Binary) Strings
∠ We can construct a bijective map φ from the set of binary strings {0, 1}∗ to natural numbers N.
∠ Enlist all strings ordered by length, and for each length, order using lexi- cographic ordering.
∠ The set of finite binary strings is countable/denumerable.
1111 321 . .

Preliminary Ideas
A Code for Turing Machines
∠ For simplicity, let’s assume that input alphabet to be binary.
∠ WLOG, we can assume that TMs halt at the final state. Consequently, we only need
one final state (perhaps after collapsing all states into one).
∠ Consider M = (Q,{0,1},Γ,δ,q1,B,F).
∠ Rename states {q1,…,qk} for some k ∈ N with q1: start state and qk: final
∠ Rename input alphabet using X1 = 0, X2 = 1, and blank B as X3.
∠ Rename the rest of the tape symbols by X4,…,Xl for some l ∈ N.
∠ RenameLasD1 andR andD2.
∠ Every transition δ(qi , Xj ) = (qk , Xl , Dm) can be represented as a tuple (i, j, k, l, m).
∠ Map each transition tuple (i, j, k, l, m) to a unique binary string 0i 10j 10k 10l 10m.
NB: No string representing a transition tuple contains 11.
∠ Order transition tuples lexicographically and concatenate all transitions using 11 to
indicate end of a transition. Let the resultant string be wM . For example, 3 transitions
can be combined as 0i1 10j1 10k1 10l1 10m1 11 0i2 10j2 10k2 10l2 10m2 11 0i3 10j3 10k3 10l3 10m3 􏰑 􏰐􏰏 􏰒􏰑 􏰐􏰏 􏰒􏰑 􏰐􏰏 􏰒
1st transition 2nd transition 3rd transition
∠ ForeachTMM,definethecode⟨M⟩forTMM aswM.

Preliminary Ideas
The Set of Turing Machines
An Example: A TM that accepts strings with odd # of 1s
01010101001 01001001001001 0010100101001 (1à1à1à1à2) (1à2à2à2à2) (2à1à2à1à2)
X1=X1à D2 X2=X2à D2 X1=X1à D2
X3à X3à D1 (2à3à3à3à1)
Remark 9.1.1
4 X2=X2àD2 (2à 2à 1à 2à 2)
00100010001000101 < M >= 01010101021110102102102102111021010210102111
00100101001001
02 102 10102 102 11102 103 103 103 101.
∠ Each TM M corresponds to a unique natural number, i.e., φ(⟨M⟩); each natural number corresponds to at most one TM.
∠ There are multiple numbers that represent the ‘same’ TM.
∠ The set of TMs/RE languages/CFLs/regular languages is countable.

Example of a non-RE language
Example of a non-RE language

Example of a non-RE language
Diagonalization Language Ld
∠ LetMi betheTM s.t. φ()=i. (Ifforani,nosuchTMexists,weletMi to be the TM with 1 state, no transitions and no final state, i.e., it accepts no input).
∠ Construct an infinite table of 0s and 1s with a 1 at the ith row and jth column if Mi
accepts wj := φ−1(j) (see Slide 3 for φ).
∠ Define a language Ld = {wj : Mj does not accept wj, where j ∈ N}.
Ý 0 1 00 01 10
1(01) 1(21) 1(32) 1(43) 1(45) 1(65) 1(76)
11 ::: 0000000
Ld = Ýà00à10à:::
Entries are for illustrative purposes only

Example of a non-RE language
Ld is not recursively enumerable language
∠ Ld cannot be accepted by any TM.
∠ For each i ∈ N, the string wi is exclusively in either Ld or L(Mi ). ∠ HenceLd ̸=L(Mi)foranyi∈N.
Ý 0 1 00 01 10
1(01) 1(21) 1(32) 1(43) 1(45) 1(65) 1(76)
11 ::: 0000000
M32 0 M4 1
Ld = Ýà00à10à:::
Entries are for illustrative purposes only

Recursive languages
Recursive languages

Recursive languages
Recursive Languages
∠ A language L is recursive if it is accepted by a TM M that halts on all inputs ∠ Insuchacase,theTMM issaidtodecideL.
∠ Every recursive language is recursively enumerable (by definition).
∠ A (decision) problem that is equivalent to: “is a given w in a given recursive language L?” is said to be decidable (for the TM that accepts/rejects L is effectively the machine description of an algorithm for solving the problem).
Context-free
Recursively Enumerable (RE)

Recursive languages
(Some Obvious) Properties of Recursive Languages
Theorem 9.3.1
If L is recursive, so is Lc . Proof of Theorem 9.3.1
w Reject Accept
∠ Accepting states of M are non-accepting states of M′.
∠ Add a new and only final state qf in M′ such that
δM(q,X) undefined and q ∈/ F ⇓
δM′(q,X) = (qf ,X,R).
Accept Reject
∠ Recursive languages are closed under complementation.

Recursive languages
(Some Obvious) Properties of Recursive Languages
Theorem 9.3.2
If L and Lc are both recursively enumerable, then L (and Lc ) are recursive.
Proof of Theorem 9.3.2
∠ Let L = L(M) and Lc = L(M′). Run M and M′ in parallel using a 2-tape TM.
∠ Both TMs cannot halt in final states, and both TMs cannot halt in non-final states. ∠ Continue running both TMs until either halts in a final state.
∠ Accept (or reject) if M (or M′) halts in a final state, respectively.
Alternate Definition of Recursive Languages
L is recursive if both L and Lc are recursively enumerable.

The Universal Language and Turing Machine
The Universal Language and Turing Machine

The Universal Language and Turing Machine
The Universal Language and Turing Machine
Universal Language Lu
∠ Lu := {⟨M⟩111w : TM M and w ∈ L(M)}. [See Slide 3]
Universal TM U (modelled as 5-tape TM)
1 U copies ⟨M⟩ to tape 2 and verifies it for
valid structure.
2 Copiesw ontotape3(maps0􏰁→01,1􏰁→ 001)
3 Initiates4thtapewith01 (M startsinq1)
U’s Finite Control
M’s input and4toidentifyM’sstateandinputas0i ààà B B B B 0 1 B B B ààà
4 To simulate a move of M, U reads tapes 3 and 0j ; if state is accepting, M (and hence
4 M’s state
U’sinputtape 2 ààà 1 0 0 0 0 1 1 1 0 1 B ààà
M’s Code 3 ààà 1 0 0 0 0 B B B ààà
U) accepts its inputs and halts. Else, U scans tape 2 for 110i 10j 1 or BB0i 10j 1. 5
∠ If found, using the transition, tapes 4 and 3 are updated, and tape 3’s head moves to right or left.
∠ If not, M halts, and so does U.
àààB01001Bààà Scratch tape
àààBBBBBBBBB Why is scratch tape needed?

The Universal Language and Turing Machine
Where does Lu Lie in the Hierarchy of Languages?
Theorem 9.4.1
Lu is recursively enumerable, but is not recursive.
Proof of Theorem 9.4.1
∠ Lu is recursively enumerable because TM U accepts it.
∠ Suppose it were recursive. Then, Lcu is also recursive.
∠ LetTMM′ acceptsw∈Lcu andrejectw∈Lu.
∠ Construct a TM M′′ such that it first takes its input w appends it with 111w. It then moves to the beginning of the first w and simulates M′.
∠M′′acceptsw⇐⇒w111w∈Lcu ⇐⇒w111w∈/Lu ⇐⇒w∈Ld. ∠ Then, L(M′′) is the diagonal language Ld, which is impossible!

∠ There exists a bijection φ : Σ∗ → N.
∠ There exists an injective (1-1 map) < · >: Set of TMs → Σ∗. ∠ RE languages are countable.
∠ The diagonalization Language Ld is not recursively enumerable.
∠ Recursive languages are closed under complementation
∠ The universal language Lu = {⟨M⟩111w : M accepts w} is RE, but not recursive.
Context-free
Recursively Enumerable (RE)

Reductions of Problems
Reductions of Problems

Reductions of Problems
What is a Reduction?
∠ A decision problem P is said to reduce to decision problem Q if every instance of P can be transformed to some instance of Q and a yes (or no) answer to that instance of Q yields a yes (or no) answer to original instance of P, respectively.
∠ Here, transform implies the existence of a Turing machine that takes an instance of P written on a tape and always halts with an instance of Q written on it.
∠ Note that for deciding all instances of P, it is not necessary for all instances of Q to be (re)solved.
Theorem 9.6.1
If a problem P reduces to a problem Q then: (a) P is undecidable ⇒ Q is undecidable (b) P is non-R.E. ⇒ Q is non-R.E.

Reductions of Problems
Problem Reduction
Proof of Theorem 9.6.1
(a) Suppose P is undecidable and Q is decidable. Let TM MQ decide Q.
∠ Consider the TM MP that first operates as TM MP−2−Q that transforms P to Q, and
then operates as MQ .
Accept Reject
wP MP2Q MQ
∠ This is a TM that decides all instances of P, a contradiction.
(b) Suppose P is non-R.E. and Q is R.E. Then there must be a TM MQ that accepts inputs when they correspond to instances of Q whose answer is yes.
∠ Consider the TM MP that first operates as TM MP−2−Q, and then operates as MQ.
∠ Note that MP might not halt, since MQ might not.
wP MP2Q MQ Accept
∠ This is a TM that accepts all instances of P whose answer is a yes, a contradiction.

Rice’s Theorem
Rice’s Theorem

Rice’s Theorem
Some More Abstract Languages
Language of TMs Accepting Empty and Non-empty Languages
∠ Le ={⟨M⟩:L(M)=∅}.
∠ Lne = {⟨M⟩ : L(M) ̸= ∅}. (Note: Lne ̸= Lce).
Theorem 9.7.1
Lne is R.E.

Rice’s Theorem
Lne is R.E.
Proof of Theorem 9.7.1
In cycle k, M0 runs one move of M for each ID, and adds the initial ID of M when 1(k) is on the tape.
ID(i,j) = the ID after j 1 moves when M reads 1 (j ) on its tape.
If any ID contains an accepting state, M0 halts as M would have on that input.
1 InputTapeforM0
Cycle Tape 1
101ààà0
ID(1à 3) ID(1àk)
IDk B ààà àààBBBB01BBB ààà
Finite Control of M0 Cycle Count
3 ListofIDsofM
àààBBB11Bààà
ààà B ID1 ààà 4 Scratch Tape
ID(1à 2) ID(2à 1)
ID(2à 2) ID(3à 1) .
ID(2àk 1) ID(3àk 2) ààà ID(kà1)

Rice’s Theorem
Lne is not recursive
Theorem 9.7.2
Lne is not recursive. Proof of Theorem 9.7.2
∠ For every TM M and string w, there is a TM Mw that ignores its input and runs M on w: Mw erases its input tape, and paste w and runs as M.
MMàw w Accept xM
∠ Mind-bending step: There is a TM M1 that takes ⟨M⟩111w and outputs ⟨Mw ⟩. Note: M1 always halts (even if M does not halt when input is w!)
hMi111w M1 hMMàw i
∠ M accepts w ⇐⇒ Mw accepts all inputs ⇐⇒ ⟨Mw ⟩ ∈ Lne
∠ Suppose Lne is recursive. Then there is a TM M2 that accepts iff input ⟨M⟩ ∈ Lne.
∠ Let TM M3 read ⟨M⟩111w and operate as M1 and then when M1 halts, operate as M2. Then, M3 accepts/rejects ⟨M⟩111w iff M accepts/rejects w.
∠ Lu is then recursive, which is a contradiction.

Rice’s Theorem
Rice’s Theorem
Given: alphabet Σ and let RE = {L ⊆ Σ∗ | L recursively enumerable}.
∠ Recursively enumerable (RE) languages L corresponds to TM M if L = L(M)
∠ A property of RE languages is subset P ⊆ RE of the set of RE languages over Σ. ∠ A property P is trivial if P = ∅ or P = RE (and non-trivial otherwise).
∠ a property P ⊆ RE is decidable if LP = {⟨M⟩ | L(M) ∈ P} is decidable.
∠ identify TM M with RE language L(M) ∠ identify M with its code ⟨M⟩.
Theorem 9.7.3
Every non-trivial property P of RE languages is undecidable, i.e., LP is not recursive.

Rice’s Theorem
Rice’s Theorem
Proof of Theorem 9.7.3
∠ WLOG, we can assume that ∅ ∈/ P. Else consider Pc .
∠ Since P is non-trivial, there is a language L ∈ P and a TM ML that accepts L
∠ LetMM,w beaTMthatrunsM onw andifM acceptsw,thenreadsitsinputand operates as ML.
∠ Mind-bending step: There is a TM M1 that takes ⟨M⟩111w and outputs ⟨MM,w ⟩.
Note: M1 always halts (even if M does not halt when input is w!) hMi111w M1 hMMàw i
∠Macceptsw ⇐⇒ L(MM,w)=L∈P
∠ If P were decidable, then there is a ML M2 such that M2 accepts ⟨M⟩ iff L(M) ∈ P.
∠ Then, we can devise a TM M3 such that it reads ⟨M⟩111w operates first as M1 and then when M1 has halted, it operates as M2.
∠ M3 accepts/rejects ⟨M ⟩111w ⇐⇒ L(MM ,w ) ∈ / ∈/ P ⇐⇒ M accepts/rejects w .
∠ Then, Lu is recursive, a contradiction

Post’s Correspondence Problem
Post’s Correspondence Problem

Post’s Correspondence Problem
PCP: Definition
∠ Suppose we are given two ordered lists of strings over Σ, say A = (u1,…,uk) and B = (v1,…,vk).
∠ We say (ui , vi ) to be a corresponding pair
∠ PCP Problem: Is there a sequence of integers i1 , . . . , im such that ui1 ···uim = vi1 ···vim?
∠ m can be greater than k, the list length.
∠ We can reuse pairs as many times as we like.
A PCP example
A 110 0011 0110
B 110110 00 110
∠ A solution cannot start with i1 = 3.
∠ A solution can start with i1 = 1, but then i2 = 1, and i3 = 1…. Consequently, i1
cannot equal 1.
∠ A solution does exist: (i1, i2, i3) = (2, 3, 1).
∠ (i1, i2, i3, i4, i5, i6) = (2, 3, 1, 2, 3, 1) is also solution.

Post’s Correspondence Problem
Modified PCP (MPCP): Definition
∠ Suppose we are given two ordered lists of strings over Σ, say A = (u1,…,uk) and B = (v1,…,vk).
∠ MPCP Problem: Is there a sequence of integers i1 , . . . , im such that u1ui1 ···uim = v1vi1 ···vim
∠ The previous example does not have a solution when viewed as an MPCP problem. ∠ So MPCP is indeed a different problem to PCP, but…
Theorem 9.8.1
MPCP reduces to PCP

Post’s Correspondence Problem
Outline of Proof of Theorem 9.8.1
∠ Given lists A = (u1,…,uk) and B = (v1,…,vk) for MPCP, suppose that symbols ⋄, △ are not in the strings.
∠ Construct lists C = (w1,…,wk+2) and D = (x1,…,xk+2) for PCP as follows.
∠ For i = 1, . . . , k, If uk = s1 . . . sl, then wk+1 = s1 ⋄ s2 ⋄ · · · ⋄ sl⋄. [⋄ succeeds
∠ For i = 1, . . . , k, If vk = s1 . . . sl, then xk+1 = ⋄s1 ⋄ s2 ⋄ · · · ⋄ sl. [⋄ precedes
∠ w1 = ⋄w2 and x1 = x2. [Ensures any solution to PCP also starts with i1 = 1]
∠ wk+2 = △ and xk+2 = ⋄△. [Balances the extra ⋄]
110 ⇧1⇧1⇧0⇧ 110110 ⇧1⇧1⇧0⇧1⇧1⇧0 0011 1⇧1⇧0⇧ 00 ⇧1⇧1⇧0⇧1⇧1⇧0 0110 0⇧0⇧1⇧1⇧ 110 ⇧0⇧0
0⇧1⇧1⇧0⇧ ⇧1⇧1⇧0 4 ⇧4
wi1 ···wim = xi1 ···xim (PCP) ⇕
u1ui2−1···uim−1−1 =v1vi2−1···vim−1−1 (MPCP)

Post’s Correspondence Problem
PCP is undecidable
Theorem 9.8.2
PCP is undecidable.
Outline of Proof of Theorem 9.8.2 (for one-sided TM)
∠ The proof proceeds by constructing a MPCP for each TM M and input w
Rule A: Construct two lists A and B whose first entries are ⋄ and ⋄q0w⋄
Rule I: Add corresponding pairs (X , X ) (all X ∈ Γ) and (⋄, ⋄)
Rule B: Suppose q is not a final state. Then, append to the list the following entries
List A qX ZqX q⋄ Zq⋄
List B Yp pZY Yp⋄ pZY⋄
ifδ(q,X) = (p,Y,R) ifδ(q,X) = (p,Y,L) if δ(q, B) = (p, Y , R) ifδ(q,B) = (p,Y,L)
Rule C: For q ∈ F, let (XqY,q), (Xq,q) and (qY,Y) be corresponding pairs for X,Y ∈Γ
Rule D: For q ∈ F (q ⋄ ⋄, ⋄) is a corresponding pair.

Post’s Correspondence Problem
PCP is undecidable
Outline of Proof of Theorem 9.8.2
∠ Suppose there is a solution to the MPCP problem. The solution starts with the first corresponding pair, and the string constructed from List B is already a ID of TM M ahead of the string from List A.
∠ As we select strings from List A (corresponding to Rule B) to match the last ID, the string from List B adds to its string another valid ID.
∠ The sequence of IDs constructed are valid sequences of IDs for M starting from q0w.
∠ Suppose the last ID constructed in the string constructed from List B corresponds to
a final state, then we can gobble up one neighboring symbol at a time using Rule C.
∠ Once we are done gobbling up all tape symbols, the string from List B is still one
final state symbol ahead of List A’s string.
∠ We then use Rule D to match and complete.
String from List B one ID ahead zàààz
List A catch-up
Final state catch-up
q0w⇧ ‘ I D 10 ⇧
‘ I D 10 ⇧ ‘ I D 20 ⇧
à à à ‘ I D k0 ⇧ zzzz
‘ I D k0 ⇧ s1qf s4s5⇧
s1qf s4s5⇧ qf s5⇧
qf s5⇧ qf ⇧
Rule A Rule B Rule C Rule D
IDk = s1s2qf s3s4s5

Post’s Correspondence Problem
PCP is undecidable
Outline of Proof of Theorem 9.8.2
∠ M accepts w ⇐⇒ a solution to the MPCP exists.
∠ If MPCP were decidable, then Lu would be recursive, which it isn’t.
∠ Hence, MPCP is undecidable. [Theorem 9.6.1]
∠ Since MPCP is undecidable, PCP is also undecidable. [Theorem 9.6.1]

Ambiguity in CFGs
Ambiguity in CFGs

Ambiguity in CFGs
∠ We’ll now revisit CFGs and prove that ambiguity in CFGs is undecidable. Theorem 9.9.1
The problem if a grammar is ambiguous is undecidable
Outline of Proof of Theorem 9.8.2
∠ We’ll reduce every instance of PCP problem to a CFG.
∠ Given an PCP problem A = (w1,··· ,wk) and B = (x1,…,xk), pick symbols
a1,…,ak that don’t appear in any string in list A or B.
∠ Now define a grammar G with production rules
A −→ w1Aa1|···|wkAak|w1a1|···|wkak B −→ x1Ba1|···|xkBak|x1a1|···|xkak
∠ If there are two leftmost derivations of a string in L(G ), one must use S −→ A and other S −→ B
∠ Every solution to the PCP leads to 2 leftmost derivations of some string in L(G) and vice versa.
∠ Since PCP is undecidable, the ambiguity of CFGs must be undecidable [Thm 9.6.1] 36/37

Ambiguity in CFGs
Some More Undecidable Problems Concerning CFGs
∠ Given CFGs G1 and G2, is L(G1) ∩ L(G2) = ∅?
∠ Given CFGs G1 and G2, is L(G1) ⊆ L(G2)?
∠ Given CFGs G1 and G2, is L(G1) = L(G2)?
∠ Given CFG G and regular language L, is L(G ) = L? ∠ Given CFG G and regular language L, is L ⊆ L(G )? ∠ Given CFG G, is L(G) = Σ∗?

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts