[SOLVED] 代写 R math parallel graph theory EECS2001:

EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
[email protected]
Office: Lassonde 2015 Course page: Moodle
Notes based on work by Professor Suprakash Datta
7/22/2019 EECS2001, Summer 2019 1

Next
Towards undecidability:
• The Halting Problem
• Countable and uncountable infinities • Diagonalization arguments
7/22/2019 EECS2001, Summer 2019 2

The Halting Problem
The existence of the universal TM U shows that
A = {M,w | M is a TM that accepts w } TM
is TM-recognizable, but can we also decide it? The problem lies with the cases when M does
not halt on w. In short: the halting problem.
We will see that this is an insurmountable problem: in general one cannot decide if a TM will halt on w or not, hence A is undecidable.
7/22/2019 EECS2001, Summer 2019 3
TM

Counting arguments
• We need tools to reason about undecidability.
• The basic argument is that there are more languages than Turing machines and so there are languages than Turing machines. Thus some languages cannot be decidable
7/22/2019 EECS2001, Summer 2019 4

Baby steps
• What is counting?
– Labeling with integers
– Correspondence with integers
• Let us review basic properties of functions
7/22/2019 EECS2001, Summer 2019 5

Mappings and Functions
The function F:A→B maps one set A to another set B:
F
F is one-to-one (injective) if every xA has a unique image F(x): If F(x)=F(y) then x=y.
F is onto (surjective) if every zB is ‘hit’ by F: If zB then there is an xA such that F(x)=z.
F is a correspondence (bijection) between A
and B if it is both one-to-one and onto.
A
B
7/22/2019 EECS2001, Summer 2019
6

Cardinality
A set S has k elements if and only if there exists a bijection between S and {1,2,…,k}.
S and {1,…,k} have the same cardinality.
If there is a surjection possible from {1,…,n}
to S, then n  |S|.
We can generalize this way of comparing the
sizes of sets to infinite ones.
7/22/2019 EECS2001, Summer 2019 7

How Many Languages?
For ={0,1}, there are 2k words of length k. Hence, there are 2(2k ) languages L  k.
Proof: L has two options for every word k; (2k )
L can be represented by a string  {0,1} . That’s a lot, but finite.
There are infinitely many languages  *. But we can say more than that…
Georg Cantor defined a way of comparing infinities.
7/22/2019 EECS2001, Summer 2019 8

Countably Infinite Sets
A set S is infinite if there exists a surjective function F:S→N.
“The set N has no more elements than S.”
A set S is countable if there exists a surjective function F: N →S
“The set S has not more elements than N.”
A set S is countably infinite if there exists a bijective function F: N →S.
“The sets N and S are of equal size.”
7/22/2019 EECS2001, Summer 2019 9

Counterintuitive facts
• Cardinality of even integers
– Bijection i  2i
– A proper subset of N has the same cardinality as N !
– Same holds for odd integers
• What about pairs of natural numbers?
– Bijection from N to N x N !!
– Cantor’s idea: count by diagonals
– Implies set of rational numbers is countable
7/22/2019 EECS2001, Summer 2019 10

Counterintuitive facts – 2
• Note that the ordering of Q is not in increasing order or decreasing order of value.
• In proofs, you CANNOT assume that an ordering has to be in increasing or decreasing order.
• So cannot use ideas like “between any two real numbers x, y, there exists a real number 0.5(x+y)” to prove uncountability.
7/22/2019 EECS2001, Summer 2019 11

More Countably Infinite Sets
One can make bijections between N and 1.{a}*: i ai
2. Integers (Z):
1 2 3 4 5 6 7 8 9 10 11 0 +1 -1 +2 -2 +3 -3 +4 -4 +5 -5
7/22/2019 EECS2001, Summer 2019 12

Countable sets in language theory
• * is countable – finitely many strings of length k. Order them lexicographically.
• Set of all Turing machines countable – every TM can be encoded as a string over some .
7/22/2019 EECS2001, Summer 2019 13

Summary
A set S is countably infinite if there exists a bijection between {0,1,2,…} and S.
Intuitively: A set S is countable, if you can make a List (numbering) s1,s2,… of all the elements of S.
The sets Q, {0,1}* are countably infinite. Example for {0,1}*: the lexicographical ordering:
{0,1}* = {,0,1,00,01,10,11,000,…}
Q: Are there bigger sets?
7/22/2019 EECS2001, Summer 2019 14

Next
•Chapter 4.2:
• Uncountable Set of Languages
• Unrecognizable Languages
• Halting Problem is Undecidable
• Non-Halting is not TM-Recognizable
7/22/2019 EECS2001, Summer 2019 15

Uncountable Sets
There are infinite sets that are not countable. Typical examples are R, P (N) and P ({0,1}*)
We prove this by a diagonalization argument. In short, if S is countable, then you can make a list s1,s2,… of all elements of S.
Diagonalization shows that given such a list, there will always be an element x of S that does not occur in s1,s2,…
7/22/2019 EECS2001, Summer 2019 16

Uncountability of P (N)
The set P (N) contains all the subsets of {1,2,…}.
Each subset X N can be identified by an infinite string of bits x1x2… such that xj=1 iff jX.
There is a bijection between P (N) and {0,1}N. Proof by contradiction: Assume P (N) countable.
Hence there must exist a surjection F from N to the set of infinite bit strings.
“There is a list of all infinite bit strings.”
7/22/2019 EECS2001, Summer 2019 17

Diagonalization
Try to list all possible infinite bit strings:
000000 111111 210000 301010

Look at the bit string on the diagonal of
this table: 0101… The negation of this
string (“1010…”) does not appear in the table.
7/22/2019 EECS2001, Summer 2019 18

No Surjection N → {0,1}N Let F be a function N → {0,1}N.
F(1),F(2),… are all infinite bit strings. Define the infinite string Y=Y1Y2… by
Yj = NOT(j-th bit of F(j))
On the one hand Y {0,1}N, but on the other hand: for every j N we know that F(j)  Y because F(j) and Y differ in the j-th bit.
F cannot be a surjection: {0,1}N is uncountable. 7/22/2019 EECS2001, Summer 2019 19

Generalization
• We proved that P ({0,1}*) is uncountably infinite.
• Can be generalized to P (*) for any finite .
7/22/2019 EECS2001, Summer 2019 20

R is uncountable
• Similar diagonalization proof. We will prove [0,1) uncountable
• Let F be a function N → R F(1),F(2),… are all infinite digit strings (padded with zeroes if required).
• Define the infinite string of digits Y=Y1Y2… by
Yj = F(i)i + 1 if F(i)i < 87 if F(i)i  8Q: Where does this proof fail on N?7/22/2019 EECS2001, Summer 2019 21 Other infinities• We proved 2N uncountable. We can show that this set has the same cardinality asP (N) and R.• What if we take P (R)?• Can we build bigger and bigger infinities thisway?• Euler: Continuum hypothesis – YES!7/22/2019 EECS2001, Summer 2019 22 UncountabilityWe just showed that there it is impossible to have a surjection from N to the set {0,1}N. What does this have to do with Turing machine computability?7/22/2019 EECS2001, Summer 2019 23 Counting TMsObservation: Every TM has a finite description; there is only a countable number of different TMs. (A description M can consist of a finite stringof bits, and the set {0,1}* is countable.)Our definition of Turing recognizable languages is a mapping between the set of TMs {M1,M2 ,…}and the set of languages {L(M1),L(M2),…}P (*).Question: How many languages are there? 7/22/2019 EECS2001, Summer 2019 24 Counting LanguagesThere are uncountably many different languages over the alphabet ={0,1} (the languages L{0,1}*). With the lexicographical ordering ,0,1,00,01,… of *, every L coincides with an infinite bit string via its characteristic sequence L.Example for L={0,00,01,000,001,…} with L= 0101100…*  0 1 00 01 10 11 000 001 010  LXXX XXX L 0 1 0 1 1 0 0 1 1 1 7/22/2019 EECS2001, Summer 2019 25 Counting TMs and LanguagesThere is a bijection between the set of languages over the alphabet ={0,1} and the uncountable set of infinite bit strings {0,1}N.➢There are uncountable many differentlanguages L{0,1}*.➢ Hence there is no surjection possible from thecountable set of TMs to the set of languages. Specifically, the mapping L(M) is not surjective.Conclusion: There are languages that are not Turing-recognizable. (A lot of them.) 7/22/2019 EECS2001, Summer 2019 26 Is This Really Interesting? We now know that there are languages that are not Turing recognizable, but we do not know what kind of languages are non-TM- recognizable.Are there interesting languages for which we can prove that there is no Turing machine that recognizes it?7/22/2019 EECS2001, Summer 2019 27 Proving Undecidability (1)Recall the languageA = { M,w | M is a TM that accepts w }. TMProof that A is not TM-decidable (Thm. 4.11) TM(Contradiction) Assume that TM G decides A : TMG M,w = ”accept” if Maccepts w ” reject” if M does not accept wFrom G we construct a new TM D that will get us into trouble…7/22/2019 EECS2001, Summer 2019 28 Proving Undecidability (2)The TM D works as follows on input M (a TM): 1) Run G on M,M2) Disagree with the answer of G(The TM D always halts because G always halts.)In short:”accept”ifGrejects M,M D M = ”reject” if G accepts M, M”accept”ifMdoesnotaccept MHence: D M = ”reject”ifMdoesaccept MNow run D on D (“on itself”)…7/22/2019 EECS2001, Summer 2019 29 Proving Undecidability (3)”accept”ifDdoesnotaccept D D D = ”reject” if D does accept DThis does not make sense: D only accepts if it rejects, and vice versa.(Note again that D always halts.)Contradiction: A is not TM-decidable. TMThis proof used diagonalization implicitly…Result:7/22/2019 EECS2001, Summer 2019 30 Review of Proof (1)MMMM 1234M accept accept 1M2 accept accept accept acceptM3  M4 accept accept‘Acceptance behavior’ of Mi on Mj7/22/2019 EECS2001, Summer 2019 31 Review of Proof (2)MMMM 1234M accept reject accept reject 1M2 accept accept accept acceptM3 reject reject reject reject  M4 accept accept reject reject‘Deciding behavior’ of G on Mi,Mj7/22/2019 EECS2001, Summer 2019 32Review of Proof (3)MMMMD 1234M accept reject accept reject 1M2 accept accept accept acceptM3 reject reject reject reject  M4 accept accept reject reject D reject reject accept accept  Disagreeing D has to occur in list as well…7/22/2019 EECS2001, Summer 2019 33 Review of Proof (4)MMMMD 1234M accept reject accept reject 1M2 accept accept accept acceptM3 reject reject reject reject  M4 accept accept reject rejectD reject reject accept accept  ?Contradiction for D on input D.7/22/2019 EECS2001, Summer 2019 34 Another View of the ProblemThe “Self-referential paradox” occurs when we force the TM D to disagree with itself.On the one hand, D knows what it is going to do on input D, but then it decides to do something else instead.“You cannot know for sure what you will do in the future, because then you could decide to change your actions and create a paradox.”7/22/2019 EECS2001, Summer 2019 35 Self-Reference in MathThe diagonalization method implements the self- reference paradox in a mathematical way.In logic this approach is often used to prove that certain things are impossible.Kurt Gödel gave a mathematical equivalent of “This sentence is not true.”Old puzzle: In a town, there is a barber who shaves all those who do not shave themselves.Who shaves the barber ?7/22/2019 EECS2001, Summer 2019 36 Self-Reference in CSEWhat happens if a computer program M tries to answer questions about itself ?
Sometimes this is perfectly okay: – How big is ?
– Is a proper TM?
Other questions lead to paradoxes:
– Does halt or not?
– Is there a smaller program M’ that is equivalent?
7/22/2019 EECS2001, Summer 2019 37

TM-Unrecognizable
A is not TM-decidable, but it is TM-recognizable. TM
What about a language that is not recognizable?
Theorem 4.22: If a language A is recognizable and its complement Ā is recognizable, then A is Turing machine decidable.
Proof: Run the recognizing TMs for A and Ā in parallel on input x. Wait for one of the TMs to accept. If the TM for A accepted: “accept x”;
if the TM for Ā accepted: “reject x”.
7/22/2019 EECS2001, Summer 2019 38

ĀTM is not TM-Recognizable
By the previous theorem it follows that ĀTM cannot
be TM-recognizable, because this would imply
that A is TM decidable (Corollary 4.23). TM
We call languages like ĀTM co-TM recognizable.
TM-recognizable
TM decidable
co-TM recognizable
7/22/2019 EECS2001, Summer 2019 39

Things that TMs Cannot Do:
The following languages are also unrecognizable: ETM = { G | G is a TM with L(G)= }
EQTM = { G,H | G and H are TMs with L(G)=L(H) }
To be precise:
• ETM is co-TM recognizable
• EQTM is not even co-Turing recognizable
How can we prove these facts?
7/22/2019 EECS2001, Summer 2019 40

Next: reducibility
• We still need to prove that the Halting problem is undecidable.
• Do more examples of undecidable problems.
• Try to get a general technique for proving undecidability.
7/22/2019 EECS2001, Summer 2019 41

Halting problem
• Assume that it is decidable. So there is a TM R that decides
HALT={ |M is a TM and M halts on w}
• Use R as a subroutine to get a TM S to decide
= {M,w | M is a TM that accepts w }
• Therefore A is decidable. CONTRADICTION!
A TM
TM
• Details follow ….
7/22/2019 EECS2001, Summer 2019 42

Halting problem – 2
S = “On input
• Run TM R on input .
• If R rejects, REJECT.
• If R accepts, simulate M on w until it halts. • If M has accepted, ACCEPT, else REJECT”
7/22/2019 EECS2001, Summer 2019 43

More undecidability
ETM = { | M is a TM and L(M) = }
We mentioned that ETM is co-TM recognizable. We will prove next that ETM is undecidable.
Intuition: You cannot solve this problem UNLESS you solve the halting problem!!
But this is hard to formalize, so we use A
Instead.
.
7/22/2019 EECS2001, Summer 2019
44
TM

ETM is undecidable
Assume R decides E . Use R to design TM S to decide A . TM TM
• Given a TM M and input w, define a new TM M’: – If xw, reject
– If x=w, accept iff M accepts w
S = “On input
• ConstructM’asabove.
• Run TM R on input .
• If R accepts, REJECT; If R rejects, ACCEPT.”
7/22/2019 EECS2001, Summer 2019 45

EQTM is undecidable
If this is decidable, then we can solve ETM!! (You need to check equality with TM M1 that rejects all inputs)
Assume R decides EQTM. Use R to design TM S to decide ETM.
S = “On input
• Run TM R on input .
• If R accepts, ACCEPT; If R rejects, REJECT.”
7/22/2019 EECS2001, Summer 2019 46

The running idea
All our proofs had a common structure
• The first undecidable proof was hard – used diagonalization/self-reference.
• For the rest, we assumed decidable and used it as a subroutine to design TM’s that decide known undecidable problems.
• Can we make this technique more structured?
7/22/2019 EECS2001, Summer 2019 47

Mapping Reducibility
Thus far, we used reductions informally:
If “knowing how to solve A” implied “knowing how
to solve B”, then we had a reduction from B to A.
Sometimes we had to negate the answer to the “A?” question, sometimes not. In general, it was unspecified which transformations were allowed around the “A?”-part of the reduction.
Let us make this formal…
7/22/2019 EECS2001, Summer 2019 48

Computable Functions
A function f:*→* is a TM-computable function if there is a Turing machine that on every input w* halts with just f(w) on the tape.
All the usual computations (addition, multiplication, sorting, minimization, etc.) are all TM-computable.
Note: alterations to TMs, like “given a TM M, we can make an M’ such that…” can also be described by computable functions that satisfy f(M) = M’.
7/22/2019 EECS2001, Summer 2019 49

Mapping Reducible
A language A is mapping reducible to a another language B if there is a TM-computable function
f:*→* such that: wA  f(w)B for every w*.
A
Terminology/notation: • A m B
• function f is the
reduction of A to B • also called:
f
B
f
“many-one reducible”
7/22/2019 EECS2001, Summer 2019
50

A m B
The language B can be more difficult than A.
f f
Typically, the image f(A) is only a subset of B, and f(*A) a subset of *B.
“Image f(A) can be the easy part of B”.
A
B
7/22/2019 EECS2001, Summer 2019 51

Previous mappings used
A  HALT TMm TM
F = “On input
• Construct TM M’ = “on input x: – Run M on x
– If M accepts, ACCEPT
– If M rejects, enter infinite loop.”
• Output ”
Check: f maps < M,w> to .
 ATM   HALTTM
7/22/2019 EECS2001, Summer 2019 52

Previous mappings used – 2
Recall: M1 rejects all inputs. Assume R decides EQTM. Use R to design TM S to decide ETM.
S = “On input
• Run TM R on input .
• If R accepts, ACCEPT; If R rejects, REJECT.”
Check: f maps < M> to .  ETM   EQTM
7/22/2019 EECS2001, Summer 2019 53

Decidability obeys m Ordering
Theorem 5.22: If AmB and B is TM-decidable, then A is TM-decidable.
Proof: Let M be the TM that decides B and f the reducing function from A to B. Consider the TM: On input w:
1) Compute f(w)
2) Run M on f(w) and give the same output.
By definition of f: if wA then f(w)B. M “accepts” f(w) if wA, and
M “rejects” f(w) if wA.
7/22/2019 EECS2001, Summer 2019 54

Undecidability obeys m Order
Corollary 5.23: If AmB and A is undecidable, then B is undecidable as well.
Proof: Language A undecidable and B decidable contradicts the previous theorem.
Extra: If AmB, then also for the complements (*A) m (*B)
Proof: Let f be the reducing function of A to B with wA  f(w)B. This same computable function also obeys “v(*A)  f(v)(*B)” for all v*
7/22/2019 EECS2001, Summer 2019 55

Recognizability and m
Theorem 5.28: If AmB and B is TM-recognizable, then A is TM-recognizable.
Proof: Let M be the TM that recognizes B and f the reducing function from A to B. Again the TM: On input w:
1) Compute f(w)
2) Simulate M on f(w) and give the same result.
By definition of f: wA equivalent with f(w)B. M “accepts” f(w) if wA, and
M “rejects” f(w)/does not halt on f(w) if wA.
7/22/2019 EECS2001, Summer 2019 56

Unrecognizability and m
Corollary 5.29: If AmB and A is not Turing- recognizable, then B is not recognizable as well.
Proof: Language A not TM-recognizable and B recognizable contradicts the previous theorem.
Extra: If AmB and A is not co-TM recognizable, then B is not co-Turing-recognizable as well.
Proof: If A is not co-TM-recognizable, then the complement (*A) is not TM recognizable.
By AmB we also know that (*A) m (*B).
Previous corollary: (*B) not TM recognizable, hence B not co-Turing-recognizable .
7/22/2019 EECS2001, Summer 2019 57

Decidable A m B
If A is a decidable language, then A m B for
every nontrivial B. (Let 1B and 0B.)
Because A is decidable, there exists a TM M such that M outputs “accept” on every xA, and “reject” on xA. We can use this M for a TM-computable function f with
f(x)=1B if xA and
f f
f(x)=0B if xA
“The function f does all the decision-work”
B
A
7/22/2019
EECS2001, Summer 2019
58