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:AB maps one set A to another set B:
F
F is one-to-one (injective) if every xA has a unique image F(x): If F(x)=F(y) then x=y.
F is onto (surjective) if every zB is hit by F: If zB then there is an xA 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} . Thats 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:SN.
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 !!
Cantors 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 jX.
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,M2) 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 MNow 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 acceptAcceptance behavior of Mi on Mj7/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 rejectDeciding behavior of G on Mi,Mj7/22/2019 EECS2001, Summer 2019 32Review of Proof (3)MMMMD 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)MMMMD 1234M accept reject accept reject 1M2 accept accept accept acceptM3 reject reject reject reject M4 accept accept reject rejectD 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 Godel 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
Other questions lead to paradoxes:
Does
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 A is recognizable, then A is Turing machine decidable.
Proof: Run the recognizing TMs for A and A 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 A accepted: reject x.
7/22/2019 EECS2001, Summer 2019 38
ATM is not TM-Recognizable
By the previous theorem it follows that ATM cannot
be TM-recognizable, because this would imply
that A is TM decidable (Corollary 4.23). TM
We call languages like ATM 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={
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 = {
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 xw, reject
If x=w, accept iff M accepts w
S = On input
ConstructMasabove.
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 TMs 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: wA 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
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
7/22/2019 EECS2001, Summer 2019 53
Decidability obeys m Ordering
Theorem 5.22: If AmB 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 wA then f(w)B. M accepts f(w) if wA, and
M rejects f(w) if wA.
7/22/2019 EECS2001, Summer 2019 54
Undecidability obeys m Order
Corollary 5.23: If AmB and A is undecidable, then B is undecidable as well.
Proof: Language A undecidable and B decidable contradicts the previous theorem.
Extra: If AmB, then also for the complements (*A) m (*B)
Proof: Let f be the reducing function of A to B with wA 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 AmB 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: wA equivalent with f(w)B. M accepts f(w) if wA, and
M rejects f(w)/does not halt on f(w) if wA.
7/22/2019 EECS2001, Summer 2019 56
Unrecognizability and m
Corollary 5.29: If AmB 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 AmB 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 AmB 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 1B and 0B.)
Because A is decidable, there exists a TM M such that M outputs accept on every xA, and reject on xA. We can use this M for a TM-computable function f with
f(x)=1B if xA and
f f
f(x)=0B if xA
The function f does all the decision-work
B
A
7/22/2019
EECS2001, Summer 2019
58
Reviews
There are no reviews yet.