Computability Theory
Decision Problems
A decision problem is a problem which requires ‘yes’/‘no’ answer.
Examples
1) Hamiltnian Circuit Problem: Given a graph G, determine whether or not it has a Hamiltonian circuit (i.e., a circuit (tour) that passes through every vertex of G exactly once). a decidable decision problem (there is a nondeterministic polynomial time algorithm to solve this problem).
2) Hilbert’s tenth problem: Given a polynomial p(x1,…,xn) whose coefficients are integers, determine whether or not p(x1,…,xn)=0 has a nontrivial integral solution (i.e., an integral solution other than (0,…,0)). an undecidable decision problem (there is no algorithm to solve this problem).
3) Halting problem for TMs: Given a TM M and input x, determine whether or not M halts eventually on input x. an undecidable decision problem.
4) Travelling salesman problem: Given a weighted complete graph (a graph in which there is an edge between any two vertices and each edge has an integer as a label), find a tour whose sum of weights is minimum. this is not a decision roblem.
5) Compute the gcd of two integers. non-decision problem.
Why are Turing machines algorithms ?
Note: Correspondence between recursively enumerable sets of strings and recursively enumerable sets of integers
A set, say S, of natural numbers is said to be recursively enumerable (r.e.)if it is the domain of a partial recursive function, say f (equivalently, if it is the range of some partial recursive function). Thus f is an enumerator of the elements in S (some elements appear repeatedly in the enumeration): S = {f(0), f(1), f(2), …}.
A set S of natural numbers is said to be recursive if it is the range of a monotonically increasing (i.e., if xy then f(x)f(y)) recursive function f (or equivalently, S is recursive if and only if there is a recursive function g such that g(x)=1 if xS and g(x)=0 if xS (g is called the characteristic function of S). Thus g can be regarded as an algorithm that determines whether or not a given x is a member of S.
Recall that a language L is r.e. if and only if L is accepted by a TM (or equivalently, if there is a TM that enumerates all the elements of L). Also recall that L is recursive if and only if L is accepted by a halting TM, say M. Then M can be regarded as an algorithm to determine whether or not a given x is a member of L (that is, xL if M halts on input x in an accepting state, and xL if M halts in a nonaccepting state).
Exercises
1. Show that L (or S) is recursive if and only if both L (or S) and its complements are r.e. (It is known that there is a r.e. set which is not recursive. Thus the class of r.e. sets/languages (= the class of type 0 languages) is not closed under complementation.)
2. If L is recursive, so is its complement.
Coding of Objects
Let be a set of objects and a finite alphabet. An encoding of over is a one-to-one function from to *. (x) is called the code of x (under ). When is understood (or not necessary to be specified), we write x instead of (x).
Each decision problem, say P, can be represented by a language over some alphabet by using an appropriate encoding (we denote the language by P, and call it the code of P).
Examples
1)Encodings of natural numbers:
Tally representation: nN 1n{1}*
Binary represetation: nN n{0,1}*
2)Hamiltonian circuit problem (HCP)
Suppose G=(V,E) be a (directed or undirected) graph, where V={v1, …, vn}, E={e1, …, em}. Let ={0,1,#} be an alphabet.
Define the code of vertiex vi and edge ej =(vs,vt) to be vi = # i and ej = vs vt, respectively. Then define the code of G as follows: G = n ## e1… em.
The HCP is represented by the following language (the code of HCP under the above encoding):
HCP = { G | G is a graph that has a Hamiltonian circuit }.
Any graph G (or equivalently its code G) is called an instance of HCP. In general, an instance of a decision problem is a concrete object for which the decision is to be made.
If M is a TM that accepts HCP, then we can determine whether or not a given graph G has a Hamiltonian circuit as follows: Let G be the code of G. Then check if M accepts it. That is to say, G has a Hamiltonian circuit M accepts G, i.e., GL(M). Thus M can be regarded as an algorithm that determines whether or not a given graph has a Hamiltonian circuit.
3) Halting problem for TMs (HTM)
Instances of HTM are TMs. We may assume the following without loss of generality:
i)Tape symbols of any TM are from a1, a2, a3, a4, …, where a1=B, a2=0, a3=1.
ii)Symbols to represent states of any TM are from q1, q2, q3, …
iii)The initial state of any TM is q1, and there is exactly one accepting state, q2.
iv)Input symbols of any TM can be encoded as strings over {0,1}. Thus we consider only those TMs whose input alphabet is {0,1}.
Suppose M=(Q,{0,1},,,q1,{q2}) be an arbitrary DTM. M can be regarded as the set = {(p,a,q,b,d) | (p,a)=(q,b,d)}. Each element, say (qi,as,qj,at,d), of is encoded as string (qi,as,qj,at,d) = 1i01s01j01t01D, where D=1 if d=L, D=2 if d=N, and D=3 if d=R. Finally, define the code of M to be M = 000100200…00k000, where ={1,2,…,k}.
The halting problem for TMs is represented by the following language:
HTM = {Mx | The computation by M on input x{0,1}* halts eventually}.
Solvable and Unsolvable Problems
Let P be a decision problem and x an instance of P. P is defined to be decidable (computable, recursively solvable) if P, the code of P (under an appropriate encoding), is a recursive set. If P is a recursive set, then a TM, say M, that accepts it (i.e., L(M)=P) can beregarded as an algorithm to solve the problem: Given any instance x of P,
the answer for x is ‘yes’ (‘no’, resp.) xP (xP, resp.)
M accepts x (M rejects x, resp.).
THEOREM There is a nonrecursive set. Thus the decision problem represented by the language is not recursively solvable (i.e., there is no algorithm to solve it).
Proof. Let LD = {x{0,1}* | xL(Mx)}, where Mx is the TM whose code is x. (We regard a string over {0,1} which is the code of a TM as an integer. There are strings over {0,1} that are not the code of any TM. In that case, we regard them as TMs that accept the empty set.) Assuming that LD is r.e., there exists a TM Mx that accepts LD. Then we have xLD xL(Mx)=LD, a contradiction. Hence LD is not a r.e. set and therefore nonrecursive either.
The following problems are known to be recursively unsolvable:
- HTM (the halting problem for TMs)
- Hilbert’s tenth problem
- Given a TM, determine whether or not L(M)=.
- Given a TM, determine whether or not L(M) is infinite.
- Given TMs M and M’, determine whether or not L(M)=L(M‘).
- PCP (Post’s correspondence problem): Let be an alphabet and P a finite subset of **. Suppose P={(x1,y1), …, (xn,yn)}. If xi1xi2…xik=yi1yi2…yik, then (i1, i2, …, ik) is called a solution of P. Given any instance of PCP (i.e., and a finite subset of **), determine whether or not P has a solution.
- Given CFGs G and G’, determine whether not L(G)=L(G’).
- Given a CFG G, determine whether or not L(G) is a regular set.
Let P be a property. We denote by [P] the class of r.e. sets/languages that satisfies P:
[P] = {L(M) | M is a TM and L(M) satisfies P}.
Thus [P] represents a “property about r.e.sets/languages”. For example, “being finite” is represented by the set {L | L is a finite r.e.set/language}. P is called trivial if either [P]= or [P]=the class of all r.e. sets/languages.
THEOREM (Rice’s Theorem) P is recursively solvable if and only if [P] is trivial.
Reduction among decision problems
Let L and L’ be languages (or problems). L is many-one reducible to L’,
L m L’ in symbols,
if there is a DTM (transudecer) M such that for any x, xL M(x)L’, where a transducer is a DTM such that |M(x)|1 (i.e., there is at most one output) for any input x.
We assume that there is no move from any accepting ID (thus M(x) is uniquely determined).
Lemma If L m L’ and L is not recursive, so is not L’ either.
Proof. Suppose L m L’ via M and assume that L’ is recursive. Then there exists a halting TM M’ that accepts L’. Define TM N as follows. On input x, N calls M to compute M(x), the output of M on input x. Then N transmit M(x) to M’ as its input. If M’ accepts M(x) then N accepts x. If M’ rejects M(x) then N rejects x. Thus we have
xL M(x)L’, since L m L’ via M,
M’ accepts M(x), since L’=L(M’), and note that M’ is a halting TM,
N accepts x,
which means that N is a hlating TM that accepts L, a contradiction.
Examples
1) The membership problem for r.e. sets (RE-MEMBER: Given a string xand a TM M, determine whether or not x is in L(M)) is knownto be recursive unsolvable. Namely, the code language of the problem, RE-MEMBER={Mx |xL(M)} is notrecursive but r.e.
In general, the membership problem for a class of sets/languagesℒis the problem to determine whether or not xL for any given x and Lℒ. Thus the recursive sets/languages are those sets/languages whose membership problemsare solvable.
Reduction of RE-MEMBER to HTM:
Given an arbitrary x and an arbitraryTM M, we construct a TM N such that xL(M) iff N halts on input x. Formally, RE-MEMBERm HTM via A, where A is an algorithm (= a halting TM) to obtain N from x, that is, A(x)=Nx). The algorithm is as follows. Define N as follows. On input x, N simulates M on input x. If M accepts x, then N halts. If M rejects x (i.e., M enters a nonaccepting state and halts), then N enters an inifinite loop (and thus never halts). If M does not halts on x (thus x is not accepted by M), then so doesn’tN. Then xL(M), i.e., MxRE-MEMBERN halts on x, i.e., A(x)=NxHTM.
2) LDmHTM (HTM is r.e., while LD is not. Prove that if L m L’ and L’ is r.e., so is L.)
3)PCP m(the problem to determine whetheror not LL’=for CFLs L and L’):
From a PCP instance P={(x1,y1), …, (xn,yn)} over alphabet , construct CFGs Gx: S1Sx1R |…| nSxnR | , and Gy: S1Sy1R |…| nSynR | over alphabet{1,…,n}.Then P has a solution iff L(Gx)L(Gy).
1
#011