Week 2:
Lecture 3
TM: tape: two way, can write…
Formally, Turing machine M is a 7-tuple,
(Q, , , , q0, qaccept, qreject,), where
1. Q is the set of states
2. is the input alphabet not containing the
special blank symbol
3. is the tape alphabet, where { } and
4.: Q Q {L.R} is the transition function (not a mapping)
5.q0 Q is the initial state
6. qaccept Q is the accept state
7. qreject Q is the reject state, where qaccept, qreject
Configuration of M: uqv (head is at the first symbol of string v)
Start configuration
Accepting configuration
uaqibv yields uacqjv if (qi,b) = (qj,c,R)
M accepts w: C1 is the start conf of M on input w
Each Ci yields C i+1
Ck is the accepting conf
Note that the definition hold even for a NDTM.
Even in this case, we have many variations:
determinism vs. non det
1 tape vs. multi tape
read only vs. read write
Theorem: If an algorithm A has time complexity O(nk), then there is a TM M which can implement A in O(nkc), for some constant c.
i.e., Time complexity on random access machine and TM are polynomially related.
Nondeterminism vs. determinism
Theorem:Let M be a NDTM. Then there is a DTM M’ such that L(M) = L(M’).
Proof: Given with input x, M’ searches all possible computation tree of M in a breadth-first search style. (depth first search style simulation does not work since M may not halt on input w for some computation sequences)
Definitions:
L is decidable (recursive) if there exists a TM M which halts on all input and accepts L.
L recursively enumerable if there exists a TM M which accepts L. (i.e. if x is not in L, M may not halt at all)
Frequently, if L is decidable, then we say that the decision problem “if x is in L or not” is decidable.
Or the decision problem on language L has the following format:
Decision problem L
Instance: x and L
Question: Is x in L?
Some decidable languages: cfl, regular…
Some decidabledecision problems:
Membership of CFL L.
Instance: CFL L, and a string x
Question: Is x in L?
Emptiness of regular language.
Instance: DFA M
Question: Is L(M) = ?
Why???
Equivalence of regular language.
Instance: DFA M1 and M2
Question: Is L(M1) = L(M2)?
Theorem: Let A and B are FA. Then it is decidable if L(A) = L(B).
Proof: Let define L =((L(A) L(B)c) ((L(A)c L(B)). Then L = iff L(A) = L(B).
Note that L is also regular. Thus it is decidable if L is empty or not. Thus, it is decidable if L(A) = L(B).
Some undecidable problems
Halting problem.
Instance: TM M, and a string x
Question: Does M halts on x?
Equivalence of CFL
Membership of CFL L.
Instance: CFG G1 and G2
Question: Is L(G1) = L(G2)?
How about:
Question: Does there exist n such that xn + yn = z2n?
Question: Does there exist God?
Theorem: L is recursive iff Lc is recursive.
Theorem: It is decidable if L is empty or not.
Theorem: recursive sets are closed under union and intersections.
TM as an enumerator: TM M generates strings.
Note that a string may be generated multiple times, and generated in any order.
Theorem: L is Turing recognizable iff there is a TM M’ which enumerates L.
Proof. (=>) Let L be accepted by TM M. then construct an TM M which enumerate L as follows:
- Repeat i=1 to infinite
- Run M I steps for each input s1,…,si
- if any computations accepts si, print si.
(<=) Let M enumerates L. Let us construct a TM M’ such that L(M) = L.
Given input w, M’ simulate M. Each time M generate a string x, check if x = w o not. If x=w then accepts w; else continue the simulation of M.
Lecture 4 summary of lecture to be covered.
- ATM = {<M,w> | M is a TM and M accepts w} is undecidable.
- ATM is Turing recognizable (recursively enumerable).
Diagonalization Method
Countable, uncountable
Z is countable, ZZ is countable.
RR has the same size as R.
R is uncountable.
The set of all languages is uncountable.
The set L of all TMs, that is L = {<M>| M is a TM}, is uncountable.
Theorem: ATMis undecidable.
(proof) Diagnalization.
A non recursively enumerable (Turing-unrecognizable) language
The complement of ATM is not r.e.
- Hating problem is undecidable.
HALTTM = {<M,w> | M is a TM and M halts on input w} is undecidable.