EECS2001:
Introduction to Theory of Computation
Summer 2019
Ali Mahmoodi
amahmoodi@cse.yorku.ca
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 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} . 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 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 < 8
7 if F(i)i 8
Q: 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 as
P (N) and R.
• What if we take P (R)?
• Can we build bigger and bigger infinities this
way?
• Euler: Continuum hypothesis – YES!
7/22/2019 EECS2001, Summer 2019 22
Uncountability
We 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 TMs
Observation: Every TM has a finite description; there is only a countable number of different TMs. (A description M can consist of a finite string
of 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 Languages
There 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 Languages
There 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 different
languages L{0,1}*.
➢ Hence there is no surjection possible from the
countable 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 language
A = { M,w | M is a TM that accepts w }. TM
Proof that A is not TM-decidable (Thm. 4.11) TM
(Contradiction) Assume that TM G decides A : TM
G M,w = "accept" if Maccepts w
" reject" if M does not accept w
From 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 M
Hence: 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 D
This 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. TM
This proof used diagonalization implicitly...
Result:
7/22/2019 EECS2001, Summer 2019 30
Review of Proof (1)
MMMM 1234
M accept accept 1
M2 accept accept accept accept
M3 M4 accept accept
‘Acceptance behavior’ of Mi on Mj
7/22/2019 EECS2001, Summer 2019 31
Review of Proof (2)
MMMM 1234
M accept reject accept reject 1
M2 accept accept accept accept
M3 reject reject reject reject M4 accept accept reject reject
‘Deciding behavior’ of G on Mi,Mj
7/22/2019 EECS2001, Summer 2019 32
Review of Proof (3)
MMMMD 1234
M accept reject accept reject 1
M2 accept accept accept accept
M3 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 1234
M accept reject accept reject 1
M2 accept accept accept accept
M3 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 Problem
The “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 Math
The 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 CSE
What 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 Ā 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={
• 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
• 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: 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